22C:153 Design and Analysis of Algorithms

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.

Syllabus document, Information about TAs, Announcements, Homeworks and Exams

Information about TAs

	Office: 101 L, MLH, Phone: 353-2543
	e-mail: jkodali@cs.uiowa.edu
	Office Hours: MWF 3:30-4:30

Homeworks and Exams

• self-evaluation exam (pdf). Due back on Thursday, 1/23.
• solutions to the self-evaluation exam (pdf).
• Homework 1 (pdf). Due back on 2/25.
• Solution to Homework 1 (pdf).
• Homework 2 (pdf). Due back on 3/25.
• Exam 1 (pdf). Due back on 3/18.
• Programming project (pdf). Due back on 5/9.
• Solution to Homework 2 (pdf).
• Scores thus far: scores
• Homework 3 (pdf). Due back on 5/13.
• About the Final.

Announcements

• Reading for Week 1 (1/20-1/24) Sections 5.1, 5.2, and 5.3. Sections 7.1, 7.2, and 7.3.
• Reading for Week 2 (1/27-1/31) Sections 9.1 and 9.2. Sections 1.1 and 10.2 from Motwani and Raghavan.
• Reading for Week 3 (2/3-2/7) Chapter 15.
• Reading for Week 4 (2/10-2/14) Section 16.2 (on the knapsack problem) and Chapter 8 from Vazirani.
• Reading for Week 5 (2/17-2/21) Sections 26.1, 26.2, and 26.3 (on the max-flow problem).
• Reading for Week 6 (2/24-2/28) Sections 9.4 and 9.5 from Papadimitriou and Steiglitz (on the max-flow problem).
• Reading for Week 7 (3/3-3/7) Sections 10.1, 10.2, 10.3, 11.1, and 11.2 from Papadimitriou and Steiglitz (on bipartite matching).
• Mid-term exam The schedule on the syllabus for this is: handed out on March 11, due back on March 13. To give you a little more time for the exam, let us go with the schedule: handed out on March 13, due back on March 18.
• Reading for Week 8 (3/10-3/14) Sections 10.1, 10.2, 10.3, 11.1, and 11.2 from Papadimitriou and Steiglitz (on bipartite matching).
• Homework 2 is due back on 3/25.
• Reading for Week 9 (3/24-3/28) Sections 10.1, 10.2, 10.3, 11.1, and 11.2 from Papadimitriou and Steiglitz (on bipartite matching).
• Reading for Week 10 (3/31-4/4) The introductory section in Chapter 29, Sections 29.1, 29.2, and 29.4 (without the proof of strong duality).
• Reading for Week 11 (4/7-4/11) Sections 34.1, 34.2, 34.3, and 34.4.
• Reading for Week 12 (4/14-4/18) Sections 34.5, 35.1, and 35.2.
• Change in office hours Starting on April 17th, my office hours for the rest of the semester will be: 10:30-12:00 on Tuesdays and Thursdays.
• Scores thus far: scores
• NEOS Server for Optimization: If you want to have large LPs solved.
• Reading for Week 13 (4/21-4/25) Sections 34.5, 35.1, and 35.2.
• Reading for Week 14 (4/28-5/2) Sections 35.1, 35.3, and 35.4 and Chapters 14 and 15 from Vazirani.
• Reading for Week 15 (5/5-5/9) Sections 35.1, 35.3, and 35.4 and Chapters 14 and 15 from Vazirani.