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.

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

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

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

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