BBM 402 - Theory of Computation

BBM 402 - Theory of Computation, Fridays 9:40 - 12:20. (SH)

Instructor

Lale Özkahya

Office Hours:
Email to arrange an appointment.

All communication will be on https://piazza.com/hacettepe.edu.tr/spring2025/bbm402

Resources

Introduction to the Theory of Computation, by Michael Sipser.

Algorithm Design, by Jon Kleinberg and Eva Tardos.

Introduction to Automata Theory, Languages, and Computation, by John E. Hopfcroft, Rajeev Motwani, Jeffrey D. Ullman.

Margaret Fleck and Sariel Har-Peled's automata and formal languages notes, 2008 (available online)

Jeff Erickson's Algorithm Notes (available online)

Similar Courses

MIT Open Courseware: Automata, Computability, and Complexity

CS125: Algorithms and Complexity at Harvard Uni.

15-251: Great Theoretical Ideas in Computer Science at Carnegie Mellon Uni.

COS423: Theory of Algorithms at Princeton Uni.

CS170: Efficient Algorithms and Intractable Problems at EECS, Berkeley Uni.

CS374: Algorithms and Models of Computation at Uni. of Illinois

Grading (Tentative)

Attendance, 5%

Midterm Exam, 30%

Paper Presentation, 25%

Final Exam, 40%

Schedule

Week Slides/Notes Reading: MS, KT

1 Review of Asymptotic (big-Oh) Notation and Graphs [Slides:1, 2] Chapters 2-3 (KT)

2 Review of Deterministic Finite Automata [Slides:1, 2] Chapter 1.1,3 (MS)

3 Review of Nondeterministic Finite Automata [Slides:1, 2] Chapter 1.2 (MS)

4 Turing machines: history, formal definitions, examples: [Slides 1, 2] Chapter 3.1-2 (MS)

5 Undecidability: halting problem, diagonalization, reductions slides Chapter 4 (MS)

6 Polynomial time Reductions, NP-hardness: Definitions, examples, Cook-Levin Theorem [Slides 1, 2] Chapter 7.1-3 (MS), Chapter 8 (KT)

7 NP-hardness: 3SAT, Max Independent Set, Vertex cover, 3-Color, Hamiltonian cycle slides Chapter 7.4-5 (MS), Chapter 8 (KT)

8 Problem Session Chapter 8 (KT)

9 Midterm Exam

10 Approximation Algorithms [Slides] Chapter 11 (KT), 10.1 (MS)

11 Approximation Algorithms ('ctd),
Randomized Algorithms [Slides] Chapter 11 (KT), 10.1 (MS)
Chapter 13 (KT), 10.2 (MS)

12 Randomized Algorithms ('ctd) Chapter 13 (KT), 10.2 (MS)

13 Paper Presentations

14 Paper Presentations

© 2025 Hacettepe University

Week	Slides/Notes	Reading: MS, KT
1	Review of Asymptotic (big-Oh) Notation and Graphs [Slides:1, 2]	Chapters 2-3 (KT)
2	Review of Deterministic Finite Automata [Slides:1, 2]	Chapter 1.1,3 (MS)
3	Review of Nondeterministic Finite Automata [Slides:1, 2]	Chapter 1.2 (MS)
4	Turing machines: history, formal definitions, examples: [Slides 1, 2]	Chapter 3.1-2 (MS)
5	Undecidability: halting problem, diagonalization, reductions slides	Chapter 4 (MS)
6	Polynomial time Reductions, NP-hardness: Definitions, examples, Cook-Levin Theorem [Slides 1, 2]	Chapter 7.1-3 (MS), Chapter 8 (KT)
7	NP-hardness: 3SAT, Max Independent Set, Vertex cover, 3-Color, Hamiltonian cycle slides	Chapter 7.4-5 (MS), Chapter 8 (KT)
8	Problem Session	Chapter 8 (KT)
9	Midterm Exam
10	Approximation Algorithms [Slides]	Chapter 11 (KT), 10.1 (MS)
11	Approximation Algorithms ('ctd), Randomized Algorithms [Slides]	Chapter 11 (KT), 10.1 (MS) Chapter 13 (KT), 10.2 (MS)
12	Randomized Algorithms ('ctd)	Chapter 13 (KT), 10.2 (MS)
13	Paper Presentations
14	Paper Presentations