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