# CSE 417 final exam topics

**
Final Exam:** Will be Wednesday, December 18, 8:30-10:20 a.m. in our
regular room.
That will mean lots of time to study after the end of classes.
Here is a sample final from a previous quarter.
Our
course covered slightly different material that year, so don't take it too
literally, but it will give you some idea of the kinds of questions I might
ask.

## Review session:

Will be Monday, December 16, 3:30-5:00 p.m. in Sieg 134.
## Topics:

All the following are fair game:

- Computability and Turing Machines
- Church-Turing Thesis
- The fact that the Halting Problem is undecidable and how to use this
fact to show that other problems are undecidable

- Basics of Algorithm Analysis
- Complexity analysis, T, Big-O, Omega, Theta
- Recurrences

- Divide and conquer
- Main ideas and recurrences. Why partition into equal size subproblems is
best.
- Bisection, Binary search
- Repeated Squaring
- Karatsuba's Algorithm
- Basic idea behind Strassen's algorithm and Fast Fourier Transform (but not
the details)

- Dynamic programming
- Basic ideas: small # of possible choices of parameters, memoization and
bottom-up evaluation order.
- Conversion of Recursive to Dynamic Programming Solution
- Fibonacci
- Edit Distance
- Longest Increasing Subsequence (rough idea)
- Partition (rough idea)

- Graph Algorithms
- Data Structures for graphs
- Graph Traversal Algorithms: BFS, DFS, including characterization of non-tree
edges in both undirected and directed graphs and applications to connectivity, articulation points (rough idea) and strongly connected components (rough idea).
- Topological Sort
- Min Spanning Trees, Shortest Paths and Priority Queues
- Bipartite Matching

- Basic Pattern Matching
- P, NP, and NP-completeness
- Decision Problems and terminology
- Definition of TIME complexity classes, especially P.
- Definition of NP.
- Showing problems in NP
- Definition of NP-hard and NP-complete.
- Definition of Polynomial-time reduction.
- The fact that Satisfiability and other related problems are all NP-complete.
- What steps are needed to show that a problem is NP-complete now that we
know these NP-complete problems.
- Roughly what NP-completeness of a problem implies about it.