Final Exam Study Guide
CSE 326: Data Structures
Autumn 2005

Final Exam, 2:30-4:20 p.m. Wednesday, December 14, 2005

• Exam policies
  • You may bring your own notes and the text book to the final.
  • The exam begins promptly at 2:30 and ends at 4:20.
• Topics covered
  • Linked lists. Simple linked lists, doubly linked lists, sparse polynomials. Cursor implementation of pointers.
  • Stacks and Queues, array and list implementations.
  • Recursion. Designing algorithms recursively, using call by reference.
  • Analysis of algorithms. Worst case, average case, upper bound, lower bound, analyzing loops, recurrences, amortized complexity.
  • Sorting. Insertion sort, quicksort, mergesort, multi-mergesort.
  • The memory hierarchy. Programming for the memory hierarchy. Temporal and spacial locality.
  • Trees and traversals. Multiway trees, preorder, postorder.
  • Binary search trees. Inorder traversal, insert, delete, find.
  • AVL trees. Single and double rotations, insert, delete, find.
  • Splay trees. Splaying, insert, delete, find.
  • B-trees. Split for insert, borrow and merge for delete.
  • K-d trees and quad trees. Range queries and nearest neighbor search.
  • Binary Heaps and Binomial Queues. Findmin, Deletemin, Insert. Additional operations of merge, increase, decrease.
  • More Sorting. Radix sort. Lower bound on sorting. In-place sorting. Stable sorting.
  • Disjoint Union/Find. Up-trees. Weighted union and path compression.
  • Graphs. Directed and undirected. Adjacency list and adjacency matrix representations.
  • Topological sorting.
  • Graph searching. Depth-first, breadth-first search, best-first search, A* search.
  • Shortest paths. Dijkstra's algorithm.
  • Euler paths and circuits.
  • Hashing. Hash functions. Chaining and closed hashing. Extendible hashing.
  • P and NP. NP-complete problems.
  • Minimum spanning tree
  • Dictionaries for data compression, LZW, LZ77.
• Study suggestions
  • Do concrete problems from the book. Suggestions from:
    Chapter 2: 2.2, 2.3, 2.6, 2.7, 2.10.
    Chapter 3: 3.4, 3.5, 3.11, 3.21.
    Chapter 4: 4.1, 4.2, 4.9, 4.11, 4.22, 4.28, 4.36.
    Chapter 5: 5.1, 5.10, 5.11, 5.13,
    Chapter 6: 6.2, 6.3, 6.13, 6.29, 6.30.
    Chapter 7: 7.1, 7.15, 7.19, 7.39; 7.48. Chapter 8: 8.1.
    Chapter 9: 9.1, 9.2, 9.10, 9.15, 9.20, 9.53 Chapter 12: 12.22 12.26.
    
  • Do the relevant questions from the final exam from Winter 2005.
  • Practice all the operations in binary search trees, AVL trees, splay trees, B-trees, k-d trees, and quad trees, binary heaps, and binomial queues, hashing with linear probing, quadradic probing, and double hashing, disjoint union / find with weighted union and path compression. Be able to execute basic graph search algorithms and minimum spanning tree. Be able to execute sorting algorithms mergesort, quicksort, heapsort, insertion sort, and radix sort. Be able to execute the data compression algorithms LZW and LZ77 and understand their data structures. You need to know how to implement pointers with arrays (cursor implemenation of pointers). Practice analysis of algorithms.