CS-581: Theory of Computation

Syllabus - Fall 2012

Course Reference Number:
CS-581, Fall 2012: 11069 (section 003, 3 credits)
Grades so far: PDF of scores
Grades so far: PDF of bar chart
Lecture slides - Syllabus & Chapter 0 - Introduction (pdf) (jpeg files)
Lecture slides - Chapter 1 - Regular Languages (pdf) (jpeg files)
Lecture slides - Chapter 2 - Context-Free Languages (pdf) (jpeg files)
Lecture slides - Chapter 3 - The Church-Turing Thesis (pdf) (jpeg files)
Lecture slides - Chapter 4 - Decidability (pdf) (jpeg files)
Lecture slides - Chapter 5 - Reducibility (pdf) (jpeg files)
Lecture slides - Chapter 6.1 - The Recursion Theorem (pdf) (jpeg files)
Lecture slides - Chapter 6.2 - Decidability of Logical Theories (pdf) (jpeg files)
Lecture slides - Chapter 7 - Time Complexity (pdf) (jpeg files)

Instructor: Professor Harry Porter
E-Mail: harry@cs.pdx.edu
Web Page: www.cs.pdx.edu/~harry
Short Bio: Click Here
Office space at PSU: Fourth Ave Bldg, room 115-06 (click here for map)
Office hours: Tuesday, Thursday, 4:00-5:00 PM, and by appointment

When and Where:
Tuesday, Thursday, 2:00 - 3:50 PM
Fourth Avenue Building, room 40-06
First Class: Tuesday, September 25, 2012
Holiday: Thanksgiving, Thursday, November 22, 2012
Mid-Term Exam #1: Tuesday, Month xxx, 2012 (date is tentative)
Mid-Term Exam #2: Thursday, Month xxx, 2012 (date is tentative)
Final Exam Time: Monday, December 3, 2012, 10:15AM - 12:05PM

Homework:
HW #1
HW #2
HW #3
HW #4
HW #5
HW #6

Catalog Description:
Computability theory: study of models of computation (Turing, Church, Kleene), recursive function theory, properties of recursive, and recursively innumerable sets. Prerequisite: CS 311

Topics to be covered (tentative):

Regular Languages
Finite State Machines
Regular Expressions
Nondeterministic Machines
Pumping Lemma for Regular Languages
Context-Free Languages and Grammars
Pushdown Automata
Pumping Lemma for Context-Free Languages
Turing Machines
The Church-Turing Thesis
Decidability and Turing Recognizability
The Halting Problem
Reducibility
The Recursion Theorem
Decidability of Logical Theories
Time Complexity
The Classes P and NP
NP-Completeness

Prerequisites:
The official course prerequisites are:

   CS 250: Discrete Structures I  (sets, functions, relations, countability, proofs) 
   CS 251: Discrete Structures II (Boolean logic, first-order logic, formal reasoning and deduction)
   CS 311: Computational Structures (regular languages, context-free languages, Turing machines, computability)

Students will have previously encountered some but not all of the topics we will cover. Chapter 0 of the Sipser textbook sets the stage by providing background, prerequisite information that you should already know. We will not cover this chapter, but please read it before the first class as a refresher and to make sure you are ready for this material.

It is the student's responsibility to ensure that he/she has the appropriate background before attempting this class.

Course Outline:

