CS 5311: Computation Theory
 Spring 2013
 3:35-4:50pm ΤΘ
125  Fisher

Most recent update: April 26
Final Exam: 3:00-5:00pm Thursday, May 2
Second Exam: 5:30-7:00pm Thursday, April 25, 135 Fisher
Homework 5 Due Tuesday, April 16
Homework 4 Due Thursday, March 28
First Exam: 5:30-7:00pm Thursday, March 7
Homework 3 Due Thursday, March 7
Homework 2 Due Tuesday, Feb. 26
Homework 1 Due Tuesday, Feb. 5
Topics covered include Turing machines and their variants, the halting problem and decidability, computability, reducibility, NP-completeness, time and space complexity, and topics from recursive function theory. The course starts with a brief review of the computation models from CS 3311. Prerequisite: CS 3311

Prerequisite CS 3311 (Fall '10 course web page for CS 3311)
Syllabus
Text (required):
Title: Introduction to the Theory of Computation (Second and Third Editions are acceptable)
Author: Michael Sipser
ISBN-13: 978-1-133-18779-0
Publisher: Cengage Learning
Pub. Date: 2013
Errata: Textbook typografical errors
Instructor: Steve Seidel
Office hours: To be announced and whenever my door is open, and by appointment.
Office: 310 Rekhi Hall
Phone: 487-2950
Email: steve@mtu.edu

A real Turing machine

The complexity zoo

Grading is based on a 10% sliding scale: 100%-90% A, 89%-80% B, etc. Course activities will be weighted as given below.

50%: Homework will be assigned on a regular basis. You may discuss problems with each other but you are most strongly encouraged to do the problems on your own because this approach is the best way to prepare for the examinations. Under all circumstances, you must write your answers to the homework problems in your own words. Homework assignments will be graded; they will be worth about 50 points each.

24%: Two 1-hour in-class closed-book exams, each worth 12%, will be given.

26%: 2-hour final exam. The format of the final exam is like that of the midterm exams, but the final exam will be comprehensive. This exam will be given in the regularly scheduled final exam time slot.

All students in this course are expected to read, understand, and abide by the University's Academic Integrity Policy.