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 general--I 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:

• See the Study Guide for the Second Midterm
• Gender issues will not be covered. If you are sexist there is little I can do to cure you.
• The most important areas to review are ADTs I and II, Java I/O (especially Serialization), and everything about Collections.
• Don't ignore Comparisons.

For the final third of the semester:

• You should understand the basic concepts of Trees, Graphs, Spanning Trees, and Priority Queues.
• You should know how to traverse and search both Binary Trees and general Trees.
• You should be able to extend tree traversal and search techniques to graphs. Other graph algorithms are not particularly important.
• You should understand Backtracking.
• You should know the basic algorithms for both Heapsort and Quicksort.
• You should know what a State Space is, and how to search one.
• You should know the terms for various Types of Algorithms.
• Alpha-beta searches and Animation will not be covered.