MIT OCW - Lecture 5(Linear-time Sorting: Lower Bounds, Counting Sort, Radix Sort)

Today morning I took the 5th Lecture which talked about decision trees and linear sorting algorithms.Specifically it covered

• Started by reviewing how fast were the already covered sorting algorithms i.e. Merge,Insertion,Quick and Heap Sort(which is not covered in the lectures but wikipedia has good information on it )
• Discussed what is a computation model
• Comparison sorting model - All sorts which use comparison operators for sorting
• What is a decision tree model
  
• How we can represent sorting algorithms based on comparison in decision tree model
• Proof using decision tree model that all comparison sorts have a lower bound of at least n*lg(n).
  
• Merge sort, Heap Sort and Randomized QuickSort are asymptotically optimal comparison model sorting algorithms
• Counting Sort for sorting in linear time - O(n+k) where n is input size and k is the number of distinct elements in the input
• limitations of Counting sort i.e k needs to be fairly small else it will need very large storage space for keeping the counter array
• What is a Stable sorting algorithm - keeps the relative position of equal elements in output same as in input array
• Radix sort
  
• Run time analysis of Radix sort and also how to optimally break the input integer into digits i.e O(n) and r =lg(n)
  

Then I got a little bored of all the theory so went ahead and installed Go. Go is using Mercurial for version control.I have used CVS, use ClearCase now in work life, use Git for GitHub (still know just the basics) and hopefully I will get to a point with Go where I can compare Mercurial with other version control systems.Always fun to compare different designs for the same problem.

I have been too long in the Object Oriented Java world that I am yet to digest the Cish type of syntax of Go and unfortunately all it's speed is lost on my computer because I run Ubuntu on VMWare and that is sloooooooooooow.