Computer Models and Limitations

Computer Science 280
University of Rochester
Spring 2015

Instructor: Muthu Venkitasubramaniam

Time: TR 15:25-16:40
Place: Morey 321
Course Web page: http://www.cs.rochester.edu/courses/280/spring2015/

Graduate Teaching Assistant:

• Spyridoula Gravani

  • Email: sgravani@cs.rochester.edu

  • Office Hours:

    • 10:00a-11:00a Wednesday (Room CSB 727A)

    • 10:00a-11:00a Friday (Room CSB 727A)

Undergraduate Teaching Assistants:

• Ian Mackinon

  • Email: imackinn@u.rochester.edu

  • Office Hours: 12:00p-1:00p Monday (Room CSB 727A)

• Doug Miller

  • Email:dmill44@u.rochester.edu

  • Office Hours: 10:00a-11:00a Tuesday (Room CSB 727A)

• Adam Scrivener

  • Email:ascriven@u.rochester.edu

  • Office Hours: 3:00p-4:00p Thursday (Room CSB 727A)

Workshop Leaders:

• Hassler Thurston (Email: jthurst3@u.rochester.edu)

  • Workshop I: 7:30p-9:30p Wednesday (Room CSB 632)

  • Workshop II: 7:30p-9:30p Thursday (Room CSB 632)

• David Sekora (Email: dsekora@u.rochester.edu)

  • Workshop III: 5:00p-7:00p Tuesday (Room CSB 601)

  • Workshop IV: 5:00p-7:00p Thursday (Room CSB 601)

Reading

The required text for the course is Introduction to the Theory of Computation (2ed.) by Michael Sipser. (Please note that this is the second edition)

You may find the following books to be useful references. Note, however, that we will not always be following the same notations as these books.

• [HMU06] Introduction to Automata Theory, Languages, and Computation (3ed.), J. E. Hopcroft, R. Motwani, J. D. Ullman, 2006

• [K97] Automata and Computability, D. Kozen, 1997

Topics Outline

TBD

Lectures

TBD

Prerequisites

CS 173 and MTH150

Course Administration

All homeworks and grades will be posted on blackboard. Course announcement, discussions and notes will be posted through Piazza.

Grading

There will be Quizzes every class, Homeworks every week, and 3 Mid-terms. The grade will be based on all tests and workshop participation

Quizzes 25%

Homeworks 25%

Mid-Terms (10+10+10)%

Workshops 20%

Homework Policy

You are free to collaborate with other students on the homework, but you must turn in your own individually written solution and you must specify the names of your collaborators. Additionally, you may make use of published material, provided that you acknowledge all sources used. Note that it is a violation of this policy to submit a problem solution that you are unable to explain orally to me. Typed problem sets are strongly preferred.