Checkpoint

Progress So Far

so far we have implemented and tested serial implementations of both algorithms. We have also started to implement the parallel algorithms.

Schedule

November 12: start implementing and testing serial algorithms (Monica and Kathy)

November 19: finish implementing and testing serial algorithms(Monica and Kathy)

November 23: start implementing parallel humanistic solver (Monica), start implementing parallel SAT solver (Kathy)

November 26: continue implementing parallel solvers (Monica and Kathy)

November 30: finish implementing parallel solvers (Monica and Kathy)

December 3: test and run parallel solvers (Monica and Kathy)

December 7: optimize parallel algorithms (Monica and Kathy)

December 10: prepare speedup graphs and writeup (Monica and Kathy)

December 13: prepare poster and presentation (Monica and Kathy)

New Goals

We were originally planning to implement a motion blur algorithm using ray tracing, but after reading some papers on the subject, we thought that this subject was too complicated for us. Many of the papers about motion blur were too difficult for us to understand. We were interested in trying to parallelize an NP-hard problem so we settled on parallel Sudoku solving. We plan to implement two parallel algorithms: a humanistic solver and a sat solver.

75% goal: Implement elimination in Crook’s algorithm and sequential dpll sat solver

100% goal: Implement elimination and lone rangers in Crook’s algorithm and parallelize dpll sat solver

125% goal: Implement elimination, lone rangers, twins, and triplets in Crook’s algorithm and additional sat solver optimizations

Deliverables

We plan to prepare a poster showing the ideas behind our algorithms and plots of speedup and timing statistics.

Preliminary Results

we do not have preliminary results at this time.

Concerns

no concerns for now