Fall 2020 — 40974 Computer Science 2

This course is an introduction to algorithm design. Topics will include divide-and-conquer, greedy, and dynamic programming approaches to the design of algorithms for string processing problems, network optimization problems, and problems about cuts, flows and matchings in graphs. We will also cover the theory of NP-completeness.

General information

Instructor: Luca Trevisan

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

Lectures

Past Lectures

Week 1 (Divide-and-Conquer)

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)

References: Chapter 2 (skip Sections 2.5 and 2.6)
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)

References: Sections 2.5, 3.1, 3.2 and 3.3
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)

References: Sections 3.4, 4.1, 4.2, 4.3, 4.4 and 4.5, 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)

References: additional lecture notes

Lecture Plan

Week 1 (Divide-and-Conquer)

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

References: Chapter 2 (skip Section 2.5)

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

References: Chapter 3

Week 3 (Shortest Path Problems)

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

References: Chapter 4

Week 4 (Greedy Algorithms)

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

References: Sections 7.1, 5.1, 5.2, additional lecture notes

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

References: Chapter 6 (skip sections 6.5 and 6.7), additional lecture notes

Week 6 (NP-completeness)

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

References: Chapter 8, additional lecture notes