Computer Models and Limitations


Instructor: Mehdi Manshadi


Department of Computer Science

University of Rochester

Spring 2010


This page is under construction. Contents are subject to change.


Location: CSB 601

Time: MW 3:25-4:40


Instructor's office hours: Please make an appointment by email.


TA: Curtis Menton

TA's office hours: TR 2-3pm (CSB 617)


Workshop Leaders: Adina Rubinoff (Tuesdays), Scott Ames (Fridays)



Michael J. Sipser, Introduction to the Theory of Computation (2nd edition), Thomson (Course Technology), 2006.

or alternatively,

John E. Hopcroft and Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, 1979.

-Both are on reserve in the library. There will be handouts for the topics not covered in the book.



Workshop 5%

Homework 15%

Quiz 10%

Short Exams 10%

Midterm 20%

Final: 40%



There will be 15 workshops. Each workshop will be held twice: Fridays 3:30-5pm and the follwoing Tuesdays 5-6:30pm, both in CSB 632 (e.g. Workshop-1 will be held on Friday 1/15 and Tuesday 1/19, Workshop-2 will be held on Friday 1/22 and Tuesday 1/26, etc.). Attending one session of each workshop is required and counts for 5% of your final grade.




There will be 15 problem sets, posted on the course web site on Wednesdays right before class. The assignments are due 1 week later in class (except the one assigned before spring break, which will be due the Monday after break). No late submissions will be accepted. In order to allow for any sick days, religious holidays, unavoidable trips, etc. the lowest 3 problem set grades will be dropped.




There will be 15-20 quizzes with no advance warning (exception: there will be a quiz on the first day of class!), given at the beginning, in the middle, or at the end of the class. The quizzes may be based on the two previous lectures, the reading assigned for the day, the lecture just given, or the assignment due that day. You will get 25% of the score just for taking the quiz. As with homework, the lowest 3 quiz grades will be dropped.


Short Exams (2/15, 4/7)

There will be two short exams, at the end of the first and third quarters of the semester, covering part 1 (Automata) and part 3 (Complexity) of the course respectively (See course syllabus below). They each contribute 5% to your final grade.


Midterm (3/17)

There will be a midterm on Wednesday 3/17, covering the first two parts of the course (Automata and Computability). The midterm counts for 20% of your final grade.


Final (5/3, 8:30AM)

The final exam will be on May 3rd at 8:30AM. It is cumulative, and counts for 40% of your final grade. The final will be an open-book exam.



Collaboration on homework is allowed as long as no written solutions are taken out of the discussion, and each student writes up their own independent solution.





Reading assignment



W 1/13


This handout

SP Ch. 0/HU Ch. 1

Lecture 1


M 1/18

Martin Luther King Day, No class.

Part 1. Automata

W 1/20

Strings, Languages, and Regular Expressions

SP pp 63-66

Lecture 2


M 1/25

Finite Automata

SP pp 31-54/HU pp 13-21



W 1/27

Regular Grammars, Equivalence of the models




M 2/1

Properties of Regular Languages




W 2/3

Context-Free Grammars




M 2/8

Push Down Automata




W 2/10

Pumping Lemma




M 2/15

Review, Q&A, Short Exam 1




Part 2. Computability

W 2/17

Turing Machines




M 2/22

Alternative definitions




W 2/24





M 3/1





W 3/3

Post Correspondence Problem




M 3/8

Spring break

W 3/10

Part 3. Complexity

M 3/15

Review, Q&A




W 3/17





M 3/22

Time complexity & the class P




W 3/24

Class NP: P vs. NP




M 3/29





W 3/31

Space Complexity




M 4/5

The class L and NL




W 4/7

Review, Q&A, Short Exam 2




Part 4. Advanced topics

M 4/12

Kolmogorov Complxity




W 4/14

Cryptography and one-way functions




M 4/19

Randomized computation and the class BPP




W 4/21

Take it easy: Approximation




M 4/26

Take it easy [cont.]:

Average Case Complexity




W 4/28

Something fun:

Quantum computing and the class BQP