# Spring 2022 — 30540 Computer Science 2

This course introduces the beautiful and powerful techniques of theoretical computer science for the design of algorithms, the analysis of algorithms, and the study of the computational complexity of problems.

### General information

Instructors: Luca Trevisan, Fabrizio Iozzi
Teaching assistants: NiccolĂ˛ Anceschi, Caicai Chen

Lectures:

• Tuesdays 14:00-16:30
• Thursdays 8:30-10:00
• Fridays 14:00-16:30

Office hours:

• Fabrizio Iozzi: TBA
• Luca Trevisan: TBA
• NiccolĂ˛ Anceschi: TBA
• Caicai Chen: TBA

• S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani. Algorithms
It is easy to find online a pdf of the Dasgupta et al. book. As far as we know, these pdf copies are circulating with the blessing of the authors.

Additional lecture notes will be distributed when the content of the lectures deviates from the book.

### Lecture plan

• No class on 2022-02-03

• 2022-02-04: Introduction
Contents: What this course is about. Review of the topics and goals of the course. Preview of some highlights. Mathematical preliminaries: proving things by induction, bounding summations, big-Oh and little-oh notations, basics of probability
Instructor: Iozzi
Suggested Exercises:
• 2022-02-08: Divide-and-conquer I
Contents: Integer multiplication in O(n^{log_2 3}) time, analysis of mergesort
Instructor: Iozzi
Suggested Exercises:
• 2022-02-10: Divide-and-conquer II
Contents: Median in linear time, Master Theorem
Instructor: Iozzi
Suggested Exercises:
• 2022-02-11: Graph Decomposition I
Contents: Graphs, representations of graphs, directed and undirected graphs, paths, connected components, DFS for connected components in undirected graphs
Instructor: Iozzi
Suggested Exercises:
• 2022-02-15: Graph Decomposition II
Contents: Directed acyclic graphs, linearization, DFS finds linearization
Readings: Section 3.3 and Notes on topological sort
Instructor: Iozzi
Suggested Exercises:
• 2022-02-17: LAB 1
Contents: Covers all material up to DFS
Instructor: Iozzi
Suggested Exercises:
• 2022-02-18: Shortest Paths I
Contents: BFS and shortest paths in unweighted graphs
Instructor: Trevisan
Suggested Exercises:
• 2022-02-22: Shortest Paths II
Contents: Dijkstra's algorithm
Readings: Sections 4.3 and 4.4, notes
Instructor: Trevisan
Suggested Exercises:
• 2022-02-24: Shortest Paths III
Contents: Continuation of Dijkstra's algorithm, priority queue implementation as sorted lists and as heaps
Instructor: Trevisan
Suggested Exercises:
• 2022-02-25: Greedy Algorithms I
Contents: Minimum spanning tree problem, Kruskal and Prim's algorithm, proofs of correctness
Instructor: Trevisan
Suggested Exercises:
• 2022-03-01: Greedy Algorithms II
Contents: Correctness of Kruskal and Prim's algorithm, continued. Union-find data structure
Instructor: Trevisan
Suggested Exercises:
• 2022-03-03: LAB 2
Contents: Covers all material up to MST
Instructor: Anceschi
Suggested Exercises:
• 2022-03-04: Greedy Algorithms III
Contents: Prefix codes, Huffman coding
Instructor: Trevisan
Suggested Exercises:
• 2022-03-08: Greedy Algorithms IV
Contents: More on data compression, entropy; set cover
Instructor: Trevisan
Suggested Exercises:
• 2022-03-10: Dynamic Programming I
Contents: Shortest paths in DAGs, shortest paths with negative weights
Instructor: Trevisan
Suggested Exercises:
• 2022-03-11: Lab 3
Contents: Final review before Midterm
Instructor: Anceschi
Suggested Exercises:
• No class on 2022-03-24

• 2022-03-25: Dynamic Programming II
Contents: Shortest paths with negative weights. All-pairs shortest paths. Rethinking Dijkstra's algorithm
Instructor: Trevisan
Suggested Exercises:
• 2022-03-29: Dynamic Programming III
Contents: Edit distance, knapsack
Instructor: Trevisan
Suggested Exercises:
• No class on 2022-03-31

• 2022-04-01: Flows I
Contents: Flows in networks, residual network, Ford-Fulkerson, Max flow min cut theorem, analysis of Edmonds-Karp
Instructor: Trevisan
Suggested Exercises:
• 2022-04-05: Flows II
Contents: Reduction to other problems, Karger's min cut algorithms
Instructor: Trevisan
Suggested Exercises:
• 2022-04-07: Lab 4
Contents: Flows, cuts and matchings
Instructor: Anceschi
Suggested Exercises:

• 2022-04-08: Linear Programming I
Contents: Introduction, geometry of solutions, weak duality
Instructor: Iozzi
Suggested Exercises:
• 2022-04-11: Linear Programming II
Contents: The simplex algorithm
Instructor: Iozzi
Suggested Exercises:
• 2022-04-12: Linear Progamming III
Contents: Problems modelled by linear programming: flows, zero-sum games
Instructor: Iozzi
Suggested Exercises:
• 2022-04-13: Lab 5
Contents: Linear programmings
Instructor: Iozzi
Suggested Exercises:
• 2022-04-26: NP-completeness I
Contents: Combinatorial explosion, search problems, P, NP, reductions, NP-completeness
Instructor: Trevisan
Suggested Exercises:
• 2022-04-28: NP-completeness II
Contents: NP-completeness of Independent Set, Clique, Set Cover, Subset Sum
Readings: Sections 8.2 and 8.3, notes
Instructor: Trevisan
Suggested Exercises:
• 2022-04-29: NP-completeness III
Contents: NP-completeness of Partition, Bin Packing, Scheduling, Hamiltonian Circuit, TSP
Instructor: Trevisan
Suggested Exercises:
• 2022-05-03: NP-completeness IV
Contents: Boolean circuits, and NP-completeness of Circuits SAT and 3SAT