Spring 2022 — 30540 Computer Science 2

General information

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

Textbooks and other readings

• S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani. Algorithms

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

• Notes on the proof of correctness of Dijkstra's algorithm
• Notes on data compression
• Notes on network flows and cuts
• Notes on reductions, cuts, and matchings
• Notes on NP-completeness, Part 1
• Notes on NP-completeness, Part 2
• Notes on NP-completeness, Part 3
• Notes on NP-completeness, Part 4

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
  Readings: Chapter 0
  Instructor: Iozzi
  Suggested Exercises:
  
• 2022-02-08: Divide-and-conquer I
  Contents: Integer multiplication in O(n^{log_2 3}) time, analysis of mergesort
  Readings: Sections 2.1 and 2.3
  Instructor: Iozzi
  Suggested Exercises:
  
• 2022-02-10: Divide-and-conquer II
  Contents: Median in linear time, Master Theorem
  Readings: Sections 2.2 and 2.4
  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
  Readings: Sections 3.1 and 3.2
  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
  Readings: Notes
  Instructor: Iozzi
  Suggested Exercises:
  
• 2022-02-18: Shortest Paths I
  Contents: BFS and shortest paths in unweighted graphs
  Readings: Sections 4.1 and 4.2
  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
  Readings: Section 4.5
  Instructor: Trevisan
  Suggested Exercises:
  
• 2022-02-25: Greedy Algorithms I
  Contents: Minimum spanning tree problem, Kruskal and Prim's algorithm, proofs of correctness
  Readings: Section 5.1
  Instructor: Trevisan
  Suggested Exercises:
  
• 2022-03-01: Greedy Algorithms II
  Contents: Correctness of Kruskal and Prim's algorithm, continued. Union-find data structure
  Readings: Section 5.1
  Instructor: Trevisan
  Suggested Exercises:
  
• 2022-03-03: LAB 2
  Contents: Covers all material up to MST
  Readings: Notes
  Instructor: Anceschi
  Suggested Exercises:
  
• 2022-03-04: Greedy Algorithms III
  Contents: Prefix codes, Huffman coding
  Readings: Section 5.2, notes
  Instructor: Trevisan
  Suggested Exercises:
  
• 2022-03-08: Greedy Algorithms IV
  Contents: More on data compression, entropy; set cover
  Readings: Section 5.2, 5.4notes
  Instructor: Trevisan
  Suggested Exercises:
  
• 2022-03-10: Dynamic Programming I
  Contents: Shortest paths in DAGs, shortest paths with negative weights
  Readings: Section 6.1
  Instructor: Trevisan
  Suggested Exercises:
  
• 2022-03-11: Lab 3
  Contents: Final review before Midterm
  Readings: Notes
  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
  Readings: Sections 6.1, 6.6
  Instructor: Trevisan
  Suggested Exercises:
  
• 2022-03-29: Dynamic Programming III
  Contents: Edit distance, knapsack
  Readings: Section 6.3, 6.4
  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
  Readings: Section 7.2, notes
  Instructor: Trevisan
  Suggested Exercises:
  
• 2022-04-05: Flows II
  Contents: Reduction to other problems, Karger's min cut algorithms
  Readings: Notes, Section 7.3
  Instructor: Trevisan
  Suggested Exercises:
  

2022-04-07: Lab 4
Contents: Flows, cuts and matchings
Readings: Notes
Instructor: Anceschi
Suggested Exercises:


• 2022-04-08: Linear Programming I
  Contents: Introduction, geometry of solutions, weak duality
  Readings: Sections 7.1 and 7.4
  Instructor: Iozzi
  Suggested Exercises:
  
• 2022-04-11: Linear Programming II
  Contents: The simplex algorithm
  Readings: Section 7.6
  Instructor: Iozzi
  Suggested Exercises:
  
• 2022-04-12: Linear Progamming III
  Contents: Problems modelled by linear programming: flows, zero-sum games
  Readings: Sections 7.2 and 7.5
  Instructor: Iozzi
  Suggested Exercises:
  
• 2022-04-13: Lab 5
  Contents: Linear programmings
  Readings: Notes
  Instructor: Iozzi
  Suggested Exercises:
  
• 2022-04-26: NP-completeness I
  Contents: Combinatorial explosion, search problems, P, NP, reductions, NP-completeness
  Readings: Section 8.1, notes
  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
  Readings: Section 8.3 and notes
  Instructor: Trevisan
  Suggested Exercises:
  

2022-05-03: NP-completeness IV
Contents: Boolean circuits, and NP-completeness of Circuits SAT and 3SAT
Readings: notes
Instructor: Trevisan
Suggested Exercises:


• 2022-05-05: Lab 6
  Contents: Computational complexity
  Readings: Notes
  Instructor: Chen
  Suggested Exercises:
  
• 2022-05-06: Final review
  Contents: Whole syllabus review, all questions answered
  Readings: Notes
  Instructor: Trevisan
  Suggested Exercises: