| CSE 30151 | Theory of Computing | (3-0-3) |
| | The theory of automata and formal language is developed along with applications. Various classes of automata, formal languages, and the relations between these classes are studied. Restricted models of computation: finite automata and pushdown automata; grammars and their relations to automata; parsing; Turing machines; limits of computation; undecidable problems, the classes of P and NP. |
| | |
| Text: |
| References: |
H.R. Lewis & C.H. Papadimitriou, Elements of the Theory of Computation, 2nd, Prentice-Hall, , 1998, |
| |
M. Sipser, Introduction to the Theory of Computation, , PWS Publishing Co., , 1997, |
| |
J. E. Hopcroft, R. Motwani and J. D. Ullman, Introduction to Automata Theory, Languages and Computation, 2nd, Addison-Wesley, , 2001, |
| |
| Faculty-in-Charge: |
Amitabh Chaudhary |
| |
| Course Goals: | Develop the fundamental theory of automata, Turing machines and formal languages, and to understand the power and limits of different computational models. |
| Prerequisites: | CSE 20110, CSE 20232 and CSE 30331 |
| Co-requisites: | |
| | |
| Topics: | | Number of Lectures |
| |
Introduction | 2 |
| |
Regular Languages & Finite Automata | 7 |
| |
Context-free grammars | 5 |
| |
Pushdown Automata | 5 |
| |
Turing Machines | 9 |
| |
Undecidable problems | 5 |
| |
The Classes P & NP | 5 |
| |
NP Completeness | 5 |
| | |
| Course Content: |
| | Engineering Science |
3.0 |
| | Engineering Design |
0.0 |
| Course Grading: |
| | Final exam |
30 |
| | Assignments |
35 |
| | Participation |
5 |
| | Midterm exams |
30 |
| | |
| | |
| Computer Usage: | Some homework and a project may require a programming in a high-level language. |
| Laboratory Usage: | None |
| Special Consideration: | |