Algorithms: Design and Analysis, Part 1

Nov 29, 2015 - Algorithms

Today I finished the final exam of Stanford's "Algorithms: Design and Analysis, Part 1" at Coursera. I solved all its programming assignments with JavaScript and put the solutions at GitHub:

shuhei/algo

The course focused on fundamental algorithms and their analysis. What I learned so far were:

Divide-and-conquer algorithms and analysis with Master Method: merge sort and quick sort
Graph algorithms: minimum cut, depth-first and breadth-first search, strongly connected components, Dijkstra's shortest-path
Data structures: [heaps](https://en.wikipedia.org/wiki/Heap_(data_structure), hash tables and binary search trees

As a self-taught programmer, I had been away from formal Computer Science topics like big O notation. But after I learned Machine Learning and tried to implement some ML algorithms for large datasets a few months ago, I noticed that I needed some knowledge of basic algorithms and mathematical analysis of them.

The Algorithms course focused not only on algorithms themselves but also on their performance analysis and mathematical proofs. The analysis and proofs are crucial especially for the cases when we design custom algorithms for real-world problems in the future, and more importantly made me more confident about the algorithms.

Another good side effect of the course was that I got interested in Mathematics. Through the course and a study meetings on SICP with my co-workers, I noticed that Mathematics is interesting but I lacked some prerequisites to understand it. At the moment, I came across Introduction to Mathematical Thinking by Keith Devlin. It was written to fill the gap between the school math, which focuses following given procedures, and the college math, which focuses on thinking. It is perfect for someone like me, who skipped proper Mathematics training at college. I am still on the way reading it but it already started working on my analysis of the SICP exercises.

The part 2 of the course will start probably on March 2016. I cannot wait for it to start and get my eyes open again.