CMSC451 Design and Analysis of Computer Algorithms

What does it say on Testudo?

Fundamental techniques for designing efficient computer algorithms, proving their correctness, and analyzing their complexity. General topics include graph algorithms, basic algorithm design paradigms (such as greedy algorithms, divide-and-conquer, and dynamic programming), network flows, NP-completeness, and other selected topics in algorithms.

Why did I take this class?? Should I have taken this class???

Definitely a very interesting and useful class. I would have taken this eventually, but I think the online format for this class is suboptimal. Probably more valuable in-person.

Review

I learned a lot of useful algorithm patterns, but some of the algorithms seem so niche that they're just for fun. We covered all of the topics in the description and syllabus. The full list:

• Introduction and mathematical background
• Graph algorithms: connectivity, bipartiteness, topological sorting
• Greedy algorithms: shortest paths, minimum spanning trees, scheduling
• Divide-and-conquer algorithms: mergesort, closest points, integer multiplication
• Dynamic programming: weighted interval scheduling, knapsack, sequence alignment, shortest paths
• Network flows: Ford-Fulkerson algorithm, applications
• NP-completeness: P and NP, reductions, the Cook-Levin theorem
• Approximation algorithms: load balancing, set cover
• Randomized algorithms: minimum cut, game tree evaluation
• Quantum algorithms: quantum circuits, Deutsch’s problem

The first half of the class up to the midterm (before dynamic programming) was pretty easy. The only thing is that the proofs of correctness tend to be extremely handwavy. I think the TAs didn't really take grading seriously since the averages on the homeworks and midterm were very high. For the second half of the class, I stopped attending live lectures since they were basically like office hours.

Some notes:

• Topological sorting is associated with directed acyclic graphs (this seems to be common knowledge for computer science)
• Network flows apparently falls under graph theory material according to Kyoto-U's 2021 entrance exam
• Quantum algorithms are confusing