Lectures: Tuesdays and Thursdays, 16:50-18:20 — all lectures will be remote using bboard

Office hours: by appointment only

Check the calendar below to see which lectures and office hours will be remote and which ones will be in presence

The exam will be a *take-home* final which will be out on December 11 and due December 18.

Textbook:

- Sanjoy Dasgupta, Christos Papadimitriou, and Umesh Vazirani

**Algorithms**

McGraw-Hill

(A PDF version is available online) - Lecture Notes will be posted when the content of lectures deviates from the book

- 11/03: Introduction to the course, divide and conquer method, integer multiplication, master theorem (whiteboard transcript)
- 11/05: Mergesort, median, and introduction to FFT (whiteboard transcript)

Recommended exercises: 2.5 and 2.17

**Week 2 (FFT, Graphs and DFS)**

- 11/10: FFT. Graphs, paths, connectivity (whiteboard transcript)
- 11/12: DFS and use of DFS to find connected components in undirected graphs and to find topological sort of directed acyclic graphs (whiteboard transcript)

Recommended exercises: 3.8 and 3.12

**Week 3 (More Graph Problems)**

- 11/17: use of DFS to find strongly connected components in directed graphs. BFS (whiteboard transcript)
- 11/19: Dijkstra's algorithm (whiteboard transcript) (additional notes)

Recommended exercises: 3.29, 3.31, 4.4, 4.8, 4.17(a)

**Week 4 (Greedy Algorithms)**

- 11/24: Flows in networks, Ford-Fulkerson algorithm (whiteboard transcript) (additional notes)

- 11/03: Introduction to the course, divide and conquer method, integer multiplication, master theorem
- 11/05: Mergesort, median, FFT

**Week 2 (Graphs and DFS)**

- 11/10: Graphs, representations of graphs, connected components, strongly connected components
- 11/12: Algorithms based on DFS: connected components, strongly connected components and topological sort

**Week 3 (Shortest Path Problems)**

- 11/17: Distances, shortest paths, BFS
- 11/19: Dijkstra's algorithm

**Week 4 (Greedy Algorithms)**

- 11/24: Flows in networks, Ford-Fulkerson algorithm
- 11/26: Minimum Spanning Tree, Huffman algorithm

**Week 5 (Dynamic Programming Algorithms)**

- 12/1: All-pair shortest path and shortest paths in DAGs, longest increasing subsequence, edit distance
- 11/3: Knapsack, Viterbi's algorithms

**Week 6 (NP-completeness)**

- 12/09: P, NP, reductions, NP-completeness, NP-completeness of Circuit-SAT
- 12/10: NP-complete problems