Final Exam. The final will be a
cumulative closed-book exam. Just like the midterm, but half
again
as long. A sample final (with
solutions) is
available.
12/12/96, 7:00pm, in AKW 500
Review session.
12/6/96
Retrospective. Where to go from here.
12/4/96
Binary trees.
12/2/96
Recursive search procedures.
11/22/96
More examples of divide-and-conquer. Algorithms and their
worst-case costs. Binary search and mergesort.
Abstract data types. Concrete representations vs
abstractions. Dictionaries and stacks.
Readings:
Sections 15.1, 15.4-15.6
11/13/96
Hash tables. A hash table is a trick for speeding up access
to the elements of a linked list by splitting the list into many
separate lists (stored in an array). To find out which list
each element goes in, one uses a hash function that
transforms each element into a consistent but random-looking
number. The effect is a bit like using a filing cabinet with
many separate folders to store data instead of one big stack of
paper. See the demo program for an example.
monet. A
formerly huge drawing of a smiley-face, signed by the master.
This is a compressed version of the test file
drawn in class. The compression was done on a Unix machine
using a program written in Perl, which
demonstrates how data files with well-defined formats can be
manipulated by a wide variety of tools.
conquest.p This
program didn't appear at all in lecture, but I wrote it
beforehand while playing around with enumerated data types, and
it has some nice examples of doing things with them and 2-d
arrays. So I figured it would make more sense to put it up here
than let it go to waste.
10/18/96
Multi-dimensional arrays and their uses.
Readings:
Section 11.9. Ignore the discussion in Section 11.8 on
parallel arrays. The technique
discussed there is almost always better done with an array
of records as described in Section 12.2.
toxic.p
(This version is slightly improved from the one shown in
lecture; it includes a version of ButtonClick that works
better.)
10/16/96
Midterm. The midterm will be give in class
at the usual time and location. It will be a closed-book
test, covering everything discussed in class up to 10/11/96.
You should be comfortable with the material in Chapters 1, 2, 3
(Sections 3.1-3.4 only), 4, 5, 6, and Sections 11.1-11.4 and
12.1 and 12.2 in the book. A sample
midterm is available showing roughly the length and types
of questions you should expect; you may wish to try going through
this before the review session to see if you have any
questions. Note that questions on the sample midterm are not
exhaustive: the real midterm may touch on different subjects and
use different types of questions.
Procedures with state. Most procedures maintain no
information from one call to the next, so they always act
exactly the same way. Sometimes this isn't what we want, so by
used of a global variable or a call-by-reference parameter we
can produce procedures like iterators (returning
e.g. 1,2,3,4,5, etc.) or pseudorandom number
generators (which return random-looking numbers; see also
the library of useful
procedures).
10/2/96
Examples of using call-by-reference parameters and
functions. Getting input from the mouse.
Sections 1.8 (simple procedures), 2.12 (constants), 6.1
(procedures with parameters). You should probably also
read Sections 2.10 and 2.11 (input and output).
9/4/96
Introduction. How the course is set up.
What programming is all about. Running Think Pascal.