CS 208: Computing Theory: Spring, 2005/2006

Assoc. Prof. Dr. Brahim Hnich

Location/Time/Contact Information

• Software Engineering Group:

Lecture Room M204; Lecture Times: Tuesdays 8:30—11:20 AM

• Computer Science Group:

Lecture Room M203; Lecture Times: Fridays 14:30—17:20 PM

Room 415

Email: brahim.hnich@ieu.edu.tr

Textbooks:

• Harry R. Lewis and C.H. Papadimitriou. "Elements of the Theory of Computation", ISBN 0-13-272741-2, Prentice Hall. (Reference Book)
• Michael Sipser. "Introduction to the Theory of Computation", ISBN 053494728X, PWS Publishing Company.
• Michael R. Garey and David S. Johnson. “Computer and Intractability", ISBN 0-7167-1045-5, W.H. Freeman and Company.
• C.H. Papadimitriou. “Computational Complexity", ISBN 0-201-53082-1, Addison-Wesley Publishing Company, Inc.

Exams and Grading:

• Midterm Exam I (week 6): 30%
• Midterm Exam II (week 11): 30%
• Final Exam (week 16/17): 40%

Programme

1. Part A: Preliminaries
1. Introduction
2. Mathematical Notations for Computations
2. Part B: Automata Theory
1. Finite State Automata
2. Context Free Grammars
3. Part C: Computability Theory
1. Turing Machines
2. Decidability and Undecidability
3. Reducibility
4. Part D: Complexity Theory
1. Time Complexity
2. Intractability
3. Space complexity
5. Part E: Summary and Concluding Remarks

Lecture Notes

Part A

Part B

• Deterministic Finite Automaton
• Non-deterministic Finite Automaton
• Regular Expressions
• Context-Free Languages

Part C

• Turing Machines
• Decidability and Undecidability
• Reducibility(No slides)

Part D

Part E