###
CSC 421: Algorithm Design & Analysis

Spring 2016

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
exexamples: AnagramFinder, BinaryTree, KWIC-index
string matching: brute force, Horspool, Boyer-Moore
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

Sample Midterm Questions