CSE 373 Midterm Exam 2 Topics (Autumn 2008)
- Equivalence relations and partial orders (also covered in
Midterm 1).
- B-trees (comparing access times for RAM and magnetic disks; B-tree definitions according to Weiss; insertion, deletion).
- Hashing, including hash functions, surjections,
separate chaining, probing, rehashing, lazy deletion,
load factors, Dictionary ADT.
- Priority queues and binary heaps, including complete binary
trees, INSERT, DELETEMIN, BUILDHEAP, and the worst-case running
times of these operations.
- Sorting, including simple Insertion Sort, simple Selection Sort,
Heapsort, Merge Sort, and Quicksort, stability of a sorting method, in-place sorting, Bucket Sort, Radix Sort, the n log n lower bound on the number of comparisons for sorting n keys.