The second test for this course will take place in class on Monday, April 29. The test counts for 15% of the total grade for the course. It will cover material that we have done in class since the first test. I will not ask about specific algorithms and data structures covered earlier in the term (such as heaps, quicksort, and breadth-first search of 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 certainly 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: giving an outline of a well-known algorithm; executing an algorithm, such as topological sort or Kruskal'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.
Aside from the test, your only remaining work for the course is your term project. The term project counts for 10% of the total grade for the course. For the project, you should turn in either a moderately long paper (about six to ten pages), a significant programming project with whatever commenting and documentation is necessary to understand it, or a small programming project and a short paper (about two or three pages).
I will accept projects from seniors up until 12:00 noon on Sunday, May 12. I will accept projects from non-seniors up until the scheduled final exam time, 7:00 PM on Monday, May 13.
You are also encouraged to do a presentation to the class about your project. (Of course, you were encouraged to do that since the beginning of the semester.) If you want to do a presentation, you should meet with me to sign up for a time during one of the last three classes (May 1, 3, and 6) and to discuss what you will do in the presentation. I cannot guarantee a time for everyone who wants to do a presentation, so you should act soon.
Here is a list of some of the things that you should know for the test:
some basic approaches to algorithms design:
exhaustive search ("brute force")
greedy algorithm
divide-and-conquer (recursion)
dynamic programming
heuristic search
directed acyclic graph (dag)
topological sort of a dag
spanning tree for a connected, undirected graph
minimal spanning tree (MST) for a weighted graph
Prim's MST algorithm
Kruskal's MST algorithm
the union-find data structure
how union-find is used to keep track of connected components in Kruskal's algorithm
Prim's algorithm and Kruskal's algorithm are greedy algorithms
configuration spaces for optimization problems
exhaustive search of a configuration space
fitness functions and the fitness landscape
heuristic search
hill climbing
simulated annealing
genetic algorithm: population, fitness, selection, crossover, mutation
using heuristic search on a hard problem such as k-coloring a graph
how to speed up a recursive function that has many repeated subproblems
dynamic programming using memoization
dynamic programming using bottom-up filling of a table
the Fibonacci sequence; dynamic programming for the Fibonacci sequence
the longest common subsequence problem and its dynamic programming algorithm
edit distance
edit operations: keep, replace, insert, delete, swap
the dynamic programming algorithm for edit distance
polynomial-time algorithms
polynomial-time problems
how input size is measured in the definition of polynomial time, and why it matters
decision problems
decision problems associated to optimization problems
P (the class of polynomial-time decision problems)
NP (the class of nondeterministic-polynomial-time decision problems)
definition of NP in terms of validation algorithms
P is a subset of NP
the "P = NP" problem
problem reduction
polynomial-time problem reduction
NP-hard problem (any NP problem can be polynomially reduced to it)
NP-complete problems (NP-hard and also in NP)
why you probably won't find an efficient solution to an NP-complete problem
how to prove a problem H is NP-hard by reducing a known NP-complete problem to it
why we need to prove directly that some problem is NP-complete
why showing any NP-complete problem is in P would prove that P = NP
the basic idea of approximation algorithms for hard problems
NP-complete problems that you should be familiar with:
CIRCUIT-SAT
SAT
3-CNF-SAT
CLIQUE
VERTEX-COVER
HAMILTONIAN-CYCLE
TSP (decision problem version)
k-COLORABILITY and 3-COLORABILITY