CSE22BYear 2 · Quarter 2 · 5 ECcore — renamed

Theoretical Foundations of Computer Science

Formal languages and automata, computability, and complexity theory — finite automata through Turing machines to P vs. NP.

Download course · 124 MB

Lectures: 17
Exams: 9
Solutions: 8
Notes: 1
Textbooks: 1
Total: 43 · 124 MB

Renamed from CSE2315 Automata, Computability and Complexity; moved from Quarter 3 to Quarter 2. Same three pillars: formal languages, computability, complexity.

What it covers

Regular languages: DFAs, NFAs, subset construction, regular expressions (via GNFAs), the pumping lemma
Context-free languages: CFGs, PDAs, Chomsky Normal Form, the CFL pumping lemma
Computability: Turing machines, decidability, the Halting Problem, mapping reductions, Rice's theorem
Complexity: P, NP, NP-completeness, polynomial-time reductions (3SAT, CLIQUE, VERTEX-COVER)

Assessment

Written, closed-book exam worth 100% of the grade; one handwritten, double-sided A4 cheat sheet is allowed, nothing else. Weekly take-home lab assignments are optional and peer-corrected with TA feedback — they support the exam material but aren't separately graded.

Worth knowing

Grading follows the "Sipser method" strictly — a mathematically correct but non-Sipser procedure (e.g. from Hopcroft & Ullman) can lose points.
Flipped classroom: lectures assume you've already read the relevant Sipser sections beforehand; showing up unprepared makes them close to useless.
The pumping lemma proof structure (adversary picks length p, you pick string s, adversary splits it, you find the breaking i) is a recurring, heavily tested pattern.

AI tutors

Zip

TFoCS4 knowledge filesSystem prompt

Lectures · 17

Zip

Lecture 115 MB

Lecture 23 MB

Lecture 33 MB

Lecture 43 MB

Lecture 59 MB

Lecture 64 MB

Lecture 79 MB

Lecture 810 MB

Lecture 94 MB

Lecture 104 MB

Lecture 115 MB

Lecture 124 MB

Lecture 136 MB

Lecture 147 MB

Lecture 155 MB

Lecture 165 MB

Lecture 175 MB

Exams · 9

Zip

Written Endterm 2023Written Exams / Written Endterms446 KB

Written Endterm 2024Written Exams / Written Endterms315 KB

Written Endterm 2025Written Exams / Written Endterms373 KB

Written Midterm 2020Written Exams / Written Midterms287 KB

Written Midterm 2022Written Exams / Written Midterms261 KB

Written Resit 2022Written Exams / Written Resits354 KB

Written Resit 2023Written Exams / Written Resits343 KB

Written Resit 2024Written Exams / Written Resits386 KB

Written Resit 2025Written Exams / Written Resits400 KB

Solutions · 8

Zip

Lab Assignment 1 SolutionsLab Assignment Solutions236 KB

Lab Assignment 2 SolutionsLab Assignment Solutions276 KB

Lab Assignment 3 SolutionsLab Assignment Solutions315 KB

Lab Assignment 4 SolutionsLab Assignment Solutions282 KB

Lab Assignment 5 SolutionsLab Assignment Solutions245 KB

Lab Assignment 6 SolutionsLab Assignment Solutions283 KB

Lab Assignment 7 SolutionsLab Assignment Solutions295 KB

Lab Assignment 8 SolutionsLab Assignment Solutions332 KB

Notes · 1

Zip

Notes292 KB

Textbooks · 1

Zip

Introduction to the Theory of Computation10 MB

Reference · 1

Zip

Cheat Sheet6 MB

What it covers

Regular languages: DFAs, NFAs, subset construction, regular expressions (via GNFAs), the pumping lemma

Context-free languages: CFGs, PDAs, Chomsky Normal Form, the CFL pumping lemma

Computability: Turing machines, decidability, the Halting Problem, mapping reductions, Rice's theorem

Complexity: P, NP, NP-completeness, polynomial-time reductions (3SAT, CLIQUE, VERTEX-COVER)

Worth knowing

Grading follows the "Sipser method" strictly — a mathematically correct but non-Sipser procedure (e.g. from Hopcroft & Ullman) can lose points.

Flipped classroom: lectures assume you've already read the relevant Sipser sections beforehand; showing up unprepared makes them close to useless.

The pumping lemma proof structure (adversary picks length p, you pick string s, adversary splits it, you find the breaking i) is a recurring, heavily tested pattern.