22C:31 Algorithms

10:55-12:10 TTh Room 218 PH (Phillips Hall)

Instructor: Sriram V. Pemmaraju
101G MLH, sriram@cs.uiowa.edu, 319-353-2956
Office Hours: 9-10:30 MW
Course website: http://www.cs.uiowa.edu/~sriram/31/spring10/

This course deals with the design and analysis of algorithms. We will study algorithm design techniques such as greedy method, dynamic programming, divide-and-conquer, and randomization and see many examples of each of these techniques in action. We will study algorithm analysis techniques such as asymptotic analysis, recurrence relations, and charging schemes. Towards the end of the course, we will also study the intractability of problems, specifically the theory of NP-completeness. Time permitting, we will study approximation algorithms as a way of getting around the intractability of some problems.

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.

C- or better in 22C:21 and 22M:025 or 22M:031


The textbook for this course is Algorithm Design by Kleinberg and Tardos (see this for more details).

Teaching Assistant

There may be a Teaching Assistant (TA) assigned to this course. We'll find out soon. The TA's primary responsibilities will be to grade homeworks that you submit and hold office hours (3 hours per week) to provide help on homeworks and material being covered in the lectures. More details regarding the TA will be posted as soon as I find out.

Course Accounts

For this course, it will be helpful if you have an account on computer science machines. Most of you already have such accounts; the rest of you will get CS accounts by the end of the first week. You will also need a HawkID and a password to login to ICON to electronically submit your assigned work.

Plus/Minus grading will be used for the course. There are the three components that will determine your grade.

Late submissions will not be accepted and in general you will be better off turning in what you have on time rather than seeking extra time to complete your work. Starting early is the key, and the TA and I will be glad to help with any questions you may have on the assignments. So please visit us often during our office hours and if necessary, outside our office hours as well. There will be no make-up exams in general and exceptions will be rare and only for students whose reasons are included in the University's policy on "Excused Absences from Examinations".

Solutions will be provided on the course page for all the homeworks.

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 policy in 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.

Tentative List of Topics