22C:44 Algorithms Spring 2001

Instructor: Sriram V. Pemmaraju
101G MLH, 1:30-2:30 M and 2:30-3:30 Th, sriram@cs.uiowa.edu, 353-2956

Teaching Assistants:
Shuquan Hou, B20J MLH, 10-11 MW, shuquan-hou@uiowa.edu, 335-3650.
Xu Ye, B20J MLH, 3-4 T, 9:30-10:30 F, xu@cs.uiowa.edu, 335-3650.

Syllabus html, postscript,or pdf,

Final Grades. Posted 5/13. If you are interested in picking up your final or homeworks send me e-mail.

Announcements

• Reading for week 2 (1/22-1/26): Chapter 2
• Reading for week 3 (1/29-2/2): Sections 1.3, 3.1, and 4.1.
• Reading for week 4 (2/5-2/9): Sections 4.1, 4.2, and 4.3.
• Reading for week 5 (2/12-2/16): Section 4.3 and Chapter 7.
• Reading for week 6 (2/19-2/23): Chapter 7 and Sections 8.1 and 8.2.
• Reading for week 7 (2/26-3/2): Sections 8.1, 8.2, and 8.3.
• Reading for week 8 (3/5-3/9): Chapter 10.
• Reading for week 10 (3/19-3/23): Sections 12.1 and 12.2.
• Reading for week 11 (3/25-3/30): Sections 12.3 and 12.4.
• Reading for week 12 (4/2-4/6): Sections 17.1 and 17.2.
• Reading for week 13 (4/9-4/13): Sections 17.2 and 17.3.
• Reading for week 13 (4/16-4/20): Sections 5.4, 23.1, and 23.2.
• Reading for week 14 (4/23-4/27): Sections 25.1, 25.2, 25.3.

Homeworks

• Homework 1: postscript and pdf. Due on Thursday, 2/1.
• Homework 1 Solution: postscript and pdf.
• Homework 2: postscript and pdf. Due on Tuesday, 2/13.
• Homework 2 Solution: postscript and pdf.
• Homework 3: postscript and pdf. Due on Thursday, 2/22.
• Homework 3 Solution: postscript and pdf.
• Homework 4: postscript and pdf. Due on Tuesday, 3/20.
• Homework 4 Solution: postscript and pdf.
• Homework 5: postscript and pdf. Due on Thursday, 4/5.
• Homework 5 Solution: For Problem 1, the C++ program and files for asscociated classes are: hw5.C, vector.h, ctimer.h, ctimer.cpp, randgen.h, and randgen.cpp. I used the g++ compiler on a Linux PC to compile and run the program. The vector class, ctimer class, and randgen class were all available at this site. The solution for Problem 2 is here: postscript and pdf.
• Homework 6: postscript and pdf. Due on Tuesday, 4/17.
• Homework 6 Solution: postscript and pdf.
• Homework 7: postscript and pdf. Due on Tuesday, 5/1.
  IMPORTANT: Problem 1 in Homework 7 is wrong. The given greedy algorithm does not compute the optimal solution and so you cannot prove that it does. Instead devise a counterexample to show that the given greedy does not always produce an optimal solution.
• Homework 7 Solution: postscript and pdf.
• Homework 8: postscript and pdf. Due on Tuesday, 5/8.
• Homework 8 Solution: postscript and pdf.

Exams

• The midterm is scheduled for Wednesday, March 7, 6-8 pm in 1505 Seaman's Center. Here are more details.
• The solution to the midterm is here (postscript) and here (pdf).
• The final is scheduled for Wednesday, May 9, 12-2 pm in 1505 Seaman's Center. Here are more details.

Handouts

• Some experiments with sorting: postscript, pdf
• Practice problems (postscript and pdf) and solutions (postscript and pdf) on asymptotic notation.
• Practice problems (postscript and pdf) and solutions (postscript and pdf) on analyzing iterative and recursive functions and on solving recurrences.
• Practice problems (postscript and pdf) and solutions (postscript and pdf) on solving recurrences and heaps. Ignore Problems 2 and 3 since they deal with probability theory, a topic we have not covered in class, this semester.
• Practice problems (postscript and pdf) and solutions (postscript and pdf) on heaps and quick sort. The solution to Problem 1 has an obvious error; make sure you spot it.
• Practice test problems (postscript and pdf). Unfortunately, the solutions to this exam do not seem to exist.
• Practice problems (postscript and pdf) and solutions (postscript and pdf) on quick sort, heaps, and selection.
• Practice problems (postscript and pdf) and solutions (postscript and pdf) on hashing.
• Practice problems (postscript and pdf) and solutions (postscript and pdf) on hashing and dynamic programming. Ignore the problems on dynamic programming.
• Practice problems (postscript and pdf) and solutions (postscript and pdf) on greedy algorithms and graph representation.
• Practice problems (postscript and pdf) and solutions (postscript and pdf) on graph traversals.