Impressions from Algorithms Course
I recently finished Princeton’s Algorithms I and II on Coursera. The course covers a lot of material, from data structures (List, Queue, Hash Table, Trees, Graphs, Tries) to algorithms (Sorting, BFS, DFS, Shortest Path, RegEx, Compression).
The course requires more time than other courses. Expect to spend 3 hours a week watching lectures, an hour answering the quiz for every chapter, and the weekly exercises can take a few hours to solve.
Learning the history of CS was also interesting. How David Hilbert, Kurt Godel, Alan Turning, Alonzo Church and John von Neumann asked the basic questions about computing. And that Alan Turing did his PhD in Princeton.
Previously I used to think search problems are related to searching arrays. Now I know it means problems where the answer is a yes/no and that an answer can be checked in polynomial time. Contrast that with other types of problems mentioned in the course: optimization and decision problems.
The exercises are fun. They are done in Java and you will get to learn which algorithms Java uses for sorting / searching / string operations. I was especially impressed with solving a baseball elimination using max flow.
Another very useful data structure is the Interval Tree. Interview questions involving intervals are very popular and this structure makes interacting with intervals much more efficient.
The only topic I wish would have been covered more is dynamic programming. Dynamic programming is a technique of breaking down big calculation into small subproblems, solve the subproblems from the easiest once and use those solutions as part of solving the bigger subproblems.
Lastly, the course ended with a song “longest path” recorded by Daniel J. Barrett in 1988 while a student at Johns Hopkins. Unlike the shortest path, there is no known polynomial time algorithm for the longest path. And one can spend their entire graduate school trying to find an algorithm for this problem. Listen to the song here