1:30-2:20 MWF Room 213 MLH
Instructor:
Sriram V. Pemmaraju
101G MLH, sriram@cs.uiowa.edu, 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.
Required Legalese
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.
Prerequisite
Undergraduate Algorithms (22C:31) or its equivalent.
Textbook
Michael Sipser, Introduction to the theory of computation, Second Edition,
Published by Course Technology, ISBN 0534950973.
Grading
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: rraman@cs.uiowa.edu 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
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.
Student Complaints
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 (cremer@cs.uiowa.edu, 319-335-1713, 14D McLean Hall).
Consult the college policy on Student Complaints
Concerning Faculty Actions (online version)
for more information.
List of Topics: