CSE 373 Final Exam Topics (Autumn 2006)
1. Topics from the midterm
- Sets, binary relations, cartesian products,
properties of binary relations, functions, properties of functions.
- logarithms and exponents, the number of
bits required to distinguish one element of a set.
- Growth rates, big O, big Omega, big Theta
- Proof by induction.
- Functional notation for abstract data types.
- Stacks and queues.
- Infix and postfix expressions. Converting and
evaluating expressions.
- Free trees. Rooted, ordered trees.
- Binary trees, binary search trees.
- AVL trees.
- Splay trees.
2. Topics after the midterm
- Document comparison.
- B-trees.
- Hashing.
- Priority queues.
- Sorting.
- Disjoint Sets (UNION-FIND) ADT, also known as dynamic equivalence processing.
- Connected components in images.
- Graphs and their representation.
- Topological sorting.
- Shortest paths via Breadth-First Search.
- Minimum cost paths via Dijkstra's algorithm.
- Transitive closure.
- Floyd-Warshall algorithm.
- Prim's algorithm.
- Kruskal's algorithm.
- Longest common subsequences.
- Genetic algorithms.