CS 31: Algorithms [archived]
Spring 2023 | 2A hour (TTh 14:25—16:15; W 17:30—18:20) | Irving 080
Professor Amit Chakrabarti

## 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, algorithms on graphs, geometric algorithms, computing with integers, and number-theoretic 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 1CS 10 sequence will provide this experience.

## Learning Objectives

The goal of this course is to grow you intellectually so that (ideally) you are able to do the following things.

• basic Describe an algorithm with mathematical precision, yet at a high enough level of abstraction so as to avoid trivial details.
• basic Analyze a well-described algorithm to work out whether it is efficient and, if so, just how efficient it is (with a focus on time complexity).
• advanced Be able to write a convincing mathematical proof that an algorithm is correct, i.e., that it does compute what it was intended to compute.
• basic Be knowledgeable about a canon of fundamental algorithms and associated data structures: this includes being able to recall the algorithms from memory, knowing the conditions under which they work, and knowing their time complexity.
• basic/advanced Adapt algorithms from the above canon, perhaps creatively, to solve novel computational problems.
• advanced Understand and apply common algorithm design paradigms to create novel algorithms for well-specified computational tasks.