22C:44 Algorithms Spring 2001
Section 1: 1:052:20 TTh Room 205 MLH
Section 2: 10:5512:10 TTh, Room 214 MLH
Instructor:
Sriram V. Pemmaraju
101G MLH, 1:302:30 M and 2:303:30 Th, sriram@cs.uiowa.edu, 3532956
Teaching Assistants:
Shuquan Hou, B20J MLH, 1011 MW, shuquanhou@uiowa.edu, 3353650.
Xu Ye, B20J MLH, 34 T, 9:3010:30 F, xu@cs.uiowa.edu, 3353650.
Syllabus html, postscript,or pdf,
Final Grades. Posted 5/13.
If you are interested in picking up your final or homeworks send me email.
Announcements
 Reading for week 2 (1/221/26): Chapter 2
 Reading for week 3 (1/292/2): Sections 1.3, 3.1, and 4.1.
 Reading for week 4 (2/52/9): Sections 4.1, 4.2, and 4.3.
 Reading for week 5 (2/122/16): Section 4.3 and Chapter 7.
 Reading for week 6 (2/192/23): Chapter 7 and Sections 8.1 and 8.2.
 Reading for week 7 (2/263/2): Sections 8.1, 8.2, and 8.3.
 Reading for week 8 (3/53/9): Chapter 10.
 Reading for week 10 (3/193/23): Sections 12.1 and 12.2.
 Reading for week 11 (3/253/30): Sections 12.3 and 12.4.
 Reading for week 12 (4/24/6): Sections 17.1 and 17.2.
 Reading for week 13 (4/94/13): Sections 17.2 and 17.3.
 Reading for week 13 (4/164/20): Sections 5.4, 23.1, and 23.2.
 Reading for week 14 (4/234/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, 68 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, 122 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.