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.

General information

Instructor: Luca Trevisan


Office hours:

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 Another great and very readable reference for both analysis of algorithms and computational complexity is 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.

For the lectures on cryptography, we will refer to my notes


  1. Problem Set 1 (updated Oct 7) covers lectures 1-6
  2. Problem Set 2 covers lectures 7-12
  3. Problem Set 3 covers lectures 13-19
    [Solutions (revised December 6, 2019)]
  4. Problem Set 4 covers lectures 20-21 (the exam will not have questions on cryptography) [Solutions (revised December 6, 2019)]

Past lectures

  1. 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
  2. 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
  3. 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
  4. 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
  5. 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)
  6. More on minimum spanning trees and union-find.
    Same readings as previous lecture
  7. 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
  8. 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
  9. More on binary heaps implementation. Discussion of the shortest path problem if negative edge lengths are present.
    Readings: Dasgupta 4.5 and 4.6
  10. 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
  11. 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
  12. 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
  13. Dynamic programming: Edit distance.
    Readings: Dasgupta 6.3 (sections 6.1 and 6.2 give addtional context and examples)
  14. Dynamic programming: all-pairs shortest paths, Knapsack.
    Readings: Dasgupta 6.4, 6.6
  15. Dynamic programming: time-bounded shortest paths and TSP.
    Readings: Notes for lecture 15
  16. P, NP and NP completeness.
    Readings: Dasgupta 8.1 and 8.2, Notes for lecture 16
  17. 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)
  18. 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
  19. 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.

  20. 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
  21. 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).
  22. 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)
  23. Message authentication in the symmetric key setting.
    Readings: Chapter 6 of my lecture notes on cryptography
  24. Review, AMA

Lecture plan

(May change slightly as the semester progresses)

  1. Introduction, review of basic data structures and of asymptotic analysis. Sorting in quadratic and O(n log n) time
  2. Multiplication of large integers in less than quadratic time. General divide-and-conquer methodology, master theorem
  3. Basic graph algorithms 1
  4. Basic graph algorithms 2
  5. Basic graph algorithms 3
  6. Basic graph algorithms 4
  7. Basic graph algorithms 5
  8. Basic graph algorithms 6
  9. Basic graph algorithms 7
  10. Maximum flow 1
  11. Maximum flow 2
  12. Dynamic programming 1
  13. Dynamic programming 2
  14. Dynamic programming 3
  15. P and NP
  16. Reductions and NP-completeness
  17. NP-complete problems
  18. NP-complete problems
  19. Undecidability of the Halting problem
  20. More undecidable problems
  21. Godel's theorem
  22. Cryptography 1
  23. Cryptography 2
  24. Cryptography 3