**Lectures**: Thursday 08:30PM - 09:20PM EST (remote)

**Instructors**: Venkatesan Guruswami (venkatg@cs.cmu.edu)

**Teaching Assistant:** Andrii Riazanov (riazanov@cs.cmu.edu)

**Office Hours**: Venkat: Friday 10:00AM EST, Andrii: Wednesday 9:30PM EST

**Piazza Link**: Here.

This 5-unit mini-course is intended for students who are taking 15-251 and would like more intensive exposure to theoretical computer science. The class meets once a week for a lecture and the students are expected to solve a number of homework problems during the course of the semester. The work done in 15-252 does not replace any of the requirements of 15-251.

Lecture topics and notes will appear here (the YouTube video links will be posted on Piazza). In the meanwhile, here is last year's page, which will give a pretty good idea of the topics we plan to cover.

- (Feb 4): Sorting Pancakes (Notes, Slides )
- (Feb 11): Nondeterministic finite automata (Lecture transcript)
- (Feb 18): Lambda Calculus (Video Part 1, Video Part 2, Slides, Frank Pfenning's notes )
- (Feb 25): Kolmogorov complexity (Lecture transcript, Lecture notes)

**General rules:** There will be a short homework assigned every week. The homeworks will usually go out on Fridays and be due by midnight the next Friday. They must be submitted via Gradescope. You can work alone or with one other person (the recommended option is the latter). However you must write the solutions completely by yourself. You may not share any written documents. Submissions of *legible* handwrittings is allowed, although LaTeXing is preferred.

- Problem Set 1, due Feb 12
- Problem Set 2, due Feb 19
- Problem Set 3, due Feb 26
- Problem Set 4, due March 5

Attendance and weekly assigned problems.