CSC 304 - Syllabus

The City College of New York • Grove School of Engineering • Computer Science Department • Course Syllabus

Course number

CSc 30400

Course name

Theoretical Computer Science

Credits & hours

3 cr., 3 hr.

Course coordinator

Prof. Stephen Lucci

 

Textbook, title, author, and year

  • One of Introduction to the Theory of Computation, 3rd Ed, Michael Sipser, 2012, Elements of the Theory of Computation 2nd Ed, Lewis and Papadimitriou, 2007, and Introduction to Automata Theory, Languages and Computation 3rd Ed, Hopcroft and Motwani, 2006
  • Other supplemental materials: additional matierials provided in class

Specific course information

  • Finite state automata, pushdown automata, Turing Machines, and the languages they can recognize. Church's Thesis. Computability. The classes P and NP; NP-complete problems and intractable problems.
  • Prereq.: CSc 10400 and CSc 22000
  • Required course

Specific goals for the course and Relationship to student outcomes

 

1

2

3

4

5

6

a. the student acquires knowledge of finite automata, pushdown automata and Turing machines

P

     

b. the student acquires an understanding of regular, context free and recursive languages

P

     

c. the student acquires knowledge of Church's Thesis and Unsolvability

P

     

d. the student acquires knowledge of P and NP, of NP complete problems and intractable problems

P

     

I - introductory-level; R - reinforced-level; P - program-level

Brief list of topics to be covered

Seq.

Topics

1

Mathematical notions and terminology - brief review

2

Types of proofs

3

Regular languages - finite automata, nondeterminism, regular expressions, non-regular languages (pumping lemma)

4

Context-free languages - context-free grammars (including ambiguity and Chomsky normal form), pushdown automata, non-context-free languages (pumping lemma)

5

Computability theory - Turing machines (including the Church-Turing thesis)

6

Decidability - decidable languages, undecidability (diagonalization)

7

Complexity theory - reducibility, P, NP, NP-completeness (several examples, including the vertex cover, Hamiltonian path, and subset sum problems

8

Cook-Levin theorem usually remains just beyond the reach of the semester