Topic List for the Final Examination in CSE 373, Winter 2002

The final exam will cover the topics listed for
Quiz 1, Quiz 2, and the following.
 1. Hashing, including hashing with chains, closed hashing,
    collision resolution using linear probing,
    hash functions involving bitwise exclusive-OR operations,
    and deletion from a hash table.
 2. binary search trees, including the binary search tree
    property, and performance considerations.
 3. AVL trees, including insertion, single and double rotations
    (but not deletion).
 4. B-trees, including insertion and deletion.  Also, disk storage
    organization in terms of tracks, sectors and blocks.
    The Indexed Sequential Access Method (ISAM).
 5. the Priority Queue ADT.  Implementation using Heaps.
    Heapsort and its properties in terms of time and space
    utilization.
 6. UNION-FIND abstract data type implemented with Uptrees;
    heuristics for optimizing performance of these operations,
    including path compression.  Its application in
    Kruskal's algorithm (see below), and in finding the
    connected components of an image.
 7. directed and undirected graphs, and weighted graphs,
    Euler paths,  graph representation with adjacency lists,
    adjacency matrices, and incidence matrices.
 8. spanning trees and minimum spanning trees, and
    Kruskal's algorithm for finding a minimum spanning tree.
 9. Depth-first search in a graph, and breadth-first search in a graph.