Course material

Java/Data Structures review
OO design: cohesion, coupling, interfaces, inheritance, polymorphism
data structures: List, Set, Map, Graph, Stack, Queue
algorithm efficiency: bigOh, rateofgrowth, iteration, recursion
Brute force approach
focus on solving in simplest way  don't worry about extensibility/reuse
exhaustive search, generate & test, nPhard problems
examples: credit card, string matching, Nqueens, knapsack, SortedArrayList
Decrease & conquer approach
reduce problem to a similar problem of a smaller size
topdown (recursive) vs. bottomup (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, redblack), 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
string matching: brute force, Horspool, BoyerMoore
Greedy approach
solve by making a sequence of choices/actions, select locally optimal
examples: minimal change, job scheduling,
minimal spanning tree: Prim's algorithm
shortest path: modified BFS, Dijkstra's algorithm
data compression: Huffman codes
