This is a core undergraduate Computer Science course on the theory of computing. The course introduces the foundations of computer computer science including questions such as “what is computation”, “what are the mathematical models of computing machines”, “what is a computable problem”, and “what is efficiently computable”. The course covers these questions and in the process introduces important concepts such as Turing machines, formal languages, models of automata, and an introduction to complexity theory. This is a theoretical course and requires rigorous mathematical analysis, including deriving formal proofs, which will help you develop your on mathematical abstraction and problem solving skills. The lecture, and some lab sessions, will consist of in-class activities and students will be required to work in groups.

Announcements

  • This website is permanently under construction - all content subject to change!

Class Resources

Tentative Schedule

Introduction Materials
Week 1-Lecture 0 Lecture 0 – Course Introduction
Finite State Automata and Pushdown Automata (Weeks 1-6) Materials
Deterministic Finite Automata (Week 1)
Chapter 1.1 (Sipser)
Chapter 2 (Linz)
Lecture 1 – Finite Automata
Lecture 2 – Building DFAs
Quiz 1
Review of Proof Techniques
Nondeterministic Finite Automata (Week 2)

Lecture 3 – Regular Languages and Nondeterminism
Lecture 4 – NFA==DFA
Lab 1
Quiz 2
Regular Expressions and Non-regular Languages (Week 3)

Lecture 5 – NFAs and Regular Expressions
Lecture 6 – Regular Language Pumping Lemma
Lab 2
Quiz 3
Non-regular Languages and Pushdown Automata (Week 4)

Lecture 7 – Proving Languages Not Regular
Lecture 8 – PDAs
Hackathon
Lab 3
Context-Free Grammars and Equivalence to PDAs (Week 5)

Lecture 9 – Context Free Grammars
Lecture 10 – CFG=PDA
Lab 4

Exam 1 (Week 6) Feb. 20
All material on finite automata
Lecture 11 – Exam review
Computability Theory (Weeks 7-10) Materials
Turing Machines (Week 7)

Lecture 12 – Turing Machines
Lecture 13 – More Turing Machines
Lab 5
Quiz 4
Decidable and Turing-recognizable Languages (Week 8)

Lecture 14 – Decidable and Turing Recognizable Languages
Lecture 15 – An Undecidable Language
Lab 6
Reductions (Week 9)

Lecture 16 – Proofs by Reduction
Lecture 17 – Reductions and Kolmogorov Complexity
Lab 7
Exam 2 (Week 10) Mar. 27 All material on Turing machines and computability
Lecture 18 – Exam review
Complexity Theory (Weeks 11-14) Materials
P and NP (Week 11)

Lecture 19 – P
NP Completeness (Week 12)

 
Complexity Classes and Interactive Proofs (Week 13)

 
Zero-Knowledge Proofs and Review (Week 14)

 
Summary Materials
Final Exam TBD Comprehensive but will focus primarily on material after Exam 2.

Office Hours:

Monday Tuesday Wednesday Thursday Friday
2:10-3:10 – Freya 10:00-11:00 – Arkady
1:30-3:30 – Freya
5:00-6:00 – Jie
3:30-5:00 – Ozzy
5:00-6:00 – Jie
6:00-8:00 – Suvasree
1:00-3:00 – Laura
5:00-6:00 – Ozzy
10:30-12:00 – Ozzy
12:00-1:00 – Arkady

All office hours will be held in the common area on the 4th floor of SEH.