Spring 2019

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: kth-order approximations (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 guessing game (HW2) divide-and-conquer algorithms reduce problem to multiple smaller instances examples: merge sort, quick sort, closest points, multiplication tree recursion: numNodes, numWords, select & rank (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: optimal change, job scheduling, greedy paths (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, Sudoku, ABC Path puzzle (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, win probabilities (HW6) all-pairs shortest path: Floyd's algorithm top-down with caching: change maker case studies Facebook: keyboard prediction, binary search Google: PageRank algorithm National Resident Matching Program: stable matching problem, Gale-Shapley algorithm Algorithm analysis recursion analysis via recurrence relation, Master Theorem space vs. time tradeoffs examples: heap sort, hash tables, BinaryTree string matching: Horspool's algorithm, Boyer-Moore algorithm complexity theory lower bounds on problems brute force, info-theoretic, adversary argument decision trees: sorting, searching problem reduction: square --> multiply, EU --> CN, CN --> CP tractable vs. intractable vs. undecidable (Halting Problem) P vs. NP, Turing machine vs. non-deterministic Turing machine NP-complete problems (e.g., SAT), reductions (e.g., SAT --> CLIQUE) approximation algorithms, genetic algorithms