CSE 326 Exams -- Autumn 1999
Midterm exam:
Friday, November 5, 1999. It will be closed-book.
For Part I of the exam you will need a Scantron form (available at the
HUB branch of the University Bookstore for around 35 cents) and a couple
of number 2 pencils.
Topics to be covered: Geometric series, harmonic series, formula for
the sum of i where i goes from 1 to n; order notation, applying the divide-and-conquer
recurrences theorem (memorization not required), greedy vs exhaustive search
algorithms, idea behind dynamic programming algorithms; mathematical description
of stack and queue operations; tree terminology -- esp. height, perfect
binary trees, complete binary trees, full binary trees, forests of trees;
traversals, evaluation of expression trees, Huffman encoding, heaps, prefix
property; unordered lists and the move-to-front heuristic; binary search
tree Lookup, Insert, and Delete operations; AVL tree definition, insertion
and deletion.
Final exam:
Monday, December 13, 1999 (from 2:30 to 4:20 PM). This will
be a closed-book exam. Bring a couple of number 2 pencils and a Scantron
standard answer sheet. The exam will be comprehensive, covering all
the midterm material, plus additional material:
-
B-tree definition and insertion method;
-
hashing, including open hashing with separate chaining, open addressing,
linear probing;
-
up-trees and their use in the disjoint set operations;
-
k-d trees and range searches;
-
mark-and-sweep garbage collection;
-
directed and undirected graphs and their representation using adjacency
lists and adjacency matrices;
-
topological sorting;
-
breadth-first search and depth-first search in graphs;
-
minimum spanning trees and their computation using Kruskal's algorithm;
-
Dijkstra's single-source shortest paths algorithm;
-
sorting with insertion sort, heapsort, merge sort, quicksort, and radix
sort;
-
the n log n lower bound on running times for comparison-based sorting.