The final exam for this course will take place during the officially scheduled final exam period: 1:30 PM on Sunday, May 6. It will be in our regular classroom, Gulick 2001.
Although this is a final exam, it counts for only 15% of your grade for the course, the same amount as the in-class part of the midterm exam. It will be four or five pages long. Because you will have up to three hours to complete the exam, some of the questions might be deeper and more challenging than questions that would ordinarily appear on a one-hour test. In particular, I will expect knowledgeable and carefully written answers to essay-type questions.
The exam will cover material that we have done in class since the midterm. I will not ask about specific algorithms and data structures covered earlier in the term (such as heaps, quicksort, and topological sort of directed acyclic graphs). However, you should understand the basic approaches to algorithms design. And you will also need to know basic ideas from earlier in the term. For example, you should be able to work with Big‑Oh, Big‑Θ, and Big‑Ω.
Many of the questions on the exam will be essay-type, including definitions, short-answer essays, and some longer essays. Other possibilities include, for example: executing an algorithm, such as Kruskal's or Prim's MST algorithm, on a given input; converting a recursive algorithm to a dynamic programming algorithm; analyzing the run time of an algorithm; or doing a simple problem reduction.
I will not ask about Floyd's algorithm, alpha-beta pruning, the dynamic programming algorithm for parsing, the proof that CIRCUIT‑SAT is NP-complete, or any of the specific non-trivial NP-completeness proofs by problem reduction.
Here is a list of some of the things that you should know about:
tree (connected, acyclic undirected graph
spanning tree for a connected, undirected graph
minimal spanning tree (MST) for a weighted graph
Prim's MST algorithm
how to speed up Prim by using a priority queue of vertices
Kruskal's MST algorithm
the union-find data structure, with operations "find" and "join"
how union-find is used to keep track of connected components in Kruskal's algorithm
Dijkstra's shortest path algorithm
Prim, Kruskal, and Dijkstra are greedy algorithms that work
state space and state space search
exhaustive search of a state space tree
state space search with pruning
minimax, for game tree search
state spaces for optimization problems
fitness functions and the fitness landscape
heuristic search
hill climbing
simulated annealing
genetic algorithm
how to speed up a recursive function that has many repeated subproblems
memoization
dynamic programming
the Fibonacci sequence; dynamic programming for the Fibonacci sequence
the longest common subsequence problem and its dynamic programming algorithm
recovering the actual longest common subsequence from the dynamic programming table
edit distance
edit operations: keep, replace, insert, delete
the dynamic programming algorithm for edit distance
problems and algorithms
polynomial-time algorithms
polynomial-time problems
decision problems
P (the class of polynomial-time decision problems)
NP (the class of nondeterministic-polynomial-time decision problems)
two definitions of NP problems:
--two phase algorithm, first a nondeterministic phase, then deterministic
--verification algorithm A(x,y)
problem reduction
examples of problem reduction
--testing an array for duplicates to sorting
--sorting to convex hull
NP-hard problems
NP-complete problems (NP-hard and in NP)
how to prove a problem D(x) is NP-hard by reducing a known NP-complete problem to it
the "P = NP" problem
why showing any NP-complete problem is in P would prove that P = NP
the idea of approximation algorithms for hard problems
using heuristic search on NP-hard problems such as k-colorability
NP-complete problems that you should be familiar with:
CIRCUIT-SAT
3-CNF-SAT
HAMILTONIAN-CYCLE
TSP (decision problem version)
k-COLORABILITY
CLIQUE
VERTEX-COVER
KNAPSACK
some basic approaches to algorithms design:
exhaustive search ("brute force");
greedy algorithm
divide-and-conquer (recursion)
dynamic programming
heuristic search