CPSC 220 Fall 2006Test 1 Topics

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

• Sorting
• 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 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