Study Guide for the Final Exam
Spring 2002, David Matuszek

The final exam will be comprehensive, with emphasis placed on the more
recent material (after the second midterm).
My goal is to have roughly
 25% from material presented before the first midterm,
 25% from material presented between the midterms, and
 50% from the material presented after the second midterm.
These numbers refer to questions about specific data structures and algorithms.
They are not intended to be exact percentages, or any sort of guarantee.
Some of the questions are likely to involve applying the concepts that
have been developed throughout the semester, rather than requests for specific
information; these questions cannot be assigned to any particular part of the
semester.
Some questions, perhaps 10  15% of the total, will be from The Pragmatic
Programmer (all chapters). Questions will be fairly generalI want
to make sure you read the book, not memorized it.
For the first third of the semester:
 Review Lisp.
 Be sure you understand Recursion.
 The most important thing about Arrays
is to realize that they can be implemented in many different ways, with many
different features, and every language has its own notion of what an array
should be.
 The Simple
Sorting techniques are not important, but they are used as examples of
Analysis of
Algorithms, which is important.
 You should know what Linked
Lists, Binary
Trees, Stacks,
Queues
and Deques are, and you should know how to implement them, but the specific
implementations given in the slides are not very important.
 You should know what Hash
Tables are, and understand the two main kinds of implementation.
 Abstract Data Types
are very important. You should be able to define a reasonable ADT for any
type of data structure. (See also ADT
II).
For the second third of the semester:
For the final third of the semester: