Final Exam Study Guide

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

# Concepts

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

# Techniques

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 Ω (nlogn) 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

# Algorithms

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
• 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