Complexity and Computability, 4003-481-01/4005-704-01

Complexity and Computability, 4003-481-01/4005-704-01, Winter 2012-2013

Course Description

This course provides an introduction to the theories of complexity and computability. It covers undecidability, degrees of undecidability, time and space complexity, reductions, and completeness.

Course Outcomes

Students will be able to explain basic concepts in computability theory.
Students will be able to explain basic concepts in complexity theory.
Students will be able to characterize problems by their degree of undecidability.
Students will be able to characterize problems by their space or time complexity class.
Students will be able to describe the relationships among complexity classes.

Course Web Page

http://www.cs.rit.edu/~eh/cc.html

Instructor

Edith Hemaspaandra
bldg. 70, room 3625
Email: eh at cs.rit.edu
http://www.cs.rit.edu/~eh

Office Hours Winter 2012-2013, weeks 1-10 (tentative)

Monday 11-12;
Monday 6pm (I will leave if nobody shows up at 6pm; part-time students have priority);
Tuesday 11-12 and 2-3;
and, if you can't make any of the above times, by appointment.

Asking questions via email seems to work well for many people.

Lectures

Monday/Wednesday, 4:00-5:50pm, GOL-3435.

Prerequisite

4003-380, 4003-389, 4003-700, or 4005-700.

Required Book

Michael Sipser, Introduction to the Theory of Computation, third edition, Course Technology, June 2012.

Other Materials

I will distribute copies of the slides that I use at the start of class and I will post them. Supplementary materials, as well as information about reading and homework assignments, exams, etc. will be linked from the course web page.

The Work

Homework Assignments

There are eight graded homework assignments, one per week except for the first week and the week of the midterm. Homeworks are due on Wednesday at 4pm, and are usually posted at least six days before they are due. The actual assignments will be available on the homework and reading page.

Discussing homework with your classmates is encouraged. However, after such discussions, you have to discard all notes, cell phone pictures, and other materials you have created before you write up your solutions on your own without further consultations with your classmates or any written material other than your class notes, materials handed out in class, the textbook, and materials linked from this page. You are not allowed to discuss the homework with people other than your classmates and me. You are not allowed to look up the answers to your homeworks and you should be able to explain all of your homework to me.

Your homework submissions must be submitted by Wednesday, 4:00pm sharp. You have the following submission options:

Give it to me before the start of class or during office hours.
Upload it to myCourses (as a single well-readable pdf file). Do not wait until the last moment to upload.

I will not accept late assigments for any reason. I will drop the lowest homework grade for 4005-704. I will drop the lowest two homework grades for 4003-481. However, a zero for cheating will not be dropped.

I will not answer homework questions on the day that the homework is due.

Midterm Exam

The midterm exam will take place on Wednesday, January 16, 4:00-5:50, in 70-3435.

Final Exam

The final exam is scheduled for Monday, February 18, 10:15-12:15, in 70-3435.

Evaluation

50% Homeworks and the best of
- 25% Midterm and 25% Final Exam or
- 20% Midterm and 30% Final Exam.

Numerical grades will be converted to letter grades according to the following scale:
> 88%: A; 77%-88%: B; 66%-77%: C; 55%-66%: D; < 55%: F.
However, your course grade will never be more than one letter grade higher than your average exam grade. In addition, if your average exam grade is below 55%, you fail the course.

Disputing Your Grade

If you feel that an error was made in grading your homework or exam, you have one week from the moment the graded work was handed back to dispute your grade. All grading issues should be taken up with me; do not discuss grading issues with graders!
All grades will be posted on myCourses.

Students with Disabilities

RIT is committed to providing reasonable accommodations to students with disabilities. If you would like to request accommodations such as special seating or testing modifications due to a disability, please contact the Disability Services Office. It is located in the Student Alumni Union, Room 1150; the Web site is http://www.rit.edu/dso. After you receive accommodation approval, it is imperative that you see me during office hours so that we can work out whatever arrangement is necessary.

Academic Honesty

The DCS Policy on Academic Honesty will be 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.

Electronic Devices in Class

Professional and respectful behavior is expected. If behavior is disruptive, the policy on electronic devices in class will change accordingly. You are not allowed to record the lectures.