Fall 2019 — 30516 Theoretical Computer Science

General information

Lectures:

• Wednesdays 10:30-noon
• Thursdays 16:15-17:45

Office hours:

• 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

A good reference for the analysis of algorithms is

• J Kleinberg and E Tardos. Algorithm Design

• M Sipser. Introduction to the Theory of Computation

• S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani. Algorithms

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

Exercises

1. Problem Set 1 (updated Oct 7) covers lectures 1-6
   [Solutions]
2. Problem Set 2 covers lectures 7-12
   [Solutions]
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

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