### CSC 421: Algorithm Design & Analysis Spring 2015 Course Overview

• To appreciate the role of algorithms in problem solving and software design, recognizing that a given problem might be solved with a variety of algorithms.
• To be capable of selecting among competing algorithms and justifying their selection based on efficiency.
• To be capable of selecting and utilizing appropriate data structures in implementing algorithms as computer programs.
• To develop programs using different problem-solving approaches (divide-and-conquer, backtracking, dynamic programming), and be able to recognize when one approach is a better fit for a given problem.
• To design and implement programs to model real-world systems, and subsequently analyze their behavior.

```Object-oriented programming review
design goals: highly cohesive, loosely coupled
OO concepts: class vs. object, interfaces, inheritance, polymorphism
data structures: List, Set, Map, Stack, Queue, Graph, ...
algorithm analysis: big-Oh, rate-of-growth, analyzing algorithms, recursion

Algorithmic design
brute force algorithms
straightforward, one-time approach
example: invoide lists (HW1)
exhaustive search: string matching
generate-and-test: N-queens, Traveling Salesman, Knapsack
decrease-and-conquer
reduce problem to single, smaller instance
by-constant: sequential search, insertion sort, topological sort
by-constant-factor: binary search, fake coin problem
by-variable-amount: BST search, selection problem, dishonest hangman (HW2)
divide-and-conquer algorithms
reduce problem to multiple smaller instances
examples: merge sort, quick sort, closest points, multiplication, tree recursion
tries: numNodes, numWords, numLetters (HW3)
Master Theorem
transform-and-conquer:
transform problem into a different, more easily solved problem
examples: presorting, balanced BST algorithms, Horner's Rule
problem reduction: lcm --> gcd
greedy
solve by making a sequence of choices/actions, select locally optimal
examples: minimal change, job scheduling, appointment scheduling (HW4)
minimal spanning tree: Prim's algorithm
shortest path: modified BFS,  Dijkstra's algorithm
data compression: Huffman codes
backtracking
solve by making a sequence of choices/actions, back up and retry if fail
examples: N-queens, blob count, Boggle, Hidato (HW5)
branch-and-bound: job assignment
game search: game trees, minimax search, alpha-beta pruning
dynamic:
bottom-up alternative to divide-and-conquer, avoids redundancy
examples: binomial coefficient, World Series puzzle, game probabilities (HW6)
all-pairs shortest path: Floyd's algorithm
top-down with caching: change maker

Algorithm analysis
recursion
analysis via recurrence relation, Master Theorem