CSC 280/480: Computer Models and Limitations - Fall 2023

Course info:

Course syllabus
Lecture:
MW 2:00pm- 3:15pm, Morey Hall room 321
Workshop:
M 4:50 PM - 6:05 PM, Bausch & Lomb Room 269
Workshop:
Th 4:50 PM - 6:05 PM, Dewey Room 4162
Instructor:
Kaave Hosseini    Email: kaave.hosseini@rochester.edu
Office hours:
W 3:30-5:00pm, Wegmans 2507
Grad TA:
Hecong Wang    Email: hwang99@u.rochester.edu
Office hours:
T 11:30 AM - 12:30 PM Wegmans 2307
TA:
Minh Dang    Email: mdang2@u.Rochester.edu
Office hours:
Th 2:00 PM - 3:00 PM Wegmans 2215
TA:
Jonathan Wang    Email: jwang201@u.rochester.edu
Office hours:
T 2:00 PM - 3:00 PM Wegmans 2215

Course Description:

This course studies fundamental computer models and their computational limitations. Finite-state machines, context-free languages, Turing machines, decidable and Turing-recognizable languages, undecidability, time complexity, and space complexity.

Prerequisites:

CSC173 and MATH 150.

Homework:

Weekly homework is posted on Slack.


Textbook:

Introduction to the Theory of Computation, 3rd Edition, by Michael Sipser. Available on amazon.

Slides:

The slides are available on Slack. They are a modified version of slides created by Michael Sipser.

image
Jan van der Greef/ Buiten-beeld/Minden Pictures/Corbis