CS310 Theoretical Computer Science

Course Syllabus

Fall 2010

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 

The above topics were copied with permission from the Computing Curricula 2008 recommendations,
the latest version of which can always be found here
 
Instructor Details

Professor: Chadd Williams

Email: chadd@pacificu.edu

Office: Strain 202

Phone: (503) 352-3041

Office Hours: 

Course Basics

Course Title: CS310 Introduction to Theoretical Computer Science

Prerequisite: CS250

Meeting Times: MWF 2:15-3:20 pm

Location:        Marsh LL15

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, 5, 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/cs310f10/

Course Assessment

Important Dates

(Tentative) Dates for Midterms

• Midterm 1: Monday, October 4, 2010.
• Midterm 2: Friday, November 12, 2010
   

Date of Final

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

Other Dates

6 September Labor day holiday (no classes)

8 October No classes (Arts & Sciences)

24-26 November Thanksgiving break 

8 December Reading day

Course Policies

• Assignments are to be submitted by the beginning of class on the day in which the assignment is due.  Late assignments will not be accepted. Both mathematical proofs and programming assignments often take longer than expected to complete. Start your assignments early.
• A programming that does not successfully compile or produces no output loses 70% of the assignment grade.
• Grade Complaints: 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 within five working days of when the graded material was returned to you. I will not consider any grade changes later than five working days after the graded material was returned.
• 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.
• Sanctions that may be imposed for academic dishonesty are:
  
  • First offense for any type of cheating: zero on the assignment and 10 percentage points deducted from your final course grade..
  • Second offense for cheating (any combination of exam/homework/programming assignment) of any kind: `F’ in the course
• 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.