## 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
- 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.
- [CLRS] Cormen, Leiserson, Rivest, Stein.
*Introduction to Algorithms*, 4th edition. [EPUB available @ Dartmouth library] - [KT] Kleinberg, Tardos.
*Algorithm Design*. - [Eri] Erickson.
*Algorithms*. [available as a free e-book]

- [CLRS] Cormen, Leiserson, Rivest, Stein.

*do not use email*unless there is a

*very*good reason to avoid Ed Discussion.