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