Spring 2021 — 30540 Computer Science 2

General information

Lectures:

• Tuesdays 14:00-16:30 Room N20
• Thursdays 8:30-10:00 Room N11
• Fridays 14:00-16:30 Room N06

Office hours:

• Luca Trevisan: Thursdays 15:00-16:00 (appointment required)

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 the analysis of Dijkstra's algorithm
• Notes on the analysis of Huffman's algorithm
• Notes on flows in networks
• Notes on NP-completeness: Part 1, Part 2, and Part 3

• Board transcript of lecture of March 5
• Board transcript of lecture of March 24
• Board transcript of lecture of March 25
• Board transcript of lecture of March 26
• Board transcript of lecture of March 30

Lecture plan

• 2021-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, basic probability
  Readings: Chapter 0
  Instructor: Iozzi
  Suggested Exercises:
  
• 2021-02-05: 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:
  
• 2021-02-09: Divide-and-conquer II
  Contents: Median in linear time, Master Theorem
  Readings: Sections 2.2 and 2.4
  Instructor: Iozzi
  Suggested Exercises:
  
• 2021-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:
  
• 2021-02-12: Graph Decomposition II
  Contents: Directed acyclic graphs, linearization, DFS finds linearization
  Readings: Section 3.3 and Notes on topological sort
  Instructor: Trevisan
  Suggested Exercises:
  
• 2021-02-16: Graph Decomposition III
  Contents: Finding strongly connected components by running two DFSs
  Readings: Section 3.4
  Instructor: Trevisan
  Suggested Exercises:
  
• 2021-02-18: Shortest Paths I
  Contents: BFS and shortest paths in unweighted graphs
  Readings: Sections 4.1 and 4.2
  Instructor: Trevisan
  Suggested Exercises:
  
• 2021-02-19: Shortest Paths II
  Contents: Dijkstra's algorithm
  Readings: Sections 4.3 and 4.4, notes
  Instructor: Trevisan
  Suggested Exercises:
  
• 2021-02-23: 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:
  
• 2021-02-25: Lab I
  Contents: Discuss solutions to exercises
  Readings: Notes
  Instructor: Iozzi
  Suggested Exercises:
  
• 2021-02-26: Greedy Algorithms I
  Contents: Minimum spanning tree problem, Kruskal and Prim's algorithm, proofs of correctness
  Readings: Section 5.1
  Instructor: Trevisan
  Suggested Exercises:
  
• 2021-03-02: Greedy Algorithms II
  Contents: Correctness of Kruskal and Prim's algorithm, continued. Union-find data structure
  Readings: Section 5.1
  Instructor: Trevisan
  Suggested Exercises:
  
• 2021-03-04: Greedy Algorithms III
  Contents: Continuation of previous lecture
  Readings: Section 5.1
  Instructor: Trevisan
  Suggested Exercises:
  
• 2021-03-05: Greedy Algorithms IV
  Contents: Prefix codes, Huffman coding
  Readings: Section 5.2, notes
  Instructor: Trevisan
  Suggested Exercises:
  
• 2021-03-09: Greedy Algorithms V
  Contents: Huffman coding, entropy, shortest paths in DAGs
  Readings: Section 5.2, 4.7
  Instructor: Trevisan
  Suggested Exercises:
  
• 2021-03-11: Dynamic Programming I (moved to 03-24)
  Contents: Shortest paths with negative weights. All-pairs shortest paths. Rethinking Dijkstra's algorithm
  Readings: Sections 6.1, 6.6
  Instructor: Trevisan
  Suggested Exercises:
  
• 2021-03-12: Lab II
  Contents: Discuss solutions to exercises and implementation of dynamic programming algorithms
  Readings: Notes
  Instructor: Iozzi
  Suggested Exercises:
  
• 2021-03-25: Dynamic Programming II
  Contents: Edit distance, knapsack
  Readings: Section 6.3, 6.4
  Instructor: Trevisan
  Suggested Exercises:
  
• 2021-03-26: Flows I
  Contents: Flows in networks, residual network, Ford-Fulkerson
  Readings: Section 7.2, notes
  Instructor: Trevisan
  Suggested Exercises:
  
• 2021-03-30: Flows II
  Contents: Max flow min cut theorem, analysis of Edmonds-Karp, reduction to other problems
  Readings: Notes, Section 7.3
  Instructor: Trevisan
  Suggested Exercises:
  
• 2021-04-01: Linear Programming I
  Contents: Introduction, geometry of solutions, weak duality
  Readings: Sections 7.1 and 7.4
  Instructor: Iozzi
  Suggested Exercises:
  
• 2021-04-02: Linear Programming II
  Contents: The simplex algorithm
  Readings: Section 7.6
  Instructor: Iozzi
  Suggested Exercises:
  
• 2021-04-13: Linear Progamming III
  Contents: Problems modelled by linear programming: flows, zero-sum games
  Readings: Sections 7.2 and 7.5
  Instructor: Iozzi
  Suggested Exercises:
  
• 2021-04-15: Lab III
  Contents: More on the simplex algorithm
  Readings: Notes
  Instructor: Iozzi
  Suggested Exercises:
  
• 2021-04-16: NP-completeness I
  Contents: Combinatorial explosion, search problems, P, NP, reductions, NP-completeness
  Readings: Section 8.1, notes
  Instructor: Trevisan
  Suggested Exercises:
  
• 2021-04-20: NP-completeness II
  Contents: NP-completeness of SAT, Independent Set, Clique
  Readings: Notes
  Instructor: Trevisan
  Suggested Exercises:
  
• 2021-04-22: NP-completeness III
  Contents: More NP-complete problems
  Readings: Notes
  Instructor: Trevisan
  Suggested Exercises:
  
• 2021-04-29: Lab IV
  Contents: Course review, review of practice problems, ask us anything
  Readings: Notes
  Instructor: Trevisan
  Suggested Exercises: