Spring 2023 — 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 assistant: Lucas Pesenti
Lectures:
 Tuesdays 14:0016:30
 Thursdays 8:3010:00
 Fridays 14:0016: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
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

20230207: Introduction
Contents: Preview of some highlights. Mathematical
preliminaries: proving things by induction, bounding summations, bigOh
and littleoh notations, basics of probability
Readings: Chapter 0
Instructor: Iozzi
Suggested Exercises:

20230209: Divideandconquer I
Contents: Integer multiplication in O(n^{log_2 3}) time, Master Theorem
Readings: Sections 2.1 and 2.3
Instructor: Iozzi
Suggested Exercises:

20230210: Divideandconquer II
Contents: Analysis of mergesort, Median in linear time
Readings: Sections 2.2 and 2.4
Instructor: Iozzi
Suggested Exercises:

20230214: 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:

20230215, 12:0013:30: Graph Decomposition II
Contents: DFS in directed graphs
Readings: Section 3.3
Instructor: Iozzi
Suggested Exercises:

20230216: Graph Decomposition III
Contents: Linearization, DFS finds linearization
Readings: Section 3.3 and Notes on topological sort
Instructor: Iozzi
Suggested Exercises:

20230217: 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)

20230221: Shortest Paths I
Contents: BFS and shortest paths in unweighted graphs
Readings: Sections 4.1 and 4.2
Instructor: Trevisan
Suggested Exercises:

20230223: 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:

20230224: Shortest Paths III
Contents: Dijkstra's algorithm
Readings: Sections 4.3 and 4.4, notes
Instructor: Trevisan
Suggested Exercises:

20230228: Greedy Algorithms I
Contents: Minimum spanning tree problem, Kruskal and Prim's algorithm, proofs of correctness
Readings: Section 5.1
Instructor: Trevisan
Suggested Exercises:

20230303: Greedy Algorithms II
Contents: Correctness of Kruskal and Prim's algorithm, continued. Unionfind data structure
Readings: Section 5.1
Instructor: Trevisan
Suggested Exercises:
 HOMEWORK 2 (turn in on Tue Mar 7 in class)

20230307: Greedy Algorithms III
Contents: Prefix codes, Huffman coding
Readings: Section 5.2, notes
Instructor: Trevisan
Suggested Exercises:

20230310: Greedy Algorithms IV
Contents: More on data compression, entropy; set cover
Readings: Section 5.2, 5.4notes
Instructor: Trevisan
Suggested Exercises:
 MIDTERM

20230323: Dynamic Programming I
Contents: Shortest paths in DAGs, shortest paths with negative weights
Readings: Section 6.1
Instructor: Trevisan
Suggested Exercises:

20230324: Dynamic Programming II
Contents: Shortest paths with negative weights. Allpairs shortest paths. Rethinking Dijkstra's algorithm
Readings: Sections 6.1, 6.6
Instructor: Trevisan
Suggested Exercises:

20230328: Dynamic Programming III
Contents: Edit distance, knapsack
Readings: Section 6.3, 6.4
Instructor: Trevisan
Suggested Exercises:

20230404: Flows I
Contents: Flows in networks, residual network, FordFulkerson, Max flow min cut theorem, analysis of EdmondsKarp
Readings: Section 7.2, notes
Instructor: Trevisan
Suggested Exercises:

20230407: 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)

20230418: Linear Programming I
Contents: Introduction, geometry of solutions, weak duality
Readings: Sections 7.1 and 7.4
Instructor: Iozzi
Suggested Exercises:

20230420: Linear Programming II
Contents: The simplex algorithm
Readings: Section 7.6
Instructor: Iozzi
Suggested Exercises:

20230421: Linear Progamming III
Contents: Problems modelled by linear programming: flows, zerosum games
Readings: Sections 7.2 and 7.5
Instructor: Iozzi
Suggested Exercises:

20230427: Linear Programming IV
Contents: Game Theory
Readings: Section 7.5
Instructor: Iozzi
Suggested Exercises:

20230428: NPcompleteness I
Contents: Combinatorial explosion, search problems, P, NP, reductions, NPcompleteness
Readings: Section 8.1, notes
Instructor: Trevisan
Suggested Exercises:

20230502: NPcompleteness II
Contents: NPcompleteness of Independent Set and Subset Sum
Readings: Sections 8.2 and 8.3, notes
Instructor: Trevisan
Suggested Exercises:

20230505: NPcompleteness III
Contents: NPcompleteness of Set Cover, Partition, Bin Packing, Scheduling, Hamiltonian Circuit, TSP
Readings: Section 8.3, notes, and reduction to Hamiltonian Circuit
Instructor: Trevisan
Suggested Exercises:
20230509: NPcompleteness IV
Contents: Boolean circuits, and NPcompleteness of Circuits SAT and 3SAT
Readings: notes
Instructor: Trevisan
Suggested Exercises:

20230512: Final review
Contents: Whole syllabus review, all questions answered
Readings: Notes
Instructor: Trevisan
Suggested Exercises: