The final exam will cover the topics listed for Quiz 1, plus the following:
AVL trees, including insertion, single and double rotations
(but not deletion).
Document comparison by taking the dot product of two vectors, where
each vector gives the number of occurrences of each word in
the corresponding document.
B-tree insertion, including splitting nodes during insertion,
(but you are not responsible for deletion or coalescing nodes
during deletion).
Sorting concepts, including the compare-exchange operation, stability,
time and space considerations.
Specific sorting algorithms: bubble sort, Heapsort, Mergesort,
Quicksort, and Radix sort.
UNION-FIND abstract data type implemented with Uptrees;
heuristics for optimizing performance of these operations,
including path compression. Its applications in
maze construction and finding the connected components of
an undirected graph.
Directed and undirected graphs, and weighted graphs.
Graph representation with adjacency lists and with
adjacency matrices.
Spanning trees and minimum spanning trees for weighted
undirected graphs.
Depth-first search in a graph, and breadth-first search in a graph.
Dijkstra's algorithm for the shortest paths from one vertex of
a directed (or undirected) graph to each of the other vertices.
The Floyd-Warshall algorithm for finding the shortest paths
between all pairs of vertices of a directed (or undirected) graph.
Topological ordering and topological sorting of the vertices
of a directed acyclic graph.