Fall 2019 — 30516 Theoretical Computer Science
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. Time permitting, we will also get a glimpse into the design and analysis of cryptographic protocols. More information will provided about a week before the start of classes.
Instructor: Luca Trevisan
- Wednesdays 10:30-noon
- Thursdays 16:15-17:45
- Luca: Thursdays 11-noon in 3-E1-14 Roentgen (from Sept 12 to Dec 5)
- Niccolò: Tuesdays 10:30-12:30 in 3-E2-FN02 (until Dec 10)
Textbooks and other readings
There is no required textbook. Readings will be assigned for each lecture.
A good reference for the analysis of algorithms is
A great introduction to computational complexity is
- J Kleinberg and E Tardos. Algorithm Design
Another great and very readable reference for both analysis of algorithms and computational complexity is
- M Sipser. Introduction to the Theory of Computation
It is easy to find online a pdf of the Dasgupta et al. book. As far as I know, these pdf copies are circulating with the blessing of the authors.
- S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani. Algorithms
For the lectures on cryptography, we will refer to my notes
- Problem Set 1 (updated Oct 7) covers lectures 1-6
- Problem Set 2 covers lectures 7-12
- Problem Set 3 covers lectures 13-19
[Solutions (revised December 6, 2019)]
- Problem Set 4 covers lectures 20-21 (the exam will not have questions on cryptography)
[Solutions (revised December 6, 2019)]
- Description of the course. Big-Oh notation. Divide-and-conquer technique. Description of Mergesort and proof that it runs in O(nlogn) time
[Lecture Notes for Lecture 1]
Readings: review mathematical prerequisites and big-Oh notation, e.g. Dasgupta Chapter 0. Divide-and-conquer idea and mergesort, Dasgupta Sections 2.2 and 2.3
- Divide-and-conquer algorithm for multiplication of large integers. Statement and proof of the Master Theorem.
[Lecture Notes for Lecture 2]
Readings: Dasgupta Sections 2.1 and 2.2
- Randomized median algorithm with expected linear time. Definition of graphs, directed and undirected graphs, reachability, and connected components. Introduction to DFS. DFS as an algorithm for discovering the connected components of an undirected graph.
[Lecture Notes for Lecture 3 (updated October 7)]
Readings: Dasgupta Sections 2.4, 3.1 and 3.2
- Analysis of DFS for finding connected components of undirected graphs, DFS for finding topological sort of directed acyclic graphs, DFS for finding strongly connected components of directed graphs.
Readings: Dasgupta Sections 3.3 and 3.4
- Minimum spanning tree problem: Kruskal's algorithm and the union-find data structure.
Readings: Dasgupta Section 5.1 (you can skip the discussion of Prim's algorithm)
- More on minimum spanning trees and union-find.
Same readings as previous lecture
- Shortest path problem. Linear-time algorithm for DAGs. Dijkstra's algorithm and intuition for correctness.
Readings: Dasgupta Sections 4.3, 4.4 and 4.7
- Rigorous proof of correctness of Dijkstra's algorithm. Priority queue data structure and implementation using binary heaps.
Readings: Dasgupta Sections 4.4 and 4.5
- More on binary heaps implementation. Discussion of the shortest path problem if negative edge lengths are present.
Readings: Dasgupta 4.5 and 4.6
- Introduction to the maximum flow problem: definition of the problem, notion of residual network, definition of capacity of a cut, Ford-Fulkerson algorithm, statement of the Max Flow - Min Cut Theorem
Readings: Dasgupta 7.2, and chapter 9 of these notes
- Proof of correctness of Ford-Fulkerson and proof of max-flow min-cut theorem. Discussion of efficiency of Ford-Fulkerson implementation, and of the Edmonds-Karp algorithm.
Readings: same as last lecture and Section 11.2 of these notes
- Applications of maximum flow algorithms: maximum flow with vertex capacities, bipartite graphs, perfect matchings in bipartite graphs, maximum matching in bipartite graphs.
Readings: Dasgupta 7.3, and sections 14.1 and 14.2 of these notes
- Dynamic programming: Edit distance.
Readings: Dasgupta 6.3 (sections 6.1 and 6.2 give addtional context and examples)
- Dynamic programming: all-pairs shortest paths, Knapsack.
Readings: Dasgupta 6.4, 6.6
- Dynamic programming: time-bounded shortest paths and TSP.
Readings: Notes for lecture 15
- P, NP and NP completeness.
Readings: Dasgupta 8.1 and 8.2, Notes for lecture 16
- Reductions from 3SAT to Independent Set, Vertex Cover, and Subset Sum.
Readings: Notes for lecture 17 and see also Dasgupta 8.3 (some of the
reductions are different)
- Reduction from Vertex Cover to Subset Sum, continued, reduction from Vertex Cover to
Hamiltonian cycle, reduction from Hamiltonian cycle to TSP.
Readings: Garey and Johnson section 3.1.4 (posted on bboard) and Dasgupta 8.3
- NP-completeness of Circuit-SAT and 3SAT.
Readings: Notes for lecture 18 and Dasgupta 8.3. There are additional details in Section 7.4 of Sipser.
- Definitions of decidable and recognizable decision problems, undecidability of the Halting problem.
Readings: Sections 8.1, 8.2, 8.3 of Barak. Alternatively, Chapter 4 in Sipser
- Reductions between undecidable problems, Godel's theorem using undecidability of the Halting problem.
Readings: Sections 8.4, 10.1 and 10.2 of Barak. Alternatively, Chapter 5 and Section 6.2 of Sipser (which has a more advanced treatment).
- Cryptography: encryption and authentication in the symmetric key and the public key setting. The notion of a pseudorandom permutation. ECB and CBC modes of encryption using a pseudorandom permutation.
Readings: Chapter 1 and Chapter 5 of my lecture notes on cryptography (you can skip the description of AES)
- Message authentication in the symmetric key setting.
Readings: Chapter 6 of my lecture notes on cryptography
- Review, AMA
(May change slightly as the semester progresses)
- Introduction, review of basic data structures and of asymptotic analysis. Sorting in quadratic and O(n log n) time
- Multiplication of large integers in less than quadratic time. General divide-and-conquer methodology, master theorem
- Basic graph algorithms 1
- Basic graph algorithms 2
- Basic graph algorithms 3
- Basic graph algorithms 4
- Basic graph algorithms 5
- Basic graph algorithms 6
- Basic graph algorithms 7
- Maximum flow 1
- Maximum flow 2
- Dynamic programming 1
- Dynamic programming 2
- Dynamic programming 3
- P and NP
- Reductions and NP-completeness
- NP-complete problems
- NP-complete problems
- Undecidability of the Halting problem
- More undecidable problems
- Godel's theorem
- Cryptography 1
- Cryptography 2
- Cryptography 3