Information on the Final Exam

The final exam for this course is scheduled for Tuesday,
May 13, at 8:30 AM. We have decided **not** to have
a take-home part of the final, so there will only
be an in-class part. The final will be five or six
pages long. The format will be similar to the previous
tests. The final exam will be cumulative, with some emphasis
on material covered since the second test.

**Here is a list of some of the most important things from earlier in the course:**

algorithm time efficiency and space efficiency of algorithms worst case, average case, and best case analysis Big-Theta, Big-Oh, and Big-Omega graphs; vertices and edges; undirected and directed graphs adjacency matrix and adjacency list representations of a graph depth-first and breadth-first search connected components of a graph paths and cycles in a graph; acyclic graphs topological sort of a directed acyclic graph Hoare and Lomutu partitioning and their use in Quicksort 2-3 trees heaps, priority queues, and heapsort hash tables; open and closed hash tables hash functions; collisions in a hash table Floyd's all-pairs shortest path algorithm techniques used in algorithms: brute force / exhaustive search decrease-and-conquer divide-and-conquer dynamic programming

**And here is a list of other things, mostly covered since the second test:**

greedy algorithms Dijkstra's single-source shortest path algorithm trees (in the sense of connected, acyclic, undirected graph) spanning tree weighted graph minimal spanning tree Prim's minimal spanning tree algorithm Kruskal's minimal spanning tree algorithm critical path analysis (in a weighted, directed, acyclic graph) the stable marriage problem blocking pair in a stable marriage problem solving a stable marriage problem decision problem optimization problems and how they relate to decision problems the class P of decision problems solvable in polynominal time nondeterministic algorithms for decision problems the class NP of nondeterministic polynomial time decision problems the unsolved problem, is P = NP ? polynomial reducibility NP-complete problems proving that D is NP-complete by reducing a known NP-complete problem to D reducing the Partition Problem to the Knapsack Problem reducing SAT to CIRCUIT-SAT reducing the clique decision problem to the vertex cover decision problem proof that CIRCUIT-SAT is NP complete NP-complete [in their decision problem form] problems that you should know: Traveling Salesman Problem Knapsack Problem CIRCUIT-SAT SAT Hamiltonian Circuit Problem Graph Coloring Clique Problem Vertex Cover Problem Partition Problem