CSC 421: Algorithm Design & Analysis
Spring 2014

Midterm Review


Java/Data Structures review
  OO design: cohesion, coupling, interfaces, inheritance, polymorphism
  data structures: List, Set, Map, Graph, Stack, Queue
  algorithm efficiency: big-Oh, rate-of-growth, iteration, recursion

Brute force approach
  focus on solving in simplest way - don't worry about extensibility/reuse
  exhaustive search, generate & test, nP-hard problems
  examples: league standings, string matching, N-queens, knapsack, dictionary
    
Decrease & conquer approach
  reduce problem to a similar problem of a smaller size
  top-down (recursive) vs. bottom-up (iterative) implementations
  decrease by constant: insertion sort, topological sorting
  decrease by constant factor: binary search, fake coin problem
  decrease by variable amount: search/insert into BST, quick select
  
Divide & conquer approach
  reduce problem to multiple subproblems, combine answers
  Master Theorem
  examples: merge sort, quick sort, closest pair, large int multiplication,
            exhaustive tree recursion (e.g., size, contains, toString)
            
Transform & conquer approach
  transform problem into a more easily solved one
  examples: presorting, BSTs (AVL, red-black), heaps, Horner's rule
  problem reduction: lcm --> gcd, graph searches
  
Space vs. time
  additional storage can often allow for a more efficient algorithm
    examples: ArrayList resize, linked structures, heap sort, hash tables
    examples: AnagramFinder, BinaryTree, KWIC-index
    string matching: brute force, Horspool, Boyer-Moore