CS310 Theoretical Computer Science

Course Syllabus

Fall 2006

Introduction

   This course is an introduction to the mathematical foundations of the theory of computation. We will study automata theory, formal languages, the theory of computability and undecidability, and computational complexity.  This material is central to many branches of computer science; it underlies the basic theory of compiler design, the efficiency of algorithms, and the limitations of computing. 

Aim

Have a basic understanding of complexity theory, computability theory, and automata theory.

Objectives

• Understand computational models such as Finite Automata, Pushdown Automata, and Turning Machines.
• Understand formal language counterparts of these computational models, such as regular languages, context-free languages and recursive languages.
• Understand time complexity and Class P and Class NP.

Topics

 
Instructor Details

Professor: Chadd Williams

Email: chadd@pacificu.edu

Office: Strain 202

Phone: (503) 352-2223

Office Hours: M 03.00 - 04.00 PM

T  02.00 - 04.00 PM

F  11.00 - 12.00 PM or by appointment

Course Basics

Course Title: CS310 Introduction to Theoretical Computer Science

Prerequisite: CS250

Meeting Times: MWF 01.00 - 01.50 PM (lecture)

Location:        Marsh LL21

Textbook:      Introduction to the Theory of Computation by Michael Sipser, PWS Publishing Company, ISBN 0321129474 (Second Edition)

From this text we will cover Chapters 0, 1, 2, most of 3, part of 4, and most of 7.

Errata: http://www-math.mit.edu/~sipser/book.html

Software:       JFLAP -- http://www.jflap.org/

Course Website: http://zeus.cs.pacificu.edu/chadd/cs310f06/cs310.html

Course Assessment

Important Dates

Dates for Midterms

• Midterm 1: Friday, October 13, 2006.
• Midterm 2: Wednesday, November 13, 2006
   

Date of Final

• Final Exam: Tuesday, December 5, 8:30AM-11:00AM

Assignments:

• Assignments will be posted here
• Homework #1 Solution
• Homework #2 Solution
• Homework #3 Solution
• Homework #4 Solution
• Homework #5 Solution

Weekly Schedule (Tentative)

WEEK 1

WEEK 2

WEEK 3

WEEK 4

WEEK 5

WEEK 6

WEEK 7

WEEK 8

WEEK 9

WEEK 10

WEEK 11

WEEK 12

WEEK 13

WEEK 14

WEEK 15

Other Dates

4 September Labor day holiday (no classes)

11 September Last day to add courses. Last day to drop courses with no record

6 October No classes (Arts & Sciences)

6 November Last day to withdraw from courses

22 - 24 November Thanksgiving break (starting at Noon on the 22nd)

6 December Reading day

Course Policies

• Assignments are to be submitted by the beginning of class on the day in which the assignment is due (which will generally be Friday).  Late assignments will not be accepted. Both mathematical proofs and programming assignments often take longer than expected to complete. Start your assignments early.
• If you have a complaint regarding a grade on an assignment or exam, write a one paragraph description of why you feel the grade is incorrect and deliver it to the instructor. The paragraph must be delivered to the instructor within one calendar week of when the graded material is returned to the student.
  
• No early or late exams/finals will be given.
• No incompletes will be given.
• The cheating policy is defined in Pacific Stuff & the Pacific Catalog as well as the Academic Policy that each of you signed upon entering Pacific University. Be sure you read or reread this policy carefully. All code written for our course is to be an original design and an original implementation. The Web, textbooks, and any other references are simply references for you. Copying source code from any source is prohibited. Further, source code is not to exchange hands in any form or by any medium except when sending your solutions to the instructor. It is OK to share high level ideas during the design phase, help someone in the class fix a bug occasionally, share information dealing with OS issues, debugger issues, in general, development issues that do not involve code writing.
• All code in any form generated from this course becomes the intellectual property of Pacific University. You may not share this code with anyone without obtaining written permission from Pacific University.
• Neither computer failure, software failure, nor lack of computer access are accepted as excuses for late programs; therefore, start work on the programs as soon as they are assigned, don't put them off until the last minute. Further, corruption of programs due to bad disk media is also not accepted as an excuse for late programs; therefore, always keep a current backup of all programs on a separate disk.
• The instructor reserves the right to raise or lower a student's grade based on class participation and attendance.
• I do not want to hear any electronic devices go off during lecture; therefore, make sure you silence these devices before lecture starts.
• Your attendance is expected at each class meeting. It is in your own best interest to attend class, as your grade will almost certainly suffer indirectly if you choose not to attend. In addition, I reserve the right to consider attendance in instances of borderline grade assignments. Of course, excused absences (sickness, family emergencies, varsity athletic participation) will not be held against you. Scheduled absences should be communicated to me well in advance. If you must miss a class, be sure to check with me or another student to get what you missed. Exams will be given in class on the day scheduled and may not be made up. The material in the course is, by necessity, cumulative. Be warned that if you fall behind, you will not be able to catch up easily.
• If you have a documented disability covered under the ADA then services and accommodations are available from LSS (Learning Support Services). If you need reasonable accommodations to fully participate in course activities or meet course requirements, you must contact Edna K. Gehring, Director of LSS , at X2107. She will meet with you, review the documentation of their disabilities, and discuss the services Pacific offers.