About the exam

Friday 8 May, 2-5 pm in the usual lecture room (Collins 408)

resources: lecture notes, class hand-outs, previous exam review, lab assignments, on-line materials (thanks, Wikipedia!)

exam will be three hours, closed book/notes and cumulative (but stressing second half of course)

typical format: some T/F, some short answer, a few longer "conceptual" questions

Review the midterm notes here ...

Random Access lists

Heaps and priority queues

priority queue is an interface which allows for prioritized removal

can be implemented poorly using linear queues with prioritization on addition or extraction

can be implemented better using a tree-like structure: heaps

structural property: left-complete binary tree

ordering property: node values above are greater than those below

yields log time on both insertion and extraction

can be implemented in an array

AVL and Splay trees

idea: try to keep the tree bushy

use rotations to re-adjust the tree

rule: height difference between children at most 1

for insertions: may require one single or double rotation on the way out

for deletion: may require multiple rotations back toward root

splay trees: rotate every node inserted or inspected to root of tree

(keeps oft-accessed items toward the top)

Sorting algorithms

basic ideas

insertion, selection, bubble

tree, quick, merge, (heap)

a general framework

breakdown by one-many or half-half

hard insert/easy remove OR easy insert/hard remove

Hash tables

the dictionary interface: lookup values according to keys

can be implemented in linear (ordered or unordered) lists, or in binary search trees

hash function computes a number from a key

store hashed values in an array

collision resolution: external chaining or internal "open addressing" (probe for new spot)

Graphs

a generalization of trees: no root, possible loops, possible sharing, may be undirected

abstractly, a set of nodes (vertices) and a set of edges

several representation choices (adjacency lists, adjacency matrix)

algorithms often modify the graph

we looked at depth-first search