CPSC 220 Fall 2006
Test 1 Topics
- The sum of the integers from a to N+b is O(N2). Be able
to prove this!
- O(N2) 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
- 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...
You must understand and be able to explain each of these!
- 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.
- Binary Search Trees
- How to build, insert nodes, remove nodes
- How to search
- Complexities to build, insert and search given various tree shapes