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

Lectures:

Office hours: Thursdays 11-noon in 3-E1-14 Roetgen (from Sept 9 to Dec 5)


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


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 Section 2.2 and 2.3

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