In the past few weeks we have revisited some previously learned sorting algorithms: Selection, Insertion and Bubble sorts and also learned some new sorts like Quick, Merge and Python's built in Timsort.
Rather than just learning the concept and implementations of these algorithms, we looked instead at the 'efficiency' of these algorithms. Efficiency is, in essence, measured in the time and space complexity of the algorithms. We focused on time complexity - the typical run-time of the algorithm and specifically, the upper bound on this run-time (the worst case, denoted using Big-Oh).
We saw that bubble and insert have the smallest time complexity in the best case (the case of an already, or nearly, sorted list) of big O of n, or O(n). But, in the worst case (a reverse sorted list) they fare worst with a time complexity of O(n^2)
Selection sort, as expected, came out at bottom with best and worst case time efficiencies of O(n^2).
Having worked with these algorithms before, the results weren't all too surprising. What was interesting though was seeing how small changes in their Python implementations could speed up their runtimes (though time complexity remains the same). For instance, calls to repeated calls to len (in loops) would slow down the runtime but this could be remedied by introducing a temporary variable to only have to call len once.
Other tweaks to improve runtime were less useful: Trying to end bubble sort early by seeing if the last scan of the list had any swaps didn't cause a significant boost to runetime.
Ofcourse, the most interesting part of the last few weeks has been working with mergesort and quicksort. I will breifly re-iterate their algorithms in my own words and the comment on any interesting aspects of them.
Both of these new algorithms are recursive. Mergesort cuts the list to be sorted into two halves, then recursively calls mergesort on the halves and finally, 'merges' the two halves back into a single list. The splitting into two halves has a time complexity of log(n) and the merge operation runs in time complexity of n. So altogether mergesort runs in best and worst case of O(nlog(n)). Like the previous algorithms, we also explored ways to speed up mergesorts runtime: By continually updating the original list and not replacing it, we were able to significantly cut down average runtime (though still O(nlog(n) ofcourse).
Quicksort first chooses a 'pivot' (any item in the list) and then splits the list into two galves: items bigger than pivot and smaller than pivot. It then (recursively) calls quicksort on the two sub lists. Quicksort is nearly identical in time complexity to mergesort except in the worst case it has a time complexity in O(n^2). We explored a similar improvement technique as the one to mergesort but it yeilded no benefits for quicksort.
All in all, this part of the course really helped solifidy my understanding of these sorting algorithms - we really got into the fundamental workings of them, took them apart, analysed them, compared them to others and explored techniques of improving them.
Thursday, 27 March 2014
Tuesday, 11 March 2014
Linked Structures
The central topic of Week 8 has been linked lists and a variant of binary trees - binary search trees (BSTs). Both these data structures are related by one particular property: each node (or element) of these data structures contains a reference to one (in the case of linked lists) or more (two in the case of BSTs) 'child' node(s).
For linked lists, we considered two definitions:
1. Lists containing an item (head) and the remaining linked list (rest).
2. As individual objects (nodes) containing some value and a reference to another node.
Though we saw in class that both these definitions employ similar functions - some functions are implemented quite differently, however the general structure/usage of linked lists stays the same.
Speaking of linked list usage, one interesting point mentioned in lecture this week was different usages of prepend(head).
In past weeks you would make a copy of the linked list and assign this copy as 'rest'. Then 'head' would become the new head being prepended. However, an alternative implementation was to make a new linked list in the prepend function where 'head' is the new head and 'rest' is self. Then this new linked list was returned. This seems a lot cleaner but requires the client to update their linked list every time prepend it called. I.e. x.prepend(1) becomes x = x.prepend(1).
Besides linked lists we looked at BSTs, a variant of binary trees already seen in past weeks. We looked at BSTs of the following kind: binary trees with the constraint that the left child is smaller than the root and the right child is larger than the root.
It was claimed that this would allow for more efficient searches. At first I didn't see how this claim was true, but thinking recursively I realized that when we say the left child is always smaller than the root, the entire left subtree will contain elements smaller than root and vice versa for the right child/subtree.
This all relies on the recursive insert(item) function that ensures that the constraint holds. Observing the way insert worked really helped solidify my understanding of recursion in binary trees and now we have a neat O(log n) search algorithm to make use of!
For linked lists, we considered two definitions:
1. Lists containing an item (head) and the remaining linked list (rest).
2. As individual objects (nodes) containing some value and a reference to another node.
Though we saw in class that both these definitions employ similar functions - some functions are implemented quite differently, however the general structure/usage of linked lists stays the same.
Speaking of linked list usage, one interesting point mentioned in lecture this week was different usages of prepend(head).
In past weeks you would make a copy of the linked list and assign this copy as 'rest'. Then 'head' would become the new head being prepended. However, an alternative implementation was to make a new linked list in the prepend function where 'head' is the new head and 'rest' is self. Then this new linked list was returned. This seems a lot cleaner but requires the client to update their linked list every time prepend it called. I.e. x.prepend(1) becomes x = x.prepend(1).
Besides linked lists we looked at BSTs, a variant of binary trees already seen in past weeks. We looked at BSTs of the following kind: binary trees with the constraint that the left child is smaller than the root and the right child is larger than the root.
It was claimed that this would allow for more efficient searches. At first I didn't see how this claim was true, but thinking recursively I realized that when we say the left child is always smaller than the root, the entire left subtree will contain elements smaller than root and vice versa for the right child/subtree.
This all relies on the recursive insert(item) function that ensures that the constraint holds. Observing the way insert worked really helped solidify my understanding of recursion in binary trees and now we have a neat O(log n) search algorithm to make use of!
Sunday, 2 March 2014
Definition of Recursion: See "Recursion".
The past few weeks of CSC148 have involved a Mid-Term, the due date of Assignment 1, some interesting labs on recursive data structures (trees, linked lists) and the beginning of Assignment 2 part 1. I think now is a good time to reflect back on one of the core concepts that has permeated all the topics of the past few weeks: Recursion.
In past weeks' SLOGs, I have discussed some of the introductory concepts of recursion - from base and recursive cases to modelling a problem recursively. In what follows, I will seek to elaborate more on this latter topic as well as some applications of recursion that I found interesting.
The tour of four stools in our Tours of Hanoi assignment was the first major application of recursion - besides lecture/labs - we had to do individually. The first step of the algorithm obviously recursive (it was in the assignment handout!) - we had to attain a value for 'i' which would allow the rest of the algorithm to run most effectively. I toyed with this a bit until I decided to implement this recursive algorithm in a brute force manner - I had my program shift through all legitimate 'i' values until an optimal one was found. The recursive call here was simple: it was written write in the formula!
Next we had the actual four peg algorithm itself. With the value of 'i' selected, these 3 recursive calls worked to shift the blocks of cheese to the destination. Here is where I saw the key to the entire algorithm: the three peg algorithm was simply a sub-part of the four peg algorithm. Once I moved n-i cheeses to an intermediate stool, I called the three peg algorithm to do the work of bringing the i cheeses to the destination. In essence, I thought of it as 'recursion within 'recursion'. "Recurception" if you will ;)
Though this seems overwhelming for an introductory recursion assignment, struggling through it really helped to see the way recursion provided a neat and intuitive solution to an otherwise difficult problem.
Alas, my thirst for more recursive insights was not quenched and immediately began thinking of other problems that could have very elegant recursive solutions. What came to mind was the fundamental theorem of arithmetic: that every integer greater than 1 can be written as a unique factorization of prime numbers. I decided to put my recursive knowledge to the test and design an algorithm to produce the prime factors of some n.
First I wrote a function to generate prime numbers from 1 to n and then I began work on the recursive function. The algorithm is rather simple and elegant with recursion: Loop through the list of generated primes and if a prime divides n, add it to the list of factors and then recursively call the algorithm to generate the prime factors of what is left when that prime factor divides n. And so, a list of prime factors for some n are generated.
This algorithm really helped to affirm my grasp of the recursion learned so far: You choose your base case and recursive call - trace a few simple cases and then hope for the best! Of course, a great deal of thought needs to go into choosing your recursive calls but once you have it for one, you may assume it will work for the cases that will follow - a lot like inductive reasoning!
In past weeks' SLOGs, I have discussed some of the introductory concepts of recursion - from base and recursive cases to modelling a problem recursively. In what follows, I will seek to elaborate more on this latter topic as well as some applications of recursion that I found interesting.
The tour of four stools in our Tours of Hanoi assignment was the first major application of recursion - besides lecture/labs - we had to do individually. The first step of the algorithm obviously recursive (it was in the assignment handout!) - we had to attain a value for 'i' which would allow the rest of the algorithm to run most effectively. I toyed with this a bit until I decided to implement this recursive algorithm in a brute force manner - I had my program shift through all legitimate 'i' values until an optimal one was found. The recursive call here was simple: it was written write in the formula!
Next we had the actual four peg algorithm itself. With the value of 'i' selected, these 3 recursive calls worked to shift the blocks of cheese to the destination. Here is where I saw the key to the entire algorithm: the three peg algorithm was simply a sub-part of the four peg algorithm. Once I moved n-i cheeses to an intermediate stool, I called the three peg algorithm to do the work of bringing the i cheeses to the destination. In essence, I thought of it as 'recursion within 'recursion'. "Recurception" if you will ;)
Though this seems overwhelming for an introductory recursion assignment, struggling through it really helped to see the way recursion provided a neat and intuitive solution to an otherwise difficult problem.
Alas, my thirst for more recursive insights was not quenched and immediately began thinking of other problems that could have very elegant recursive solutions. What came to mind was the fundamental theorem of arithmetic: that every integer greater than 1 can be written as a unique factorization of prime numbers. I decided to put my recursive knowledge to the test and design an algorithm to produce the prime factors of some n.
First I wrote a function to generate prime numbers from 1 to n and then I began work on the recursive function. The algorithm is rather simple and elegant with recursion: Loop through the list of generated primes and if a prime divides n, add it to the list of factors and then recursively call the algorithm to generate the prime factors of what is left when that prime factor divides n. And so, a list of prime factors for some n are generated.
This algorithm really helped to affirm my grasp of the recursion learned so far: You choose your base case and recursive call - trace a few simple cases and then hope for the best! Of course, a great deal of thought needs to go into choosing your recursive calls but once you have it for one, you may assume it will work for the cases that will follow - a lot like inductive reasoning!
Subscribe to:
Posts (Atom)