This course introduces the basic concepts underlying the theoretical study of computing and computers: formal languages, automata, Turing machines, computability, and computational complexity. Three lecture hours per week.
      Prerequisites: CSC 260, MAT 214.

• CG1: to present the concepts of finite automata, formal languages, computability, and computational complexity;
• CG2: to discuss the most important tools and techniques associated with these concepts;
• CG3: to explain the importance of these topics to Computer Science;
• CG4: to present these topics so as to promote understanding of the ideas; reproduction or construction of formal proofs plays a lesser role.

• CO1: define the concept of finite automaton and give computer-related examples;
• CO2: define the concept of a context-free grammar and give examples;
• CO3: define and give examples of regular expressions and regular languages;
• CO4: explain the conections between finite automata and regular expressions, with examples;
• CO5: explain the conection between comtext-free languages and pushdown automata;
• CO6: define and give examples of a Turing machine;
• CO7: explain the concept of undecidability;
• CO8: explain the concept of intractability and define the classes P and NP.

• review of background material:
  • sets, relations, functions, sequences
  • alphabets, strings, languages
  • proof methods
           mathematical induction, proof by contradiction, the technique of diagonalization
  • digraphs, tree diagrams
• formal languages and grammars
  • regular expressions and regular languages
  • deterministic context-free languages
  • context-free languages
  • context-sensitive languages
  • recursively enumerable languages
  • LL(k) and LR(k) grammars and languages
• finite automata:
  • deterministic (DFA)
  • nondeterministic (NDFA)
  • nondeterministic with empty moves (NDFAe)
  • the Pumping Lemma for regular languages
• pushdown automata
• Turing machines
• random access machines
• computability; the Church-Turing thesis
• the Halting Problem
• decidability
• parallel random access machines
• computational complexity:
  • simulations and reducibilities
  • circuits and circuit complexity
  • the complexity class NC
  • the complexity classes P and NP
  • P-completeness and NP-completeness

There will be a two-hour written final examination. There will also be one or more shorter tests.   Periodic written homework assignments will be given, including reports on assigned reading in books and journals. Oral presentations on selected topics may also be required.

Final grades will be determined using the following approximate weights: written assignments — 40%; tests and oral presentations — 30%; final examination — 30%.

• Beckman, Frank S.   Mathematical Foundations of Programming. Addison Wesley, 1981.
• Cohen, Daniel I. A.   Introduction to Computer Theory. Revised Edition. John Wiley, 1991.
• Greenlaw, Raymond; Hoover, H. James.   Fundamentals of the Theory of Computation: Principles and Practice. Morgan Kauffman, 1998.
• Gurari, Eitan M.   An Introduction to the Theory of Computation. Computer Science Press [W. H. Freeman], 1989.
• Hopcroft, John E.; Motwani, Rajeev; Ullman, Jeffrey D.   Introduction to Automata Theory, Languages, and Computation.   Second Edition. Addison Wesley, 2001.
• Kinber, Efim; Smith, Carl.   Theory of Computing.   A Gentle Introduction. Prentice Hall, 2001.
• Lewis, Harry R.; Papadimitriou, Christos H.   Elements of the Theory of Computation. Prentice Hall, 1981.
• Linz, Peter.   An Introduction to Formal Languages and Automata.   Third Edition.   Jones and Bartlett, 2001.
• Martin, John C.   Introduction to Languages and the Theory of Computation.   Second Edition.   WCB/McGraw Hill, 1997.
• Moret, Bernard M.   The Theory of Computation.   Addison Wesley, 1997.
• Sudkamp, Thomas A.   Languages and Machines: An Introduction to the Theory of Computer Science. (Addison-Wesley, 1988)
• Wood, Derick.   Theory of Computation. Harper & Row, 1987.