CS 208: Computing Theory: Spring, 2006/2007

Assoc. Prof. Dr. Brahim Hnich

Location/Time/Contact Information

• Software Engineering/Computer Engineering Group I:

Lecture Room C501; Lecture Times: Mondays 8:30—11:20 AM

• Software Engineering/Computer Engineering Group II:

Lecture Room C501; Lecture Times: Tuesdays 11:30—14: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 : 40% (16^th and 17^th of April, 2007)
• Final Exam: 60%

Programme

1. Part A: Preliminaries
1. Introduction
2. Mathematical Notations for Computations
2. Part B: Automata Theory
1. Finite State Automata (Deterministic, Nondeterministic, Regular Expressions)
2. Context Free Grammars
3. Part C: Computability Theory
1. Turing Machines
2. Decidability and Undecidability
4. Part D: Complexity Theory
1. Time Complexity
2. Intractability
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 and PushDown Automata

Part C

• Turing Machines
• Decidability and Undecidability

Part D

Part E