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