Course Description
This course is about the art of designing efficient algorithms for a wide range of fundamental computational tasks and the science of proving the correctness of such algorithms and formally analyzing their time complexity.
The course will introduce the following basic design paradigms: divide-and-conquer, greedy algorithms, dynamic programming, amortized analysis, and randomization. The computational tasks studied will span several domains. These include sorting and order statistics, computing with integers and number-theoretic algorithms, algorithms on graphs, and geometric algorithms.
Writing mathematical proofs will be required throughout this course. Students are expected to have extensive prior experience with writing proofs. Taking CS 30 will provide this experience.
Students will be expected to be experienced programmers before taking this course, so that they are able to reason about algorithms/code at a high level without seeing actual lines of code in front of them. Taking our department's CS 1 – CS 10 sequence will provide this experience.