CS 208: Computing Theory: Spring, 2008/2009

Assoc. Prof. Dr. Brahim Hnich

Location/Time/Contact Information

• Computer Engineering Group:

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

• Software Engineering Group:

Lecture Room M202; Lecture Times: Wednesdays 13:30—16:20 PM

Room 415

Email: brahim.hnich@ieu.edu.tr

Office Hours: Tuesdays 13:00--15:00

Description:

The Computing Theory course provides a study of formal languages and the theory of automata with an emphasis on Church’s thesis and the “algorithm=machine” point of view. The following topics will be included: regular expressions and context-free languages, finite and pushdown automata, Turing machines, computability, undecidability, and complexity of problems.

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:

• 6 Homeworks: 30%
• Midterm Exam: 30%
1. Tuesday’s Section: April 21^st
2. Wednesday’s Section: April 22^nd
• Final Exam: 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

Homeworks

If you have any question about homework, you may either contact me or send an email to Ozgur at ozgurakgun @ gmail.com who is preparing the homeworks and the solutions.

• Homework 1: download here.
• Due Date for Homework 1: March 24^th for Tuesday’s section and March 25^th for the Wednesday’s section.
• Solution for Homework 1: download here.

• Homework 2: download here.
• Due Date for Homework 1: April 7^th for Tuesday’s section and April 8^th for the Wednesday’s section.
• Solution for Homework 2: download here.
• Homework 3&4: download here.
• Due Date: for Tuesday’s section April 21^st and April 22^nd for Wednesday’s section
• Solution for Homework 3&4: download here.
• Homework 5: download here.
• Due Date: for Tuesday’s section May 12th and May 13th for Wednesday’s section
• Solution for Homework 5: download here.
• Homework 6: download here.
• Due Date: Last day of lecture
• Solution for Homework 6: download here

Resources

JFLAP is software for experimenting with formal languages topics including nondeterministic finite automata, nondeterministic pushdown automata, multi-tape Turing machines, several types of grammars, parsing, and L-systems.

JFLAP website: http://www.jflap.org

Challenges

• Design a DFA accepting all strings over the alphabet {0,1} such that the number of 0’s is divisible by five, and the number of 1’s divisible by 3.
• Design a DFA accepting all strings over the alphabet {0,1} beginning with a 1 that, when interpreted as a binary integer, is a multiple of 5. For example, strings 101, 1010, and 1111 are accepted whereas strings 0, 100, and 111 are rejected.