Topic List for the Midterm Exam in CSE 373, Spring 2004

This midterm covers:
 1. set theory, including union, intersection, and cartesian product.
 2. binary relations and the properties of reflexiveness, symmetry,
     transitivity.
 3. functions, domains, ranges, injection, surjection, invertibility.
 4. ADTs
 5. representation of ADTs by math formulas; especially the Stack ADT.
 6. proofs by induction
 7. Big O notation. Also, big omega and big theta.
 8. Representation of polynomials with linked lists.
 9. Representation of unlimited-precision integers.
10. Queue implementation using a "circular" array.
11. Trees, binary trees, preorder, inorder, and postorder traversal.
12. Recursive implementation of tree operations for traversal,
    FIND, INSERT, DELETE.
13. Binary search trees.
14. Huffman trees.
15. Priority queues and binary heaps.
16. Hashing. Load factor, open hashing, open addressing, 
    linear probing, quadratic probing, double hashing, rehashing.
    Computing hash functions of strings using Horner's rule.

Exam Format

Part I: Multiple-choice. Bring a standard answer sheet (sometimes called a "scantron form"). These are available from the University Book Store (including the HUB branch of the bookstore) for about 45 cents.

Part II: Written answer.

Both parts of the exam are "closed-book" and done without calculators or anything other than paper, pen, and pencil.