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.