CS 373: Theory of Computation


Fall 2009 TuTh 11:00-12:15 Room 103 Talbot Lab

Professor:
Steve LaValle
lavalleuiuc.edu
3318 Siebel Center
Phone: 217-265-6313
Office Hrs: Tu 2-3pm, Th 3-4pm 		      Teaching Assistants:
Dima (Dmytro) Suvorov
suvorov1illinois.edu
0209 Siebel Center
Phone: 217-721-9935
Office Hours: Mon 2-3pm 		     
Jingjin Yu
jyu18uiuc.edu
0209 Siebel Center
Phone: 217-333-0377
Office Hours: Wed 2-3pm 		     
Reza Zamani
zamaniuiuc.edu
0209 Siebel Center
Phone: 217-???-????
Office Hours: Fri 3-4 pm


Some "practice" complexity problems are posted here.
Midterm2 solution is posted here.
Mock midterm2 is posted here.
A brief solution to midterm1 is posted here.
A mock midterm is posted here.

Course Objectives

Course Topics

Prerequisites

The prerequisites for this course are CS 125 (or ECE 190), CS 173 (or MATH 213), and CS 225.

To assess the mathematical side of your background, read Chapter 0 of the Sipser textbook. You might not be able to produce all the details from memory, but almost all of it should look like something you either know or used to know.

Other experience, such as advanced math courses, may be able to serve in lieu of these prerequisites, especially CS 225. If you are still uncertain about whether you have sufficient background, ask Steve LaValle.

Textbooks and Materials

Required: M. Sipser, Introduction to the Theory of Computation, 2nd Edition, Course Technology, 2006.

Recommended: J. Hopcroft and J. Ullman, Introduction to Automata Theory. Languages and Computation, Addison-Wesley, 1979 (or the 2nd Edition, 2001, by J. Hopcroft, R. Motwani, and J. Ullman).

Lectures

Lectures will be presented the old-fashioned way: By use of chalk and a blackboard. In many classes, the exact presentation given in class is available from the web. Not here. In this course, the best way to find out what was done in class is to attend class. The lectures do not exactly match any of the books or course materials. It is also important to attend class to obtain and handouts or receive any critical announcements. If you are unable to attend a class, you can visit office hours to determine what was covered.

Discussion Sections

In addition to the lectures, each student is enrolled in a discussion section that meets once a week for 50 minutes. All of these meet in Room 1111 Siebel Center. The times are: These sessions are conducted by the TAs and offer a smaller classroom setting to discuss the course and homework material. The presentations are oriented more towards solving problems than the lectures. Students are responsible for material covered in the sessions, just like the regular lectures. Much of the discussion is not repeated in the regular lectures; therefore, skipping these would be unwise.

Homework

There will be a problem set roughly every other week, due at the beginning of class. You may work individually on homeworks or in groups of up to three (except for HW 0). When working in a group, each student must write up and submit his or her own solutions and list at the top of the submission the other students in the group. See the homework page for more information on homeworks. When computing the final homework average, we will drop the lowest score (unless the lowest score was obtained as a cheating penalty).

Examinations

There will be two midterm exams, and one final exam. You will be responsible for all material covered in lectures, discussion sections, homeworks, and assigned readings.

All exams will be closed book and closed notes. No calculators are allowed.

Grades

We will use Illinois Compass for online grade posting.

Grading scheme

The various components of the course will be weighted as follows:
Homeworks 20%
Midterm Exam 1 20%
Midterm Exam 2 20%
Final Exam 40%
When computing the final homework average, we will drop the lowest score (unless the lowest score was obtained as a cheating penalty).

In previous terms, this course has given about 20% As, 30% Bs, 30% Cs, 15% Ds, and 5% Fs. We expect the grading scale to be no more harsh than this. As the term progresses, we will try to keep you informed about where we think you stand in terms of letter grade. We will give a grade of C- or above to students whose grasp of the material makes them adequately prepared to succeed in the following CS courses (CS 421 and 473). We only plan to give a handful of Fs. Normally, most Fs involve students who stopped even attempting to do the work, often very early in the term, but mysteriously never dropped the course. Ideally, we would like everyone either drop the course early on, or else pass it.

Regrades

If you have a question or complaint about the way a homework or exam problem was graded, then, within one week of the date the assignment is returned, please submit a written request explaining in detail why you believe it has been graded unfairly to one of the TAs during office hours. Make sure to include your name and NetID and, in case of a group homework, those of your group members. We want everyone happy and satisfied, but we cannot do much in the couple of minutes before and after class.

Except for cases of simple arithmetic mistakes, the entire homework or exam will be regraded very carefully from scratch. We intend to take regrade requests very seriously and will give use the greatest care possible in reconsidering the evaluation of points; however, frivolous regrade requests will be met with the scorn and derision they deserve. It could be possible that more points are taken off, if more errors are discovered as a result of the regrading. We will readily admit, apologize for, and correct our mistake if you have been unfairly graded; such mistakes are bound to occur for a class of this size. Please note that out notion of fairness means you were graded no more harshly (nor more leniently) than other people in the class. Thus, it does not refer to your own opinion of whether you deserve more points for incomplete or partially correct answers. Such opinions are usually subjective; rather than debate, we can only offer our own opinion of how much credit various answers are worth, and then try our best to treat everyone the same way.