Instructor and Office Hours 
Lonnie Fairchild
Office: Redcay 147     (Enter through Computer Science Dept.)
Phone: 564-2783,         Computer Science Office: 564-2788
Email: lonnie.fairchild@plattsburgh.edu,          
Office hours:     Mon.  4:30 – 5:30         Tues.  1:30 – 2:30
                         Wed. 4:30 – 5:30         Thurs. 1:30 - 2:30
                         Fri.    9:30 - 10:30
These times will not be convenient for everyone. Students are welcome (and encouraged) to make appointments for other times.

Course Description    What kinds of computations is it possible to perform on a computer? The theory of computation provides a variety of ways of approaching this question. We will start out looking at abstract models of computation (different kinds of automata and languages) and show that different models represent different computational capabilities. We will next look at models, including the Turing machine, that seem to represent our general notion of algorithm and show that there are problems that cannot be solved by any algorithm. Finally, we will move from the question of what problems it is possible to solve on a computer to the question of what problems it is practical to solve and how we measure what is hard or easy.
        Prerequisite: CSC 318 (Discrete mathematics with Computer Science Applications II)   or   MAT 301 (Abstract algebra)

Required Text     Efim Kinber and Carl Smith, Theory of computing: A gentle Introduction, Prentice Hall, 2001

Grading The final course grade will be computed as follows:
            Quizzes                                                      25 %
            Hour tests (Sep. 23, Nov. 2)                      25 %
            Final exam                                                 15 %
            Assignments                                               30 %
            Class participation                                        5 %

Quizzes A short written quiz will be given during class every Tuesday (except 8/24, 9/28, 10/12, 11/2, and 11/30). Questions will come from the assigned readings, material discussed in the previous lectures, and the assignments recently completed.

Assignments    Homework exercises (generally done with pencil and paper) will be assigned almost every class and you will be asked to hand in a selection of these (in a clear and readable form) each Thursday.  

Attendance Policy and Academic Responsibility
    Because of the cumulative nature of the material in this course, students are required to attend all classes. Students who must miss a class due to unavoidable circumstances are expected to notify the instructor (email or phone) and to make up the work. The instructor is glad to help anyone who needs to make up work due to unavoidable emergencies (illness, etc.).
    All work submitted on tests and assignments is to be your own. Cooperative study and mutual aid are healthy learning methods and are strongly recommended. Plagiarism is copying someone's work or allowing someone else to copy or use your work, without giving credit. An assignment that shows evidence of plagiarism will result in a grade of 0, and the course grade will be lowered by one full letter grade. A second instance of plagiarism will result in a grade of E in the course.  

Topics covered ( dates to be supplied as the course progresses)

1. Background: review of sets and functions                                       [Chapter 1, in the text]

2. Finite automata                                                                                              [Chapter 2]
        Deterministic finite acceptors (DFAs) -- definitions and examples
        Nondeterministic finite automata (NFAs) -- definitions, examples, equivalence with DFAs
        Regular expressions and regular languages
        Nonregular languages
        Algorithms for finite automata 

3. Context-free languages                                                                                   [Ch. 3]
        Context-free grammars
        Parsing and ambiguity
        Deterministic and nondeterministic pushdown automata
        Equivalence of nondeterministic pushdown automata and context-free languages
        The pumping lemma and non-context-free languages
        Closure properties and decision problems for context-free languages
        Applications to programming languages

4. Turing machines                                                                                               [Ch. 4]
        Turing machine -- definitions, examples, equivalence of different models
        Nondeterministic Turing machines
        Turing enumerable languages

5.  Computability theory; unsolvable problems                                                       [Ch. 5]
        The Church-Turing thesis
        A universal Turing machine
        Undecidability of the halting problem
        Some other undecidable problems

9. Introduction to computational complexity                                                           [Ch. 6]
        Describing time complexity
        The classes P and NP
        NP-completeness
        Some NP-complete problems