600.226 DATA STRUCTURES - SPRING 2004
REVIEW TOPICS FOR FINAL EXAM
Final Exam Place & Time:
Saturday 8 May, 2-5pm, Shaffer 101 (next door to our classroom).
Practice exam:
Last year's challenging final should be excellent practice for you.
I've put 40 copies outside my office door: NEB 324A. Unfortunately
there's no official answer set. You may want to get together to
compare and discuss your answers.
Review session:
There will be a review session, probably sometime on Wednesday 3/5
(last day of reading period). General questions and questions about
the practice final are welcome.
Format:
The format of the final will be similar to the midterm and the
practice exam.
I will try not to make it overly long.
But at the same time, it will hit many of the topics below,
so that you don't feel like your studying was wasted. :-)
----------------------------------------------------------------------
General programming techniques:
You'll be expected to know how to write good code in Java. Any
coding problems will be about the same size as the DelphiOracle
problem on the practice midterm.
You'll also be expected to know how to design. You might be
asked what classes you would write and what methods they would
support for a given problem.
Class hierarchy, interfaces, method overriding, casting, etc.
Elegant code -- e.g., brief, clear, does exactly what it
should with a minimum of fuss, avoids duplication.
Safe code -- should be designed, written and documented so that
someone who is using or modifying the code will be unlikely
to make errors.
Invariants -- these should be documented and enforced
(to result in safe and correct code).
Design patterns:
You should be comfortable with pretty much all the patterns listed
under "design patterns" in the textbook's index. See the index
(p. 674 or p. 632) for where to look them up in the book:
adapter (I usually call this "wrapping a class")
amortization
brute force
comparator
composition
decorator
divide-and-conquer
dynamic programming (not on the exam - we just touched on it)
greedy method (not on the exam - we just touched on it)
iterator
locator
position
prune-and-search (similar to divide-and-conquer)
template method
You are not required to know the textbook's names for these
patterns. But you should be able to use them creatively, or think
of examples from the class.
Here are some examples of the adapter pattern:
http://cs.jhu.edu/~jason/226/hw3/ (JavaStack)
http://cs.jhu.edu/~jason/226/hw6/ (JavaComparator)
http://cs.jhu.edu/~jason/226/hw7/ (KeyIterator)
http://cs.jhu.edu/~jason/226/hw8/ (BallotPile)
http://cs.jhu.edu/~jason/226/hw10 (HashKeyedDigraph
http://cs.jhu.edu/~jason/226/hw10/source/geography/Route.java
Other design patterns not explicitly listed in the book but
covered in this course:
Function objects (Comparator, HashComparator, Weighter, ...)
Objects that implement these interfaces don't store
any data. They are really just functions that can
be stored or passed as arguments and then called later.
Hybrid implementations for efficiency. For example, using
quicksort instead of insertion sort on small lists, or using
linked lists instead of hash tables at small sizes.
Caching. For example, FastDelphiOracle on the practice midterm.
Analysis:
Big Oh notation.
Runtimes of methods for the data structures in the class,
and how to prove them.
Different implementations of the same abstract datatype,
and their efficiency tradeoffs. (One implementation may
be faster but require more space, or faster for one method
but slower for another.)
Amortized analysis (for extendable arrays).
Randomization as a defense against an adversary
(universal hashing; randomized pivot selection).
Lower bound on runtime of comparison-based sorting.
Bounds on the height of a search tree (e.g., AVL tree)
that contains n nodes.
Basic container structures: stacks, queues, deques, vectors,
lists, sequences, trees, graphs.
Methods that each datatype supports.
Implementations of each datatype using
- arrays
- linked nodes
- other basic container structures
Sample question: How would you implement an X using a Y?
Assuming such-and-such an implementation of Y, what would
be the runtime of X's methods?
Tree traversal: prefix, postfix, infix, maybe Euler
Graph traversal: depth-first, breadth-first, closest-first (Dijkstra)
Throughout the exam, you are NOT required to memorize the exact
interfaces and names used by the textbook. However, you should
know what's important. I don't care if your stack supports an
isEmpty() method ... but you'd better know the standard words push
and pop, and the fact that pop is the ONLY removal method that a
stack supports.
Priority queues:
Interface.
Entries (key/value pairs).
Implementation as heaps and the runtime of this.
Efficient bottom-up heap construction algorithm.
Adaptable (location-aware) priority queues.
Unordered dictionaries:
Implemented as sequences.
Implemented as hash tables:
bucket arrays
hash codes and compression maps
collision handling: separate chaining, the various
open addressing schemes, and their basic advantages/disadvantages
load factors and rehashing
worst-case and average-case performance of hash tables
Ordered dictionaries:
Implemented as sorted sequences (book calls these "lookup tables")
Implemented as standard tries (section 11.3.1)
Implemented as skip lists
Implemented as search trees:
unbalanced binary search trees
(2,4) trees
AVL trees
red-black trees
Search, insertion, and deletion algorithms for each of these
implementations. Don't forget binary search of a sorted
sequence!
Invariants of the different implementations.
Runtimes of the different implementations.
Other advantages/disadvantages of the different implementations.
What do AVL trees have to do with (2,4) trees?
What do red-black trees have to do with (2,4) trees?
Algorithms:
Sorting and selection
Selection sort, insertion sort, bubble sort
Merge sort, quicksort, quick select
Pivoting for quicksort
In-place sorting and pivoting methods
Bucket sort, radix sort
Knuth-Morris-Pratt pattern matching (section 11.2.3)
You do not have to know how to construct the
failure function table.
Additional graph algorithms (rough understanding is enough):
Topological sort (we discussed 3 algorithms in class)
Natural-order recomputation in spreadsheets (by topological sort)
Garbage collection (by DFS)