Algorithms: Design and Analysis, Part 2

Part 2 picks up where part 1 left off, so completing part 1 fist is highly recommended. Major topics covered in part 2 include minimum spanning tree algorithms, the knapsack problem, dynamic programming, shortest path problems, the traveling salesman problem, P vs. NP and NP completeness and heuristics for hard problems.

Part 2 is considerably harder than part 1 and the algorithms you write for homework need to be implemented well to get answers in a reasonable amount of time and without exceeding your system's memory. It is possible to complete the class using a high-level language like Python, but you'll probably have to spend a bit more time tweaking your code to get solutions in a reasonable amount of time. In the end I was able to solve all the programming assignments, but this one is definitely not for the feint of heart. I'd like to post some of the algorithms I wrote for the course, but it is against the Coursera honor code to make solutions available to others.

My biggest gripe with the class is that the coverage of the P vs. NP question and NP completeness is brief, so students don’t gain a deep understand of what P vs. NP and NP completeness really mean. The introduction to theoretical computer science by Udacity provides a much more through overview of that particular topic. That said, the overall quality of the instruction and assignments in this course are top notch and I'd highly recommend parts 1 and 2 to anyone looking for a solid foundation in algorithm design and analysis.