CS310 Theoretical Computer Science

Course Syllabus

Fall 2014

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 are from the ACM Computing Curricula recommendations,
 
Instructor Details

Professor: Chadd Williams

Email: chadd@pacificu.edu

Office: Strain 202

Phone: (503) 352-3041

Office Hours:   M,W,Th 2-4pm

Course Basics

Course Title: CS310 Introduction to Theoretical Computer Science

Prerequisite: CS250

Meeting Times: MWF 4:45pm - 5:50pm

Location:        Marsh LL 15

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/chadd2/cs310f14/

Course Assessment

Important Dates

(Tentative) Dates for Midterms

• Midterm 1: Monday, September 29, 2014.
• Midterm 2: Friday, November 7, 2014
   

Date of Final

• Final Exam: Friday, December 5, 3-5:30pm
• http://www.pacificu.edu/as/calendar/finals/

Other Dates

1 September Labor day holiday (no classes)

3 October No classes (Arts & Sciences)

26-28 November Thanksgiving break 

3 December Reading day

Class will be held on November 24!

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 assignment that does not successfully compile or produces no output loses 70% of the assignment grade. JFLAP assignments are considered programming assignments.
  
• 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 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.

• Learning Support Services for Students with Disabilities: http://www.pacificu.edu/studentlife/lss/

  Services and accommodations are available to students covered under the American with Disabilities Act. If you require accommodations in this course, You must immediately contact Learning Support Services for Students with Disabilities at x2194 or email at lss@pacificu.edu. The Director or her Assistant will meet with you, review the documentation of your disability and discuss the services Pacific offers and any accommodations you require for specific courses. It is extremely important that you begin this process at the beginning of the semester. Please do not wait until the first test or paper.