Computer Models and Limitations (CSC 280) - Summer 2021
Course Description (from CDCS)
Students will gain an understanding of fundamental computer models and their computational limitations.
Topics comprise: finite-state machines, the context-free languages, pumping lemmas, Turing machines,
decidable and Turing-recognizable languages, undecidability, NP-completeness. Prerequisites: CSC 173
& MATH 150
Course outcomes
- Students will deepen their knowledge of regular languages and show how to prove when a
language is not regular.
- Students will deepen their knowledge of context-free languages and show how to prove when a
language is not context-free.
- Students will learn the fundamentals of computability theory along with techniques to prove
when languages are undecidable.
- Students will be introduced to the basics of complexity via the study of NP-completeness,
self-reducibility, the polynomial time hierarchy, and additional topics if time allows for them.
Course Webpage
Instructor Information
Name: Michael C. Chavrimootoo
(he/him/his)
Email: michael (dot) chavrimootoo (at) r o c h e s t e r (dot) e d u
(Students can generally expect a response within 24 hours
on weekdays. This does not apply to homework questions sent within 24 hours of the due date.
I highly recommend you start your work early.)
Office Hours: TBD (EDT) via Zoom. Link will be on Blackboard.
TA Information
Name: Henry Welles
(he/him/his)
Email: hwelles (at) u (dot) r o c h e s t e r (dot) e d u
Office Hours: Thursdays 11am-12pm (EDT) via Zoom. Link will be on Blackboard.
Lectures
Monday, Tuesday, Wednesday at 1:00PM - 3:50PM (EDT) via Zoom. See Blackboard the the Zoom link.
Attendance is required (See grading).
Course Material
- Sipser M. Introduction to the Theory of Computation, 3rd Edition, 2013 (US Edition).
(Be careful, there is also an international edition which is not the same as the US edition.
Make sure to get the US edition.)
- Other materials, such as lecture slides, course notes, and homeworks, will be
distributed via Blackboard. You are not be allowed to distribute these.
Schedule
There isn't a fixed schedule for the course. What students can expect is the following:
- We will cover (almost entirely) Chapters 0-5 and 7 from the textbook. If
time permits, we will look at additional topics.
- There will be 2 midterms, each on the following dates:
- Monday, July 19th, 2021
- Wednesday, August 4th, 2021
Grading
You will be graded on the following basis:
- Attendance - 10%
- Midterms (2) - 60%
- In-class exercises - 30%
The different items in each category are equally weighted.
Attendance is mandatory and counts towards your final grade.
The in-class exercises will be to
aid students learn the material. You can think of them as equivalent to homeworks, but done in
class.
Additional guidelines will be provided in class.
Midterm dates are already posted in the syllabus.
Grade Disputes
All grade disputes must be taken up to the instructor within three (3) days from when
the grade was assigned. Do not discuss issues of grading with tutors, grades, or peers.
Rescheduling Midterms
Midterms can not be made up except for real emergencies in which case proper documentation
(like a doctor's note) will be required. If at all possible, you should contact me prior to
the midterm. Oversleeping, cars that don't start, etc. do not constitute a valid excuse.
Disabilities and/or Accommodations
Please reach out to the relevant office and have them inform me if you need any accommodations.
I will be more than happy to grant them.
Academic Integrity
UR's academic honesty policy will be strictly enforced. You should only submit work
that is completely your own. Failure to do so counts as academic dishonesty and so does being
the source of such work. Submitting work that is in large part not completely your own work
is a flagrant violation of basic ethical behavior and will minimally be punished with failing
the course.
If you're worried about your performance in the course, reach out to the instructor before
considering academic dishonesty. If you're facing a grey area and aren't sure if you might do
something dishonest, reach out to the instructor.
Zoom Etiquette
Lectures will be recorded. Office hours will not be recorded. You are expected to show
mature and respectful behavior both in lectures and in office hours. Do not hesitate to add your
preferred name and pronouns in your Zoom name.
Disclaimer
This page is subject to change throughout the term. Important changes will be announced in class.