I finished the Algorithm Specialization offered by prof Tim Roughgarden of Stanford University on coursera a few days ago. It has been a wonderful online learning journey albeit a challenging one. The part II of the specialization focuses on topics such as Dynamic Programming, Greedy Algorithms, and computational tractability. To pass the course, it requires a deep level of understanding of the content rather than merely ingesting/memorizing the content at face value.

I am introduced to some of the best hits algorithms and paradigms in computer science, and some of the particularly interesting ones to me include the Johnson’s algorithm and Papadimitriou’s randomized local search algorithm for the 2sat problem. The former involves using clever rewighting to find the shortest paths between all pairs of vertices in a graph when path weights can be negative. And the latter uses fundamental observation in a random walk on a path to derive boundary conditions on the number of iterations it takes to determine 2-satisfiability. The intuition is often not straightforward in the beginning but prof. Roughgarden has a talent in building up your knowledge to appreciate the beauty of the proofs behind these results.