Fall 2015: Limits of Computation, CS:4340:0001 (22C:131:001)
The course meets 12:30--1:45 pm Tuesday and Thursday
at 221 MLH (MacLean Hall).
Kasturi Varadarajan, 101D MacLean Hall, Phone: 335-0732, email:firstname.lastname@example.org. Office Hours: 3:00--4:30 Monday, 3:30--5:00 Thursday.
Ruoyu Zhang. Office hours: 10:00 am to 11:30 am on Tuesdays, in 101N MLH. Ruoyu's email: email@example.com.
What this Course is About
This course addresses questions such as
To answer these and other questions, we'll learn about simple models of computations such as Turing machines and circuits.
A previous edition of the course can be found here.
- Are there computational problems for which there are no algorithms? What
are some examples? How do we go about showing that a particular problem admits
- What happens when we restrict resources such as time or space? How can
we prove that with more time, we will be able to solve problems that we
- What happens to these questions when randomized algorithms are allowed?
- Precisely how do we define the classes P, NP, and co-NP?
- How can the NP-Completeness of SAT (the first NP-complete problem)
actually be demonstrated? In the algorithms course, we only hint at this.
- What about space complexity and other models of computation?
Our text is Computational Complexity, by Arora and Barak.
Undergraduate Algorithms (At the UI this is CS:3330 (22C:031)).
The grading will be based on 5 to 6 homeworks (40 percent of the grade),
a midterm (25 percent), and a final (35 percent).
The policy on late homeworks is that you have a quota of three days
for the entire semester that you may use for late submissions. So
for example, there will be no penalty if you submit the third homework
a day late, the fifth two days late, and the rest of the homeworks
on time. Once you use up your quota of three days, any homework submitted
late will not be accepted and you will get 0 points for that homework.
When you submit a homework X days late, your quota gets decreased by X
irrevocably. You can only be late by an integer number of days, obtained by
rounding up -- if you
submit 10 hours after the deadline, for example, your quota is depleted
by one day.
The midterm will be held October 29, from 6:30 to 8:30 pm, in 22 SH (Schaeffer Hall). The final will be held Monday, December 14, from 7:30 to 9:30 am,
as scheduled by the Registrar's office.
What We Covered Each Week
We will keep track of what we covered each week
Handouts and Homeworks