Date: Wed, 20 Nov 1996 23:18:35 GMT
Server: NCSA/1.5
Content-type: text/html
22C:21 Home Page
22C:21 Algorithms and Data Structures --- Spring 1996
MWF 1:30, Jessup Hall 221
PROFESSOR: Jim Cremer, 201N MacLean, E-mail: cremer@cs.uiowa.edu, Office hours: 2:30-3:30 T, 10:30-11:30 F, or by appointment
TA: Jun Tu, 255D McBride, jun@cs.uiowa.edu, Office Hours: 3:30-4:30 W, 1:30-2:30 Th
WHAT'S NEW (Last updated Monday, 5/13/96)
- Complete scores for the semester and the mapping from scores to
course letter grades are available in the Grades
section. To see or pick up your graded final, please stop by my
office.
22C:17, 22C:18, and 22C:19 (or permission of instructor)
The aim of the course is to gain experience with the major paradigms and data
structures used in creating algorithms, and with basic methods for analyzing
the time and space requirements of programs. We will cover most of the textbook.
The tentative schedule is:
Week 1 Intro and Ch 1 (math background, induction, recursion)
Week 2 Ch 2 (algorithm analysis notation and techniques), a bit of 7.6 and 10.2
Week 3 quick review of Ch3, Ch 4 (trees)
Week 4 Ch 5 (hashing)
Weeks 4 and 5 Ch 6 (priority queues)
Week 6 Ch 7 (sorting)
Week 7 (February 28) Exam 1,in class
Weeks 7 and 8 Ch 8 (disjoint sets)
Weeks 8 and 9 Ch 9 (graphs)
Week 10 SPRING BREAK
Week 11 Ch 9 (graphs), including a bit extra on decidability, tractability, complexity
Weeks 12 and 13 Ch 10 (algorithm techniques), including greedy methods, dynamic
programming, more divide-and-conquer
Week 14 (April 17) Exam 2, in class
Week 15 Ch 10.5 backtracking search/games (TENTATIVE)
Week 16 Ch 11 (amortized analysis)
May 10 (Friday) FINAL EXAM, 9:45 a.m.
Weiss, Data Structures and Algorithm Analysis, Benjamin-Cummings, Second Edition, 1995.
Supplemental Books (on reserve in Math Library)
Cormen, Leiserson, and Rivest, Introduction to Algorithms, McGraw-Hill, 1990
Aho, Hopcroft, and Ullman, Data Structures and Algorithms, Addison-Wesley, 1983
Course grades will be based on ten (or so) homework sets, two
midterm exams, and the final exam. There will be some small
programming assignments. Programming problems will usually be given
as part of regular written homework assignments; there will not be a
separate grading category for programming assignments. Class
participation and effort may be taken into account in determining grades in
borderline situations. The components will be weighted roughly as
follows:
Homeworks assignments 35%
Midterm exams 20% each
Final exam 25%
All assignments are due at the beginning of class. In other cases,
assignments turned in within 24 hours will receive a 20% penalty, and
those turned in 24 to 48 hours late will receive a 50% penalty.
(Exception --- each student may turn in one homework assignment up to
two days late with no penalty.) Regrade requests must be made within
one week of when the assignments are returned in class.
Homework and programming assignments should be done alone. It is
reasonable to discuss general approaches to problem solution or
algorithm design with other students but the bulk of the work
must be done alone. Working out details, sharing in the write-up
or sharing or copying code will be treated as a violation of the
academic integrity rules.
Program source code in the book is in Pascal. However, for course
programming assignments, you will be free to use your choice of Pascal, C, or
C++ (or another language if approved by the instructor).
- Homework 8 (HTML version).
Homework 8 (Postscript version).
- Official test data for Homework 8 (must turn in
runs of your program on these files):
wordlist1,
wordlist2,
wordlist3
Some other test data for Homework 8:
extra-wordlist1,
extra-wordlist2,
extra-wordlist3
- Homework 7 (HTML version).
Homework 7 (Postscript version).
- Homework 6 (HTML version).
Homework 6 (Postscript version).
- Official test data for Homework 6 (must turn in
runs of your program on these files):
circuit1,
circuit2,
circuit3,
circuit4
path1,
path2,
path3
Some other test data for Homework 6:
testdata11,
testdata2,
testdata3
testdata4,
testdata5,
testdata6
- Homework 5 (HTML version).
Homework 5 (Postscript version).
- Homework 4 (HTML version).
Homework 4 (Postscript version).
- Homework 3 (HTML version).
Homework 3 (Postscript version).
- Homework 2 (HTML version).
Homework 2 (Postscript version).
- Homework 1 (Postscript file).
For those who can't view or print Postscript, here's
an HTML (the basic WWW language) version
Homework 1.
- Course grades:
Total score:
> 460 A+
415 - 459 A
400 - 414 A-
390 - 399 B+
385 - 389 B
370 - 379 B-
350 - 369 C+
320 - 349 C
270 - 319 C-
250 - 269 D
< 250 F
NOTE: the two highest scorers were graduate students. The allocation of
letter grades for the rest of the class was done independently of their scores.
- Complete homework and exam scores, including final.
Sorted by ID number. (plain text file)
- Complete homework and exam scores, including final.
Sorted by total score. (plain text file)
- Final Exam data. Median: 87. Mean: 87. High 115.
Score range Number of people
> 110 2
101 - 110 6
91 - 100 4
81 - 90 9
71 - 80 10
<= 70 4
- Exam 2 data. Median: 72. Mean: 71.9. High 97.
Score range Number of people
> 95 2
81 - 90 7
71 - 80 11
61 - 70 9
<= 60 6
- Exam 1 data. Median: 80/81. Mean: 76.0. High 98.
Score range Number of people
> 90 5
81 - 90 13
71 - 80 7
61 - 70 2
<= 60 9
- Homework 8 solutions (HTML version).
Homework 8 solutions (Postscript version).
- C++ code for Question 2 on Homework 8. Code is not commented and does
not quite meet the specifications for Question 2 (it reads the input interactively
rather than from a file, handles only single character "words", and prints
the tree in preorder rather than level order), but the important part, the
one that fills in the table used to calculate the optimal binary search tree,
is as it should be.
There are two ASCII files - obst.H
and obst.C.
- Exam 2 solutions (HTML version).
Exam 2 solutions (Postscript version).
- Homework 7 solutions (HTML version).
Homework 7 solutions (Postscript version).
- Homework 6 solutions (HTML version).
Homework 6 solutions (Postscript version).
- Homework 5 solutions (HTML version).
Homework 5 solutions (Postscript version).
- Homework 4 solutions (HTML version).
Homework 4 solutions (Postscript version).
- Sample exam that might help you see the style of questions you'll get
on Exam 1 (Wed., Feb. 28). The exam was given at about this point in
the course during the fall semester, 1993. The document here contains
two extra questions that were not actually used on the exam.
Sample exam in HTML
Sample exam in Postscript
- Homework 3 solutions (HTML version).
Homework 3 solutions (Postscript version).
- Implementation of heap routines in C++
Maybe useful for last question on Homework 4. Pascal code is available
via ftp site listed in beginning of textbook.
- Homework 2 solutions (HTML version).
Homework 2 solutions (Postscript version).
For code for the MAJORITY problem of Homework 2, see the item below.
- C implementations of solution to MAJORITY problem of Homework 2.
Linear-time recursive divide-and-conquer method
maj-by-d-and-c.c, very short simple linear-time scanning method
maj-by-scan.c. Code to help generate
test data for the MAJORITY problem -
gen-maj-test-data.c. A number of test data files are contained
in the directory etc/maj-test-data.
Files: etc/maj-test-data/maj-data-1,
etc/maj-test-data/maj-data-2,
etc/maj-test-data/maj-data-3,
etc/maj-test-data/maj-data-8,
etc/maj-test-data/maj-data-16,
etc/maj-test-data/maj-data-100,
etc/maj-test-data/maj-data-1000a,
etc/maj-test-data/maj-data-1000b,
etc/maj-test-data/maj-data-1000c,
etc/maj-test-data/maj-data-1000d.
Source code is basic C. Only tested on Silicon Graphics workstation
runing IRIX (Silicon Graphics' Unix). The two MAJORITY implementations
should compile fine on other machines/compilers (e.g. just
use cc -o maj-by-scan maj-by-scan.c). The gen-maj-test-data.c code
contains a call to drand48, which is, I'd guess is a Unix specific
random number generator. It should be easy to change the code to
run elsewhere, however.
- Homework 1 solutions (HTML version).
Homework 1 solutions (Postscript version).