##
CPSC 220 Fall 2006

Test 1 Topics

- The sum of the integers from a to N+b is O(N
^{2}). Be able
to prove this!

- Sorting
- O(N
^{2}) sorts -- Insertion, Selection, Bubble
- O(NlogN) sorts -- Quick, Merge
- For each sort:
- Thorougly understand algorithm -- be able to execute and explain
- Be able to trace and understand code
- Know complexities on sorted, reverse, and random lists and be able to
explain

- Binary Trees
- Terminology -- node, edge, child, parent, level, height, etc.
- Shapes -- complete, full (completely filled in), stringy, bushy
- Traversals (pre, in, post, level order)
- Properties. A binary tree...
- with N nodes has height at least ___.
- with N nodes has height at most ___.
- with N nodes has at most ___ leaves.
- with N nodes has at least ___ leaves.
- has at most ___ nodes at level k.
- with height H has at least ___ nodes.
- with height H has at most ___ nodes.

You must understand and be able to explain each of these!

- Binary Search Trees
- Properties
- How to build, insert nodes, remove nodes
- How to search
- Complexities to build, insert and search given various tree shapes