CSC 427: Data Structures and Algorithm Analysis
Fall 2006
Test 2 Review
TEST 1 MATERIAL
Data Structures
Set & Map interfaces
TreeSet & TreeMap: underlying balanced binary search trees
HashSet & HashMap: underlying hash tables
trees
tree terminology: node, root, leaf, path, height, weight
tree applications: file structure in OS, du command
binary tree implementation
pointer manipulation, tree recursion
divide & conquer algorithms
binary search tree
if roughly balanced, O(log N) search/insert/remove
if unbalanced, O(N) search/insert/remove
SimpleTreeSet implementation, tree iterator
balanced binary search trees
AVL trees, red-black trees
add additional properties on BST, insert/remove must maintain properties
ensure O(log N) tree height --> O(log N) search/insert/remove
hash tables
key-value mapping, hash function
if table size & hash function "reasonable", O(1) search/insert/remove
if not, O(N) search/insert/remove
collision handling
linear probing, lazy deletion, primary clustering, rehashing
quadratic probing, chaining
Algorithmic Approaches
divide & conquer
idea: divide into subproblems, solve (usually recursively), then combine
when: any application that can be divided into independent parts
e.g.: binary search, merge sort, GCD, tree traversal
generate & test
idea: generate all potential solutions in sequence & test each
when: solution is a sequence of actions, no problem-specific knowledge
examples: inefficient N-queens, NP-hard problems (later)
greedy
idea: make a sequence of choices, each of which looks best at the moment
when: solution is a sequence of actions & perfect knowledge is available
e.g.: job scheduling, U.S. optimal change
backtracking (a.k.a. smart generate & test, tentative greedy)
idea: make next choice, test if still ok & unwind if dead end
when: choices are dependent, earlier choices constrain later ones
e.g.: N-queens, Boggle search, blob count, Sudoku solver
dynamic programming
idea: bottom-up divide & conquer, cache solutions to smaller problems
when: subproblems are not independent, want to avoid redundant computation
e.g.: change maker, Fibonacci, binomial coefficient