Midterm Study Guide
CSE 373: Data Structures and Algorithms
Autumn 2002

Midterm Exam, Friday, November 8, 2002

• Exam policies
  • The midterm is closed book.
  • An 8 1/2 X 11 inch blue (or green) book is required.
  • You may put your own hand written notes in your blue book to aid you during the exam.
  • The exam begins promptly at 12:30 and ends at 1:20.
• Topics covered
  • Linked lists. Simple linked lists, doubly linked lists, sparse polynomials, unbounded integers.
  • 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.
  • 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.
  • Hashing. Find, insert, delete (lazy deletion). Hash functions for integers and character strings. Chaining. Open addressing with linear probing, quadratic probing, and double hashing. Load factors. Rehashing.
  • Binary Heaps. Insert, findmin, deletemin. Increasing and decreasing keys.
  • Binomial Heaps. Merge, insert, findmin, deletemin.
• Study suggestions
  • Do concrete problems from the book. Suggestions from chapter 2: 2.1, 2.7. Chapter 3: 3.2, 3.9, 3.10, 3.17. Chapter 4: 4.1, 4.2, 4.9, 4.11, 4.22, 4.27, 4.28, 4.36. Chapter 5: 5.1, 5.2. Chapter 6: 6.2, 6.3, 6.18, 6.31, 6.32, 6.33.
  • Do the midterm exam from 1999 (CSE 326).
  • Practice all the operations in binary search trees, AVL trees, splay trees, hashing, binary heaps, and binomial heaps. You need to know how to implement pointers with arrays (cursor implemenation of pointers). Practice analysis of algorithms.