BBM 402 - Theory of Computation

BBM 402 - Theory of Computation, Mondays 12:40 - 15:30. (D10)

Instructor

Lale Özkahya

Office Hours:
Email to arrange an appointment.

All communication will be on https://piazza.com/hacettepe.edu.tr/spring2024/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)

Problem Solving, 30%

Midterm Exam, 30%

Final Exam, 40%

Schedule

Week Slides/Notes Reading: MS, KT

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

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

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

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

5 Polynomial time Reductions slides Chapter 7.1-2 (MS), Chapter 8 (KT)

6 NP-hardness: Definitions, examples, Cook-Levin Theorem slides Chapter 7.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 I Chapter 8 (KT)

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

10 Midterm Exam

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 Problem Session II Chapter 11 (KT)

14 Problem Session III Chapter 13 (KT)

© 2024 Hacettepe University

Week	Slides/Notes	Reading: MS, KT
1	Review of Deterministic Finite Automata [Slides:1, 2]	Chapter 1.1,3 (MS)
2	Review of Nondeterministic Finite Automata [Slides:1, 2]	Chapter 1.2 (MS)
3	Turing machines: history, formal definitions, examples: Slides 1, 2	Chapter 3.1-2 (MS)
4	Undecidability: halting problem, diagonalization, reductions slides	Chapter 4 (MS)
5	Polynomial time Reductions slides	Chapter 7.1-2 (MS), Chapter 8 (KT)
6	NP-hardness: Definitions, examples, Cook-Levin Theorem slides	Chapter 7.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 I	Chapter 8 (KT)
9	Approximation Algorithms [Slides]	Chapter 11 (KT), 10.1 (MS)
10	Midterm Exam
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	Problem Session II	Chapter 11 (KT)
14	Problem Session III	Chapter 13 (KT)