CSE 373 Midterm Exam 1 Topics (Winter 2010)
The format of Midterm Exam 1 will be mixed: Part I will consist of
multiple-choice questions, and Part II will contain a small number
of written-answer problems. For Part I, you need to bring a
standard answer sheet, also known as a "Scantron" form. These
are available for sale at several campus outlets, including
the HUB branch of the U Bookstore. It is not a bad idea to
bring two of these, as there may be classmates who have forgotten
to bring one. There are two more exams in the course after this one,
so an extra form purchased now probably will not go to waste.
- 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.
- Proof by induction.
- Stacks and queues.
- Binary trees; complete, full, and perfect binary trees; depth, height,
siblings, ancestors, descendants.
- Binary search trees, traversals, lookup (find), insertion and deletion.
- AVL trees, single and double rotations, insert.
- B-trees, definition, rationale in terms of hard-disk properties, FIND, insertion.