Informal Assessment

We used a sequence of projects based on the Satisfiability problem in
the Spring 2008 offering of the Design and Analysis of Algorithms course
at Rowan University.

The projects sequence was:
1. Brute force solver
2. Sudoku solver 
3. Davis-Putnam solver (Jersoslow Wang branch variable heuristic, efficient data structures)  
4. Advanced Davis-Putnam solver (fast unit propogation)

Number of students in the class: 24
Percentage of students who successfully completed the final project: 67%


NP-completeness proofs discussed in class:
3-coloring to SAT (SAT is NP-complete!)
Independent set to clique
Hamiltonian path to Hamiltonian circuit
Hamiltonian circuit to Traveling Salesperson


Informal assessment of student achievement 
(based on the final exam, which is available on this web site):

Final Exam	Topic					% of students who 
Question Num						demonstrated competence
-------------------------------------------------------------------------------
1.		graph orderings: bfs, dfs			92

2.		NP-completeness proof of Hamiltonian		67
		circuit (reduction from Hamiltonian path)

3.		design backtracking algorithm to		71
		compute independent set of a graph
                (apply design techniques learned in the
		SAT domain to another intractable problem)

4.		compute optimal binary search tree for		71
		for a set of (key, prob) pairs, following
 		the dynamic programming algorithm 
		discussed in class

5.		(Extra credit)	open-ended algorithm design	33
		question on graphs: the center of gravity