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

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 1 – CS 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.

Administrative Information

Course Staff and Office Hours
Besides the professor (Amit Chakrabarti), we have an experienced team of TAs to support your learning in this course. Details are on the course's Canvas page.
Zoom links
We may occasionally have a lecture, an x-hour, or an office hour held remotely, on Zoom. The relevant Zoom links are posted on the course's Canvas page.
Getting Help
Please use Ed Discussion
to ask any questions related to the course and do not use email unless there is a very good reason to avoid Ed Discussion.
Prerequisites
CS 10 and CS 30, or
a strong mathematics and programming backround and permission of the instructor
Textbooks and References
There is no required textbook. I recommend these three textbooks as references to supplement the lectures. Each book has its strengths (and weaknesses) and each has its own style: I encourage you to read bits of each to figure out which you like best. The answer may even differ from one topic to another.