Midterm Study Guide
CSE 326: Data Structures
Autumn 2005

Midterm Exam, Friday, November 4, 2005

• Exam policies
  • You may bring your own notes and the text book to the midterm.
  • The exam begins promptly at 11:30 and ends at 12: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.
• 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 6: 6.2, 6.3, 6.13, 6.29, 6.30. Chapter 12: 12.22 12.26.
  • Do the relevant questions from the midterm 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. You need to know how to implement pointers with arrays (cursor implemenation of pointers). Practice analysis of algorithms.