

# 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

• Lecture Notes will be posted when the content of lectures deviates from the book

## Lectures

### Past Lectures

Week 1 (Divide-and-Conquer)
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)

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)

### 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