CSE 373 Midterm Exam 1 Topics (Autumn 2008)
- 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.
- Arithmetic and geometric series.
- Growth rates, big O, big Omega, big Theta.
- Asymptotic analysis of running times.
- Analysis of Mergesort running time.
- Proof by induction.
- Functional notation for abstract data types.
- Stacks and queues.
- Binary trees; complete, full, and perfect binary trees; depth, height.
- Binary search trees, traversals, lookup (find), insertion and deletion.
- AVL trees, single and double rotations, insert, delete.