Final Exam Study Guide

This is the archived website of SI 335 from the Spring 2015 semester. Feel free to browse around; you may also find more recent offerings at my teaching page.

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

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)
- 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 concepts: matching, vertex cover, paths, cycles, spanning trees
- 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- Compromising speed or correctness to solve an NP-hard problem
- Randomized algorithms

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
- Greedy algorithms
- Expected analysis
- Using one problem to solve another problem (i.e., a
*reduction*) - Using reductions for lower bounds (especially polynomial-time reductions and NP-hardness.
- 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

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

Integer multiplication

- Standard algorithm
- Karatsuba's algorithm

Minimum Spanning Tree (MST) computation

- Prim's algorithm
- Kruskal's algorithm

- Transitive closure using matrix powering
- Standard graph search algorithms (BFS, DFS, Dijkstra's, Floyd-Warshall)
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
- 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

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

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