CPSC 220 Fall 2006
Test 1 Topics

• The sum of the integers from a to N+b is O(N²). Be able to prove this!

• Sorting
  • O(N²) 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