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

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

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

- J Kleinberg and E Tardos.
*Algorithm Design*

A great introduction to computational complexity is
- M Sipser.
*Introduction to the Theory of Computation*

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

- 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)

- 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