Final Study Guide

• Exam policies
  • Closed book, closed notes.
• Topics
  • All material from lecture is fair game.
  • This material corresponds to: Chapters: 1-9, and 10.3.4
  • Here is a (fairly complete, but not exhaustive) summary of topics we've covered in lecture:
    • Linked lists. Simple linked lists, doubly linked lists, circularly linked lists.
    • Stacks and Queues, array and list implementations.
    • Recursion. Designing algorithms recursively.  Inductive proof.
    • Asymptotic analysis, Big-O. Worst, amortized, average, best cases.  Upper and lower asymptotic bounds.  Analyzing loops, recurrences.
    • Trees - definitions
    • Binary Heaps, D-heaps - Findmin, Deletemin, Insert. Additional operations of increaseKey, decreaseKey, buildHeap.
    • Leftist Heaps and Skew Heaps - Findmin, Deletemin, Insert. Additional operations of merge, increaseKey, decreaseKey
    • Binomial Queues - Findmin, Deletemin, Insert. Additional operations of merge, increaseKey, decreaseKey.
    • Dictionary ADT
    • Binary search trees - Inorder, preorder, postorder traversals, insert, delete, find, build.
    • AVL trees - Single and double rotations, insert, find, delete, build.
    • Splay trees - Splaying: zig, zig-zig, and zig-zag rotations, insert, find, delete, build.
    • B trees - motivation, basic operations.
    • Hashing. Properties of good hash functions. Selecting hash table size. Separate chaining and open addressing. Linear Probing, Quadratic Probing, & Double Hashing to resolve collisions. Rehashing.
    • Sorting. Insertion sort, Selection sort, Heap sort, Merge sort, quicksort. In-place sorting. Stable sorting.
    • Bucket sort, Radix sort.
    • Lower bound on comparison sorting.
    • Disjoint Union/Find - Up-trees. Weighted union (union by size) and path compression.
    • Graphs. Directed and undirected. Adjacency list and adjacency matrix representations. Edge and vertex complexities.
    • Topological sorting.
    • Graph searching (just the ideas on these - don't have to be able to execute). Depth-first, breadth-first, best-first, A* search, Floyd-Warshall
    • Shortest paths. Dijkstra's algorithm for SSSP.
    • Minimum spanning tree: Prim's and Kruskal's algorithms
       
  • The focus will be on ideas/concepts about data structures and algorithms, not Java.
     

• Study suggestions
  • Do concrete problems from the book and re-work problems from lecture, section, and HW.
  • Practice all the operations on the data structures.
  • Practice analysis of algorithms.  Learn and be able to reason about the complexities of operations on the data structures we've discussed in class.
  • Try practice finals.
     
• Practice finals (which cover some topics that we did not):
  • Winter 2007
  • Spring 2007
  • Autumn 2007