Information About the Second Test

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