##
Topics for CSE 417 Final Exam

- Proofs by induction
- Algorithm design techniques
- General design by induction
- Divide and Conquer
- Greedy Algorithms
- Dynamic Programming

- Fibonacci Numbers

- Knapsack

- Edit Distance

- O-notation and running-time bounds

- Setting up recurrences to describe algorithms' resource usage

- Solving iterative recurrences

- Solving divide and conquer recurrences

- Algorithms on sequences

- Binary search

- Mergesort

- Quicksort

- Maximum consecutive subsequence

- Edit Distance

- Graph algorithms

- Topological sort

- Breadth-first and depth-first searching

- Connected components

- Single-source shortest paths - Dijkstra's algorithm

- All pairs shortest paths - Floyd's algorithm

- Minimum spanning trees - Prim's algorithm, Kruskal's algorithm

- Algebraic Algorithms

- Powering via repeated squaring

- Euclid's algorithm for gcd's

- Karatsuba's algorithm for multiplying polynomials

- Fast Fourier Transform

- Computability

- Intuitive definition of a Turing machine

- Church's thesis that all reasonable models of computation are
equivalent in power to the Turing machine (or C programs)

- What the Halting problem is

- What it means to be decidable

- Dovetailing to prove things are countable

- Diagonalization to prove things uncountable

- The fact that the Halting problem is not decidable

- What reducible means

- Complexity

- What a decision problem is

- What P is

- How to show that a problem is in P

- What polynomial-time mapping reducible means

- What NP is

- How to show that a problem is in NP

- What NP-complete means

- What SAT, k-SAT, CLIQUE, and COLOR are

- The fact that SAT, 3-SAT, CLIQUE and COLOR are NP-complete

- How to show that a problem is NP-complete