Topics for CSE 417 Final Exam

1. Proofs by induction

2. Algorithm design techniques

   1. General design by induction

   2. Divide and Conquer

   3. Greedy Algorithms

   4. Dynamic Programming
      
      
      • Fibonacci Numbers
        
      • Knapsack
        
      • Edit Distance

3. O-notation and running-time bounds
   
   
   1. Setting up recurrences to describe algorithms' resource usage
      
   2. Solving iterative recurrences
      
   3. Solving divide and conquer recurrences

4. Algorithms on sequences
   
   
   1. Binary search
      
   2. Mergesort
      
   3. Quicksort
      
   4. Maximum consecutive subsequence
      
   5. Edit Distance

5. Graph algorithms
   
   
   1. Topological sort
      
   2. Breadth-first and depth-first searching
      
   3. Connected components
      
   4. Single-source shortest paths - Dijkstra's algorithm
      
   5. All pairs shortest paths - Floyd's algorithm
      
   6. Minimum spanning trees - Prim's algorithm, Kruskal's algorithm

6. Algebraic Algorithms
   
   
   1. Powering via repeated squaring
      
   2. Euclid's algorithm for gcd's
      
   3. Karatsuba's algorithm for multiplying polynomials
      
   4. Fast Fourier Transform

7. Computability
   
   
   1. Intuitive definition of a Turing machine
      
   2. Church's thesis that all reasonable models of computation are equivalent in power to the Turing machine (or C programs)
      
   3. What the Halting problem is
      
   4. What it means to be decidable
      
   5. Dovetailing to prove things are countable
      
   6. Diagonalization to prove things uncountable
      
   7. The fact that the Halting problem is not decidable
      
   8. What reducible means

8. Complexity
   
   
   1. What a decision problem is
      
   2. What P is
      
   3. How to show that a problem is in P
      
   4. What polynomial-time mapping reducible means
      
   5. What NP is
      
   6. How to show that a problem is in NP
      
   7. What NP-complete means
      
   8. What SAT, k-SAT, CLIQUE, and COLOR are
      
   9. The fact that SAT, 3-SAT, CLIQUE and COLOR are NP-complete
      
   10. How to show that a problem is NP-complete