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)