MIT OCW -Lecture 6(Order Statistics, Median)

I took this Lecture 6 on Sunday.This is what was covered

• What is order statistic i.e. finding the k-th smallest element in an array
• Naive Algorithm for doing it i.e. sorting the array and returning the k-th element from it Theta( nlg(n))
• Algorithm using randomized divide and conquer (basically using quicksort's random partitioning method)
• Intuitive analysis on running time of randomized partition for finding the order statistic i.e. All cases when we split the array into any ratio other than (0:n-1) = Theta(n) and only worst case when we always pick a pivot such that the array is split (0:n-1) = Theta (n**2)
• Formal analysis of running time using Indicative Random variables and substitution method of the above algorithm
• To overcome the worst case of the above algorithm , another algorithm by Rivest, Floyd,Pratt et al was covered 
• The above algorithm basically involves splitting the input array into n/5 groups, finding the median of each n/5 group and then recursively finding the median of these medians.
• The above algorithm was covered at a high level and proof provided on why it would always be Theta(n) run time, but the important part is that the constant C is so high that this may not be a practical algorithm .
  

Other than the above lecture, I also cleaned up this blog a little but changing the URL and the Blog Template,editing a few blogs entries with no title etc..While in the cleaning up mood, I also cleaned up my home directory to group all logically related projects/files into one parent folder.Then I was playing around with C a little and I think I got back 80% of the C I knew 8 years back, pointer arithmetic funness is something I probably need to spend a little more time to get it back.