CSci 301 Syllabus

Course Objectives

Give a solid foundation in the theory of computation.
Establish the relevance of computation theory to software development.
Ensure a fair and accurate measurement of student performance.

Course Text

The text book for this course is Introduction to the Theory of Computation, by Michael Sipser. Additional materials will be available via the Web or handed out in class.

Students are expected to have read the assigned chapters before the indicated class session.

Schedule

Lectures and events will follow this weekly schedule:

Week  Tuesday                          Thursday

0                                      Sep 3: 0 Introduction

1     Sep 8: 1.1 Finite Automata       Sep 10: 1.2 Nondeterminism

2     Sep 14: 1.3 Regular Expressions  Sep 17: 1.4 Nonregular Languages

3     Sep 22: 2.1 Context-free         Sep 24: 2.2 Pushdown Automata
                  Grammars
      
4     Sep 29: 2.3 Non-context-free     Oct 1: 3.1 Turing Machines
                  Languages

5     Oct 6: 3.2 Variants of Turing    Oct 8: 3.3 Definition of Algorithm
                 Machines

6     Oct 13: 4.1 Decidable Languages  Oct 15: 4.2 Halting Problem
 
7     Oct 20: 5.1 Undecidable          Oct 22: First Mid-term Exam
                  Problems                     (ch 1-3)

8     Oct 27: 5.2 A Simple             Oct 29: 5.3 Mapping Reducibility
                  Undecidable Problem
                  
9     Nov 3: 6.1 Recursion Theorem     Nov 5: 6.2 Decidability of Logical
                                                  Theories

10    Nov 10: 6.3 Turing Reducibility  Nov 12: 6.4 Definition of Information

11    Nov 17: 7.1 Measuring            Nov 19: Second Mid-term Exam
                  Complexity                   (ch 4-6)

12    Nov 24: 7.2 The class P          Nov 26: Thanksgiving Recess

13    Dec 1: 7.3 The class NP          Dec 3: 7.4 NP-completeness

14    Dec 8: 7.5 Additional            Dec 10: Review
                 NP-complete
                 Problems

15    December 15: Final examination
                   4:30 to 6:30 PM

Email: Richard dot J dot Wagner at gmail dot com