CS 327, Spring 2013
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:

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
    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
   Hamiltonian Circuit Problem
   Graph Coloring
   Clique Problem
   Vertex Cover Problem
   Partition Problem