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.

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.

MIT OCW - Lecture 4 (Quicksort and Randomized Algorithms)

I completed the 4th Lecture today morning which was on QuickSort and Randomizing QuickSort.Here is what was covered

• How Quick sort fits into Divide and Conquer paradigm
• QuickSort pseudo code and algorithm explanation
• Time analysis of partition method i.e. Theta(n)
• Worst case time analysis of QuickSort i.e. when input is sorted or reverse sorted (Theta (n**2)h
• Best case time analysis of QuickSort when we the pivot always splits the array into two equal halves( Theta(nlg(n))
• Analysis for Average Case time of QuickSort when Pivot splits the array 1/10:9/10 (Theta(nlg(n))
• Time analysis of QuickSort when we alternate between best case and worst case for each recursive partition (Theta(nlg(n))
• Randomized Quicksort - How to overcome worst case by randomly picking a pivot so that the running time is independent of the input array order
• Time analysis of Randomized QuickSort (Theta(nlg(n))
  

This lecture expects a background in basics of probability and random variables(the proof for time analysis of Randomized quick sort uses Indicator random variables)

All in all QuickSort is one of the best practical algorithms available for sorting, of course it may needed to be tuned a little on a case by case basis e.g. if you expect sorted inputs at times, use randomized quick sorts, if the partition array size is say less than 5 elements use some other algorithm to sort it instead of recursively going all the way to one element to partition etc.

Here is a basic implementation of QuickSort in Java

MIT OCW - Lecture 2(Asymptotic Notation - Recurrences - Substitution, Master Method) and Lecture 3( Divide-and-Conquer: Strassen, Fibonacci)

So it was a rather productive weekend

On Saturday, I finished MIT's Lecture 2 which covered the below subjects.It was fairly mathematical

1. Asymptotic notation , Big O, Big Omega, Big Theta, Small Omega, Small O notations
2. Asymptotic analysis of recursive functions

• Substitution Method
• Recursive tree Method
• Master Theorem Method

I also read basics of Arithmetic Series, Geometric Series and Logarithms

I implemented a basic Merge Sort

On sunday I took the Lecture 3 from MIT's open course ware which covered Divide-and-Conquer: Strassen, Fibonacci, Polynomial Multiplication.This lecture covered a lot of neat ways of doing things like Fibonacci numbers and powering a number etc.Specifically it covered

1. Recap of Master Theorem
2. What is Divide and Conquer(Recursion)
3. Running time of Merge Sort using Master Theorem
4. Running time of Binary Search
5. Powering a number (naive way and divide and conquer way)
6. Fibonacci Sequence (Naive recursion, bottom up, naive recursive squaring(using golden ratio),recursive squaring(using Matrix multiplication) )
7. Matrix Multiplication - Divide and Conquer using Strassens method
8. Embedding a binary tree on a chip - (Naive way which needs area of n*lg(n) and another method(derived using Master Theorem) which needed a area of n)

I also implemented a naive solution to this game called Drench which my friend showed me on Friday.The game basically involves coloring a n*n matrix with a simple set of rules.Here is the implementation. For 14*14 sized matrix (which is what the online game drench has) , this solution solved it on an average in about 20 to 22 colorings.I use a random number generator to generate the base matrix.I have not tested it thoroughly yet and the program has a lot of scope for optimization.

I want to finish chapter 4 in the Introduction to Algorithms book (which is recommended for the course) which covers the substitution method, recursion tree method and master theorem before I proceed further with the lecture.That way I will have a better understanding of the Math involved and help me understand other lectures better.Hopefully I can do that tomorrow.

DB2 V9 SYSIBMADM views

If you are using DB2 V9 or later and want lots of nice performance monitoring information such as long running SQL and how much time they are taking, how are your buffer pools performing, lock snapshot etc.There are a bunch of views in the SYSIBMADM schema which makes it easy to write scripts to monitor your database for any offending SQLs

Check out Table 343 in the below Link

http://publib.boulder.ibm.com/infocenter/db2luw/v9/index.jsp?topic=/com.ibm.db2.udb.admin.doc/doc/r0023485.htm

MIT OCW - Lecture 1(Analysis of Algorithms,Insertion Sort,Merge Sort)

I took the first lecture on Introduction to Algorithms from MIT Open CourseWare today morning. I had already completed two lectures one on Introduction to Algorithms and the second on Stacks from National Programme on Technology Enhanced Learning of India's youtube channel

I just wanted to compare between the two before deciding which one I would take fully.I think I will go with the MIT's lectures because

• I found the explanation of how the algorithms work more insightful on the MIT Lectures.
• The IIT lectures uses power point slides whereas the MIT guy uses a black board and writes it out during the class, I liked the second approach better because it gives time for the students to think and black board is so free form that it is easy to explain much better using it
• There are already lecture notes people have taken and posted on their blogs which I can refer to
• MIT Lectures seemed to have more stress on Math (which is hard for me but good for me)
• I already have the book the MIT course recommends to use for this course
  

But since the lecture will be using a black board, I think it is better to use a pen and paper than notepad for the notes.So I will not be posting the notes on the blog, I'll still put the code I do on my github repo.

Today I tried to capture some of the lecture at least using my notepad and here it is
Define Algorithm Analysis
Talked about things in a software program more important than performance
Insertion Sort Algorithm
The Running time of Algorithm depends on
a. type of input (whether fully sorted or partially sorted)
b. size of input
c. want upper bounds of time taken most of the time

Kinds of analysis
Worst case(usually)
T(n) = max time on any input of size n
Average case(sometimes)
T(n) = expected time over all inputs of size n
expected time is time for every input multiplied by the probablility that the input will occur,
hence for this we need the statistical distribution of inputs (for example all inputs are equally likely)
Best Case(bogus)
you can cheat by showing a slow algorithm as good over some input where on vast majority of inputs it is probably very bad

What is insertion sorts running time
Depends on computer
-relative speed ( compare two algorithms on same machine)
-Abolute speed ( compare two algorithms on different machine)

Asymptotic Analysis
a.Ignore Machine dependent constants
b.Look at the growth of the running time with respect to input (instead of looking at the actual running time)

Asymptotic notation
Theta notation - a. Drop lower order terms
b. Ignore leading constants

Analysis of Insertion Sort
Worst Case analysis
T(n) = Summation (j =2 to n) theta(j) = theta(n**2) (Arithemetic Series)

Merge Sort A[1..n]

1 if n = 1 , done , Time = Theta(1)
2 Recursively sort A[1, n/2] and A[(n/2)+1,n] Time =2*Theta(n/2)
3 Merge the two sorted lists = Time = Theta(n)

Merge sort time
if n = 1 (array is already sorted) , T(n) = Theta(1)
if n > 1 , T(N) = 2*Theta(n/2) + Theta (n)

Merge sort - Theta(nlogn) - The analysis was done graphically on blackboard

my github repository

So I installed Eclipse and Git today on my Ubuntu on VMWare Player

Step 1 -> I installed Git following the instructions on this link http://chrisolsen.org/2008/03/10/installing-git-on-ubuntu/
Step 2-> I learn't the quick basics of git commands from here http://www.spheredev.org/wiki/Git_for_the_lazy
Step 3-> I installed eclipse which was straight forward sudo apt-get install eclipse
Step 4-> I opened a github micro account on github.com
Step 5-> I created my private public SSH keys and added the public key to the github command using these instructions http://help.github.com/linux-key-setup/

And here is my github repository http://github.com/bgurupra/gpb_play_projs

I have two folders in it, map_reduce folder has the basic java implementation of the map reduce idea using threads and algorithms folder has the implementation of whatever algorithms I will do based on the algorithm lectures