CSc 30400 Introduction to Theoretical Computer Science

Fall 2008

Syllabus

• Descrete Math Background
• Chapter 0
• Automata and Formal Grammars and Languages
• Chapter 1 (FA - Regular Grammars, Languages and Expressions)
• Chapter 2 (PDA - CF Grammars and Languages)
• Computability Theory
• Chapter 3 (TM - General Grammars and Lanuages, Chomsky Hierarchy, Turing - Church Thesis)
• Chapter 4 (Decidable Problems - Halting Problem - Diagonalization)
• Complexity Theory
• Chapter 7 (O-notation, Time Complexity, P & NP classes, reductions and NP-completeness)