12:30-1:45 TTh 61 SH (Schaeffer Hall)
Instructor:
Sriram V. Pemmaraju
Office: 101G MLH, sriram-pemmaraju@uiowa.edu, 319-353-2956
Office Hours: 1:30-2:30 M, 10:30-11:30 W, 2:00-3:00 F (and by appointment)
Course website: http://www.cs.uiowa.edu/~sriram/5340/fall17/
Department website: http://www.cs.uiowa.edu/
Overview
This course is a mathematical exploration of the limits of the power of computers and computation.
Some of the questions we ask and attempt to answer are the following: are there problems that cannot be solved on any computer?
What are some examples of these unsolvable problems? How do we prove that a problem is computationally unsolvable?
If we place bounds on the resources (time and space) available to a computer, then what can be said about which problems
can and cannot be solved on a computer? How do we show that as the resources (time and space) that a computer uses,
are increased then the collection of problems that can be solved grows? How does the power of a computer change, if it
has access to random bits? How does getting a limited amount of "advice" increase the power of a computer?
What if the computer could interact in a limited way with a powerful advisor?
In attempting to answer these questions we will study models of computation such as Turing machines and Boolean circuits, time complexity classes such as P, NP, NP-complete and those in the polynomial hierarchy, space complexity classes such as PSPACE, L and NL, and randomized complexity classes such as RP and BPP. We will also study interactive proofs and the corresponding complexity class IP and touch upon the surprising result that IP = PSPACE.
We will cover the following topics in the course:
Reading Material
These topics come from the first eight chapters of the following required textbook:
Computational Complexity: A Modern Approach by Sanjeev Arora and Boaz Barak, Cambridge University Press, 2009.
Prerequisite
CS:3330 Algorithms (or its equivalent)
Grading
Plus/Minus grading will be used for the course.
There are two components of evaluation that will collectively determine your grade.
Homeworks, exams and solutions to these will be posted on the course page (http://www.cs.uiowa.edu/~sriram/5340/fall17/) and all together these will form a significant study resource for students. Grades will be published on ICON.
Tardiness and Absences Late submissions will not be accepted and make-up exams should not be expected. To get credit for homeworks you should plan on turning in what you have on time. Having said this, it is also worth noting that this course will follow the University and College of Liberal Arts and Sciences (CLAS) policies that require that students be allowed to make up missed examinations and assignments due to illness, certain University activities, circumstances beyond a student's control (such as a death in the family), or mandatory religious obligations. See http://clas.uiowa.edu/students/handbook/attendance-absences for more details on this policy. Attendance will not be marked, however there is a strong correlation between attendance and performance in the course. For most students, to be successful in this course will require consistent attendance.
The key to completing homeworks on time is starting early and asking questions. I will be heppy to help with any questions you may have on homeworks, either by e-mail or in person. So please feel free to visit often during my office hours and if necessary, outside my office hours as well by making an appointment.
Communicating with the Instructor Asking me questions via e-mail is quite appropriate and any e-mails related to CS:5340 will be answered within 24 hours of e-mail receipt. You should make sure to include CS:5340 in the subject line to ensure that your e-mail is not consumed by spam filters. Try to state your question(s) as clearly as possible. The more easily understood you are, the more likely it is that you will receive a quick response. Occasionally I may send e-mail announcement to all students in the class at your uiowa e-mail address. Note that you are responsible for all official correspondence sent to the uiowa address and so make sure that you check this e-mail account regularly. I would also prefer receiving e-mails from your uiowa account, rather than from commercial e-mail providers (e.g., gmail or yahoo!).
Effort Level According to University guidelines, a student should expect to work for 2 hours per week (outside the classroom) for each course credit. This is a 3 credit course and so you should expect to spend on average about 6 hours per week studying lecture notes and the textbook, solving homeworks, preparing for exams, etc. However, the "6 hours per week" estimate is an average and also presupposes that you attend classes regularly, pay attention in class, and visit me with your questions during my office hours, etc.
Course Home
This course is run by the Computer Science department which is part of 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 at
http://www.uiowa.edu/~provost/deos/crossenroll.doc.
Students with disabilities
We 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 the instructor by e-mail or in person
during office hours.
For more information visit the website of Student Disability Services
at http://sds.studentlife.uiowa.edu/.
Collaboration
Your work on homework solutions can be collaborative in the following sense.
Groups of at most two students can work collaboratively on a homework.
If a homework solution is submitted by a group of two students, then both members of the group will get an identical grade for the
homework.
Homework groups may change from homework to homework.
Academic Dishonesty
Your work on homeworks may be collaborative in a limited manner, as described above
and you are, of course, welcome to discuss homework problems with me. But,
you have to be extremely careful about any other unsanctioned collaboration or help.`
For example, you are welcome to talk to classmates outside your homework group
about concepts and ideas that relate to the class, but avoid talking about specifics directly connected to
homework problems.
Also, any help you receive from online sources or books/articles (other than the textbook) should be carefully
attributed.
Of course, students are welcome (in fact, encouraged) to study together for exams.
If you are unclear about what constitutes academic dishonesty contact the instructor or consult the CLAS Code of Academic Honesty at http://clas.uiowa.edu/students/handbook/academic-fraud-honor-code.
Student Complaints
If you have any complaints or concerns about how the course is being conducted
please feel free to talk to the instrutors.
You are also welcome to get in touch with Prof. Alberto Segre,
the Computer Science department chair (alberto-segre@uiowa.edu, 319-335-1713, 14D MacLean Hall).
Consult the CLAS statement on Student Rights and Responsibilities
at
http://clas.uiowa.edu/students/handbook/student-rights-responsibilities
for more information.
Classroom Etiquette
Showing up to class late, leaving your cell phone ringer on, reading a newspaper
in class, chatting with your friends, etc., can be quite
distracting to the professor and to fellow students.
If you are in class, it is your responsibility to pay attention and to make sure that
you are not doing anything that makes it harder for fellow-students to
pay attention.
When disruptive activity occurs, a University instructor has the authority to
determine classroom seating patterns and to request that a student exit
immediately for the remainder of the period. One-day suspensions are reported to
appropriate departmental, collegiate, and Student Services personnel (Office of the Vice President for Student Services and Dean of Students).
For more information consult the CLAS statement on Student Rights and
Responsibilities at http://clas.uiowa.edu/students/handbook/student-rights-responsibilities.
University Statement on Sexual Harassment Sexual harassment subverts the mission of the University and threatens the well-being of students, faculty, and staff. All members of the UI community have a responsibility to uphold this mission and to contribute to a safe environment that enhances learning. Incidents of sexual harassment should be reported immediately. See the UI policy on sexual harassment at http://www.uiowa.edu/~our/opmanual/ii/04.htm for assistance, definitions, and the full University policy. Also see http://www.sexualharassment.uiowa.edu/ for additional resources.
Reacting Safely to Severe Weather
In severe weather, class members should seek appropriate shelter immediately,
leaving the classroom if necessary. The class will continue if possible
when the event is over. For more information on Hawk Alert and the siren
warning system, visit the Public
Safety web site at http://police.uiowa.edu/stay-informed/emergency-communication/.