1:30-2:20 MWF Room 213 MLH
Sriram V. Pemmaraju
101G MLH, email@example.com, 319-353-2956
Office Hours: 9-10 Tuesday, 11:30-12:30 Wednesday, and 2:30-3:30 Friday.
This course is a mathematical exploration of the limits of the power of computers. Some of the questions we ask and attempt to answer are the following. Are there problems that cannot be solved on any computer? How does one determine if a given problem can or cannot be computationally solved? If we place bounds on the resources (time and space) available to a computer, then what can be said about which problems can and which problems cannot be solved on a computer? How does the power of a computer change, if it has access to random bits? What happens when we relax the notion of solving a problem to "approximately" solving a problem - does this fundamentally change which problems can and which problems cannot be solved on a computer?
In attempting to answer these questions we will study languages, Turing machines, undecidability, time complexity classes P, NP, NP-complete, space complexity classes L and NL, the Cook-Levin theorem, the poly-time heirarchy, reductions, randomized algorithms and randomized complexity classes such as BPP, approximation algorithms and hardness of approximation. Time permitting, we will also study interactive proofs.
This course is run by the College of Liberal Arts and Sciences. This means that class policies on matters such as requirements, grading, and sanctions for academic dishonesty are governed by the College of Liberal Arts and Sciences. Students wishing to add or drop this course after the official deadline must receive the approval of the Dean of the College of Liberal Arts and Sciences. Details of the University policy of cross enrollments may be found online here.
Undergraduate Algorithms (22C:31) or its equivalent.
Michael Sipser, Introduction to the theory of computation, Second Edition, Published by Course Technology, ISBN 0534950973.
Plus/Minus grading will be used for the course. There are two components that will determine your grade.
Midterm March 9rd, Friday Time and place TBA Final May 9th, Wednesday 7:30-9:30 am (in 213 MLH)For the midterm, I would like to find a 2 hour slot on March 9th (possibly in the evening) that works for everyone. All exams will be open book/notes exams. The final will be cumulative,
Solutions will be provided on the course page for all graded work.
Teaching Assistant Information
The TA for the course is Rajiv Raman. Contact information and office hours for Rajiv are:
Office: 101K, MLH Phone: 353-2542 E-mail: firstname.lastname@example.org URL: www.cs.uiowa.edu/~rraman/ Office hours: TTh 11:00-12:00
Students with disabilities
I would like to hear from anyone who has a disability which may require seating modifications or testing accommodations or accommodations of other class requirements, so that appropriate arrangements may be made. Please contact me during my office hours.
Academic dishonesty will not be tolerated. Under no circumstances should you pass off someone else's work as your own. This also applies to code or other material that you might find on the internet. Note that we will routinely use available software systems for detecting software plagiarism, to test any suspicions we might have. If you are unclear about what constitutes academic dishonesty contact your professor or consult the printed policy in the Schedule of Courses and the CLAS Bulletin (online version). We do want students to talk to each other about concepts and ideas that relate to the class. However, it is important to ensure that these discussions do not lead to the actual exchange of written material.
If you have any complaints or concerns about how the course is being conducted by me or by the TAs please feel free to talk to me. You are also welcome to get in touch the the Computer Science department chair, Prof. Jim Cremer (email@example.com, 319-335-1713, 14D McLean Hall). Consult the college policy on Student Complaints Concerning Faculty Actions (online version) for more information.
List of Topics: