22C:153 Design and Analysis of Algorithms

2:30-3:45 TTh Room 205 MLH

Instructor: Sriram V. Pemmaraju
101G MLH, sriram@cs.uiowa.edu, 319-353-2956
Office Hours: TTh 1:00-2:30

This is our department's core graduate course in algorithms and in this offering we will focus on some of the newer algorithmic techniques such as randomization, connections to linear programming, and approximation algorithms.

Prerequisite
C- or better in 22C:34 and 22C:44
It is extremely important that you know the material in 22C:34 and 22C:44 well before taking this class. I will not review any of this material in 22C:153. If you think this material is unfamiliar to you, I suggest you review it before the semester starts. I will hand out an exam on the first day of classes (Tuesday, January 21st) due back on Thursday, January 23rd that is based on this background material. This exam is worth 0 points and is meant as a self-evaluation; depending on how well you do in the exam, you should evaluate whether you want to stay on in the class.

Textbook
T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, second edition, MIT Press and McGraw Hill, 2001, ISBN 0-07-013151-1

Supplementary Books

R. Motwani and P. Raghavan, Randomized Algorithms, Cambridge University Press, 1995, ISBN 0-521-47465-5
C. H. Papadimitriou and K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity, Dover 1998, ISBN 0-486-40258-4
V. V. Vazirani, Approximation Algorithms, Springer, 2001, ISBN 3-540-65367-8

Grading There are three components that will determine your grade.

4 Homeworks: 32% You will have 2 weeks to work on each homework.
1 Programming Project: 18% I will hand out a programming project at the semester midpoint and it will be due back on the last day of classes.
2 Exams: 50% There will be one mid-term exam and one final, each worth 25%. The mid-term will be a take-home exam which will be handed out on March 11th and will be due back on March 13th. The final exam is scheduled for May 13th, 7:30-9:30 am, in 205 MLH. This will be an open book/notes exam and it will be cummulative (that is, it will cover the entire syllabus).

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. 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 Abscences from Examinations".

Students with disabilities
I need to hear from anyone who has a disability, which may require some modification of seating, testing or other class requirements so that appropriate arrangements may be made. Please see me after class or 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 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. 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.

List of Topics

Randomized Algorithms: Chapters 5, 7, 9 from the textbook, and Chapter 10 from Motwani & Raghavan.
Dynamic Programming: Chapter 15 from the textbook.
Maximum Flow: Chapter 26 from the textbook.
Bipartite Matching: Chapter 10 from Papdimitriou and Steiglitz.
Linear Programming (LP): Chapter 29 from the textbook.
Weighted Bipartite Matching: Chapter 11 from Papdimitriou and Steiglitz.
NP-Completeness: Chapter 34 from the textbook.
Approximation Algorithms: Chapter 35 from the textbook.