- All Midterm Concepts
- add "heap" and "graph" to the Data Structures bullet
- also, your knowledge of hash tables will now be expected to
be more intimate, and should include:
- load factor
- linear probing, quadratic probing, double hashing
- primary clustering
- Heaps
- heap order property
- array-based implementation
- percolate-up/down operations
- insertion, deletion, buildheap
- applications: resource sharing; simulations
- Selection
- List, Tree, Heap-based selection
- Quickselect
- Sorting
- inversions, adjacent swaps
- For each sorting algorithm: Insertion Sort, Shellsort,
Heapsort, Mergesort, Quicksort, Bucketsort...
- How they work
- Running times: best, worst, average
- Best/worst case inputs
- Graphs
- terminology (directed, weighted, path, cycle, etc.)
- adjacency matrix vs. adjacency list implementations
- breadth-first, depth-first traversals
- topological orderings
- shortest path problem (Dijkstra's algorithm)
- minimum spanning tree problem (Prim's algorithm)
- Programming Projects -- be sure to be familiar with the
programming projects whether or not you did them.
Final Exam Review Session, Monday Dec 13th, 7pm, EE1 125