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:

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.