Spring 2021 — 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
Lectures:
 Tuesdays 14:0016:30 Room N20
 Thursdays 8:3010:00 Room N11
 Fridays 14:0016:30 Room N06
Office hours:
 Luca Trevisan: Thursdays 15:0016:00 (appointment required)
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

20210204: 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, bigOh and littleoh notations, basic probability
Readings: Chapter 0
Instructor: Iozzi
Suggested Exercises:

20210205: Divideandconquer 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:

20210209: Divideandconquer II
Contents: Median in linear time, Master Theorem
Readings: Sections 2.2 and 2.4
Instructor: Iozzi
Suggested Exercises:

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

20210212: Graph Decomposition II
Contents: Directed acyclic graphs, linearization, DFS finds linearization
Readings: Section 3.3 and Notes on topological sort
Instructor: Trevisan
Suggested Exercises:

20210216: Graph Decomposition III
Contents: Finding strongly connected components by running two DFSs
Readings: Section 3.4
Instructor: Trevisan
Suggested Exercises:

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

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

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

20210225: Lab I
Contents: Discuss solutions to exercises
Readings: Notes
Instructor: Iozzi
Suggested Exercises:

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

20210302: Greedy Algorithms II
Contents: Correctness of Kruskal and Prim's algorithm, continued. Unionfind data structure
Readings: Section 5.1
Instructor: Trevisan
Suggested Exercises:

20210304: Greedy Algorithms III
Contents: Continuation of previous lecture
Readings: Section 5.1
Instructor: Trevisan
Suggested Exercises:

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

20210309: Greedy Algorithms V
Contents: Huffman coding, entropy, shortest paths in DAGs
Readings: Section 5.2, 4.7
Instructor: Trevisan
Suggested Exercises:

20210311: Dynamic Programming I (moved to 0324)
Contents: Shortest paths with negative weights. Allpairs shortest paths. Rethinking Dijkstra's algorithm
Readings: Sections 6.1, 6.6
Instructor: Trevisan
Suggested Exercises:

20210312: Lab II
Contents: Discuss solutions to exercises and implementation of dynamic programming algorithms
Readings: Notes
Instructor: Iozzi
Suggested Exercises:

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

20210326: Flows I
Contents: Flows in networks, residual network, FordFulkerson
Readings: Section 7.2, notes
Instructor: Trevisan
Suggested Exercises:

20210330: Flows II
Contents: Max flow min cut theorem, analysis of EdmondsKarp, reduction to other problems
Readings: Notes, Section 7.3
Instructor: Trevisan
Suggested Exercises:

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

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

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

20210415: Lab III
Contents: More on the simplex algorithm
Readings: Notes
Instructor: Iozzi
Suggested Exercises:

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

20210420: NPcompleteness II
Contents: NPcompleteness of SAT, Independent Set, Clique
Readings: Notes
Instructor: Trevisan
Suggested Exercises:

20210422: NPcompleteness III
Contents: More NPcomplete problems
Readings: Notes
Instructor: Trevisan
Suggested Exercises:

20210429: Lab IV
Contents: Course review, review of practice problems, ask us anything
Readings: Notes
Instructor: Trevisan
Suggested Exercises: