| Course material |
<![CDATA[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: order-approximations, N-queens, knapsack, SortedArrayList
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
string matching: brute force, Horspool, Boyer-Moore
Greedy approach
solve by making a sequence of choices/actions, select locally optimal
examples: minimal change, job/event scheduling
minimal spanning tree: Prim's algorithm
shortest path: modified BFS, Dijkstra's algorithm
data compression: Huffman codes
]]>
|