Spring 2023 — 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
• Lucas Pesenti: 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 topological sort
• Notes on Dijkstra's algorithm
• Notes on data compression
• Notes on maximum flow
• Notes on maximum matching
• Notes on NP-completeness part I
• Notes on NP-completeness part II
• Notes on NP-completeness part III
• Reduction from Vertex Cover to Hamiltonian Circuit
• Notes on NP-completeness part IV

Lecture plan

• 2023-02-07: Introduction
  Contents: 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:
  
• 2023-02-09: Divide-and-conquer I
  Contents: Integer multiplication in O(n^{log_2 3}) time, Master Theorem
  Readings: Sections 2.1 and 2.3
  Instructor: Iozzi
  Suggested Exercises:
  
• 2023-02-10: Divide-and-conquer II
  Contents: Analysis of mergesort, Median in linear time
  Readings: Sections 2.2 and 2.4
  Instructor: Iozzi
  Suggested Exercises:
  
• 2023-02-14: 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:
  
• 2023-02-15, 12:00-13:30: Graph Decomposition II
  Contents: DFS in directed graphs
  Readings: Section 3.3
  Instructor: Iozzi
  Suggested Exercises:
  
• 2023-02-16: Graph Decomposition III
  Contents: Linearization, DFS finds linearization
  Readings: Section 3.3 and Notes on topological sort
  Instructor: Iozzi
  Suggested Exercises:
  
• 2023-02-17: Graph Decomposition III
  Contents: Strongly Connected Components
  Readings: Section 3.4
  Instructor: Iozzi
  Suggested Exercises:
  
• HOMEWORK 1 (turn in on Tue Feb 21 in class)
• 2023-02-21: Shortest Paths I
  Contents: BFS and shortest paths in unweighted graphs
  Readings: Sections 4.1 and 4.2
  Instructor: Trevisan
  Suggested Exercises:
  
• 2023-02-23: Shortest Paths II
  Contents: Continuation of Dijkstra's algorithm, priority queue implementation as sorted lists and as heaps
  Readings: Section 4.5
  Instructor: Trevisan
  Suggested Exercises:
  
• 2023-02-24: Shortest Paths III
  Contents: Dijkstra's algorithm
  Readings: Sections 4.3 and 4.4, notes
  Instructor: Trevisan
  Suggested Exercises:
  
• 2023-02-28: Greedy Algorithms I
  Contents: Minimum spanning tree problem, Kruskal and Prim's algorithm, proofs of correctness
  Readings: Section 5.1
  Instructor: Trevisan
  Suggested Exercises:
  
• 2023-03-03: Greedy Algorithms II
  Contents: Correctness of Kruskal and Prim's algorithm, continued. Union-find data structure
  Readings: Section 5.1
  Instructor: Trevisan
  Suggested Exercises:
  
• HOMEWORK 2 (turn in on Tue Mar 7 in class)
• 2023-03-07: Greedy Algorithms III
  Contents: Prefix codes, Huffman coding
  Readings: Section 5.2, notes
  Instructor: Trevisan
  Suggested Exercises:
  
• 2023-03-10: Greedy Algorithms IV
  Contents: More on data compression, entropy; set cover
  Readings: Section 5.2, 5.4notes
  Instructor: Trevisan
  Suggested Exercises:
  
• MIDTERM
• 2023-03-23: Dynamic Programming I
  Contents: Shortest paths in DAGs, shortest paths with negative weights
  Readings: Section 6.1
  Instructor: Trevisan
  Suggested Exercises:
  
• 2023-03-24: 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:
  
• 2023-03-28: Dynamic Programming III
  Contents: Edit distance, knapsack
  Readings: Section 6.3, 6.4
  Instructor: Trevisan
  Suggested Exercises:
  
• 2023-04-04: 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:
  
• 2023-04-07: Flows II
  Contents: Reduction to other problems, Karger's min cut algorithms
  Readings: Notes, Section 7.3
  Instructor: Trevisan
  Suggested Exercises:
  
• HOMEWORK 3 (turn in on Tue Apr 18 in class)
• 2023-04-18: Linear Programming I
  Contents: Introduction, geometry of solutions, weak duality
  Readings: Sections 7.1 and 7.4
  Instructor: Iozzi
  Suggested Exercises:
  
• 2023-04-20: Linear Programming II
  Contents: The simplex algorithm
  Readings: Section 7.6
  Instructor: Iozzi
  Suggested Exercises:
  
• 2023-04-21: Linear Progamming III
  Contents: Problems modelled by linear programming: flows, zero-sum games
  Readings: Sections 7.2 and 7.5
  Instructor: Iozzi
  Suggested Exercises:
  
• 2023-04-27: Linear Programming IV
  Contents: Game Theory
  Readings: Section 7.5
  Instructor: Iozzi
  Suggested Exercises:
  
• 2023-04-28: NP-completeness I
  Contents: Combinatorial explosion, search problems, P, NP, reductions, NP-completeness
  Readings: Section 8.1, notes
  Instructor: Trevisan
  Suggested Exercises:
  
• 2023-05-02: NP-completeness II
  Contents: NP-completeness of Independent Set and Subset Sum
  Readings: Sections 8.2 and 8.3, notes
  Instructor: Trevisan
  Suggested Exercises:
  
• 2023-05-05: NP-completeness III
  Contents: NP-completeness of Set Cover, Partition, Bin Packing, Scheduling, Hamiltonian Circuit, TSP
  Readings: Section 8.3, notes, and reduction to Hamiltonian Circuit
  Instructor: Trevisan
  Suggested Exercises:
  

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


• 2023-05-12: Final review
  Contents: Whole syllabus review, all questions answered
  Readings: Notes
  Instructor: Trevisan
  Suggested Exercises: