Midterm Study Guide
CSE 326: Data Structures
Winter 2008

Midterm Exam, Wednesday, February 13, 2008

• Exam policies
  • You may bring your own notes and the text book to the midterm.
  • The exam begins promptly at 12:30 and ends at 1: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.
  • The memory hierarchy. Programming for the memory hierarchy. Temporal and spacial locality. Prefetching.
  • 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. Findmin, Deletemin, Insert. Additional operations of merge, increase, decrease.
• Study suggestions
  • Do concrete problems from the book.
  • Do the relevant questions from the midterm exam from Autumn 2005.
  • Practice all the operations in binary search trees, AVL trees, splay trees, B-trees, k-d trees, and quad trees, binary heaps. You need to know how to implement pointers with arrays (cursor implemenation of pointers). Practice analysis of algorithms.