Ph.D. Program in Computer Science
City University of New York - Graduate School and University Center

CSc 75010 - Theoretical Computer Science
3 credits
Code: 96156
Instructor: Noson Yanofsky
Tuesdays, 9:30 - 11:30 am
Room tba
 

Professor Noson Yanofsky
Homepage

Required Text: Computability, Complexity and Languages: Fundamentals of Theoretical Computer Science 2nd Ed. By Martin D. Davis, Ron Sigel and Elaine Weyuker Recommended Texts: Introduction to the Theory of Computation by Michael Sipser Introduction to Automata Theory, Languages, and Computation 2nd Ed. by John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman. All books will be on reserve in the GC library.    Week Chapter Chapter Title Sections Skipped 1 2   Programs and Computable Functions   2 3 Primitive Recursive   3 Functions 4 4   A Universal Section 9 5 Program 6 6   Turing   7 Machines 8 Midterm     9 8   Classifying Section 5-9 10 Unsolvable Problems 11 12   Propositional Calculus Section 5,7 12 15   Polynomial-Time Computability   13 Basic Complexity Theory 14  Grade:  Midterm: 45%                 H.W.:   10%                  Final:   45%  There will be homework every single week. You must hand in the H.W. at the beginning of the next class. The midterm and final questions will be similar to the H.W. questions.