Topics for the Final
The final exam is in principle cumulative. That is, it will cover all
the semester. In particular you should know the complexity of each
algorithm and be able to explain why the complexity is what you say it is.
Some of the data structures involve algorithms that reshape the structure of the
object. You should know how to do these algorithms. I have marked these
algorithms that you should know and be able to trace by **
Hashing
String hashCode()
horner's **
a string as a number expressed base
37
lazy deletes
linear probing
insert algorithm **
expected probe sequence length for
successful and unsucessful probes as function of load factor. You need not
memorize any formulas but should be able to apply them.
primary chaining
quadratic probing
insert algorithm **
Trees
terms
binary trees
Huffman code algorithm **
traversals--pre-order, post-order, in-order, level-order **
recursion and binary trees using static methods
binary search trees
inserts **
deletes **
find
complexity of all methods in best,
worst and average cases.
internal and
external path lengths **
AVL trees
insert algorithm
with balance fields and rotations **
red-black trees
defining
conditions
(forget the
insertion algorithm)
aa-trees
defining
conditions
level order
insertion
with skews and splits **
TreeSet and TreeMap implementations
Tree iterators
B-trees of order m
insertion algorithm **
how to pick m and l given block size etc.
Priority queue with a binary heap
insert, remove, form-heap
algorithms**
complexity
heap sort
Java 5.0 -- Some new features
Recursion and efficient exponentiation **
Randomized algorithms -- Pseudo primes
Graphs
definitions
Java representation
unweighted shortest path **
positive weighted shortest path (Dijkstra's algorithm) **
topological sorts and Directed acyclic graphs **