Final Exam Study Guide

This exam is **cumulative** and will cover the all the material from Units 1-8.

You should have a solid understanding of the meaning and uses of the following concepts

- Problem to Algorithm to Program
- Abstract machine
- Asymptotic notation (big-O, big-Θ , big-Ω )
- Worst-case running time
- Primitive operation
- Difficulty measure
- Cost function
- Comparison model
- Lower bound for a
*problem* - Size vs value of an integer
- Polynomial-time
- Cobham-Edmonds thesis
- Modular arithmetic (addition, subtraction, multiplication, division)
- Greatest common divisor
- Public-key cryptography
- Multiple-precision integers (digits, base, representation)
- Randomized algorithms
- Graphs: terminology (vertex, edge, (un)directed, (un)weighted) and representations
- Size of a graph (depending on representation)
- Optimization problem (minimization or maximization)
- Trading off speed versus correctness
- Approximation algorithms
- Graph problems: matching, vertex cover, longest/shortest path, Hamiltonian cycle, TSP
- Inherent difficulty of a problem
- Decision problem
- Certificates and verifiers
- Complexity classes
**P**and**NP** **NP**-hardness,**NP**-completeness**P**versus**NP**question, how it could be solved, and the implications- Amortized analysis

You should know the following techniques and be able to apply them:

- Loop invariants
- Iterative analysis (loops)
- Solving arithmetic and geometric series summations
- Recursive analysis (recurrences)
- Solving recurrences by expansion
- Solving recurrences by a Master Method
- Divide-and-conquer
- Linear-time lower bounds
- Information-theoretic lower bounds (like the Ω (
*n*log*n*) lower bound for sorting) - Memoization
- Dynamic programming
- Average-case analysis
- Expected analysis
- The "At Least Linear" Lemma
- Greedy algorithms
- Reduction between problems (specifically, polynomial-time reductions)
- Branch and Bound
- Iterative Refinement
- Amortized analysis

You should be very familiar the following algorithms, including their analysis and how to apply them:

Sorted Array Search Problem

- LinearSearch
- BinarySearch
- GallopSearch

Sorting problem, using comparisons

- SelectionSort
- InsertionSort
- MergeSort
- HeapSort
- QuickSort1, QuickSort2, QuickSort3

- Factorization (leastPrimeFactor)
- Square-and-multiply exponentiation
- Euclidean algorithm (GCD)
- Extended Euclidean algorithm (XGCD)
RSA

- Key generation
- Encryption with public key
- Decryption with private key

Integer multiplication

- Standard algorithm
- Karatsuba's algorithm

- Standard algorithm for matrix multiplication
Recursive, memoized, and dynamic programming algorithms for matrix chain multiplication

Selection Problem

- Heap-based solutions
- QuickSelect1 (first element is the pivot)
- QuickSelect2 (random element is the pivot)
- QuickSelect3 (median-of-medians is the pivot)

- QuickSort (see above under "sorting")
Sorting problem, not using comparisons

- Bucket Sort (general idea, not a specific algorithm)
- CountingSort
- RadixSort

- Breadth-first and depth-first search in a graph
- DAG linearization
- Single-source shortest paths problem: Dijstras on adjacency list or matrix, using heap or unsorted array
All-pairs shortest paths problem

- Repeated Dijkstra's
- Floyd-Warshall algorithm
- Tropical algebra and matrix arithmetic

Transitive closure problem

- Reduction to all-pairs shortest paths
- Using boolean algebra

Minimum Spanning Tree (MST) problem (review!)

- Kruskal's algorithm
- Prim's algorithm

- Greedy algorithm for maximal matching
- Approximating vertex cover using maximal matching
Traveling Salesman Problem

**NP**-hard reduction- Branch-and-bound solution
- Approximation (for Metric TSP) using minimum spanning trees
- Greedy algorithm
- 2-OPT iterative refinement

Self-organizing search

- Updating with "transpose"
- Updating with "move to front"

You should also be familiar with what these algorithms do, and how much they cost, although you don't need to remember every detail:

- Miller-Rabin primality test
- Toom-Cook and Schoenhage-Strassen integer multiplication
- Strassen's algorithm for matrix multiplication
- Edmonds's algorithm for maximum matching