Week 1 Sept 25	Topic Reading: Section xxx Lecture notes Practice exercises: xxx Topic Reading: Section xxx Lecture notes Practice exercises: xxx Topic Reading: Section xxx Lecture notes Practice exercises: xxx Homework xxx
Week 2 October 2	Topic Reading: Section xxx Lecture notes Practice exercises: xxx Topic Reading: Section xxx Lecture notes Practice exercises: xxx Topic Reading: Section xxx Lecture notes Practice exercises: xxx Homework xxx
Week 3 October 9	Topic Reading: Section xxx Lecture notes Practice exercises: xxx Topic Reading: Section xxx Lecture notes Practice exercises: xxx Topic Reading: Section xxx Lecture notes Practice exercises: xxx Homework xxx
Week 4 October 16	Topic Reading: Section xxx Lecture notes Practice exercises: xxx Topic Reading: Section xxx Lecture notes Practice exercises: xxx Topic Reading: Section xxx Lecture notes Practice exercises: xxx Homework xxx
Week 5 October 23	Topic Reading: Section xxx Lecture notes Practice exercises: xxx Topic Reading: Section xxx Lecture notes Practice exercises: xxx Topic Reading: Section xxx Lecture notes Practice exercises: xxx Homework xxx
Week 6 October 30	Topic Reading: Section xxx Lecture notes Practice exercises: xxx Topic Reading: Section xxx Lecture notes Practice exercises: xxx Topic Reading: Section xxx Lecture notes Practice exercises: xxx Homework xxx
Week 7 November 6	Topic Reading: Section xxx Lecture notes Practice exercises: xxx Topic Reading: Section xxx Lecture notes Practice exercises: xxx Topic Reading: Section xxx Lecture notes Practice exercises: xxx Homework xxx
Week 8 November 13	Topic Reading: Section xxx Lecture notes Practice exercises: xxx Topic Reading: Section xxx Lecture notes Practice exercises: xxx Topic Reading: Section xxx Lecture notes Practice exercises: xxx Homework xxx
Week 9 November 20	Topic Reading: Section xxx Lecture notes Practice exercises: xxx Topic Reading: Section xxx Lecture notes Practice exercises: xxx Topic Reading: Section xxx Lecture notes Practice exercises: xxx Homework xxx
Week 10 November 27	Topic Reading: Section xxx Lecture notes Practice exercises: xxx Topic Reading: Section xxx Lecture notes Practice exercises: xxx Topic Reading: Section xxx Lecture notes Practice exercises: xxx Homework xxx
Finals Week	Final Exam --- Monday, December 3, 2012 --- 10:15AM-12:05PM Study-Guide-for-Final

Policies:
Attendance in class is mandatory. Successful students will arrive on-time, relaxed and full of curiosity.

Attendance will be checked regularly and will count for part of your grade.

I encourage students to freely discuss the material in this class. You may also use the class mailing list to post questions, comments, etc. You should not post solutions to homework problems.

However, you must compose and write all homework and exam material individually. You may not copy or plagiarize.

The exams may test on material covered only in class and/or on material covered only in the reading assignments.

Your grade will be based approximately, as follows. These percentages are tentative and subject to change.

 
   Tentative

   10% - Homeworks
   12% - In-class quizzes, class participation
   50% - Midterm Exams
   30% - Final Exam

Incompletes will not be given.

Snow Closure: For inclement weather information, call the University switchboard, 725-3000, for a recorded message about university-wide class cancellation. Snow closure info is also available at: www.flashnews.net/pdx.html (click on "View Current Info").

Other Cancellations: If I should need to cancel class for any reason, I will email the class mailing list.

MailMan Mailing List: PorterClassList
A "MailMan" e-mailing list will be maintained for this class. From time to time I may post notices about the class and hints/comments about assignments. Students are encouraged to send mail to the list, too.

All students should subscribe to this list. Go to the following web page and enter your email address and a password and click "subscribe".

    
https://mailhost.cecs.pdx.edu/mailman/listinfo/porterclasslist/

The MailMan program will email you a confirmation message. You must reply, but you can simply hit your email "reply" button. After being adding to the mailing list you will get a "welcome" message from me.

To post a message to all the list members, send email to:

    PorterClassList@mailhost.cecs.pdx.edu

For additional documentation, see

    staff.imsa.edu/~ckolar/mailman/mailman-userguide-0.1.pdf (pdf, 159 kb)

(By the way, if Internet Explorer does not work with MailMan on the Mac, use the "Safari" web browser instead.)

Hints on how to study effectively:
Here is a document I wrote, which you may find useful or interesting:

Professor Porter's Study Tips

Problems / Comments on This Web Page

Send email to: harry@cs.pdx.edu
Harry Porter's Web Page: www.cs.pdx.edu/~harry

CS-581: Theory of Computation

Syllabus - Fall 2012

Week 1

Week 2

Week 3

Week 4

Week 5

Week 6

Week 7

Week 8

Week 9

Week 10

Finals Week

Problems / Comments on This Web Page