Graduate student presentations:

You will show that Dijkstra's algorithm is optimal according to the measure "number of node expansions" in the class of unidirectional blind algorithms for state-space search. You will also show that the algorithm realization that uses Fibonacci heaps is optimal in the traditional algorithm analysis sense in the decision tree model. This material is based on Chapter 13 of: Jeffrey H. Kingston.

Laura Boccanfuso and Amber McKenzie, presented on 2008-09-10

You will present the analysis of the optimality of A* by Dechter and Pearl. This analysis is presented in several articles, including: Rina Dechter and Judea Pearl. "The Optimality of A*." In: L. Kanal and V. Kumar, eds.

Jimmy Cleveland and Jarrell Waggoner, presented on 2008-09-19

You will present and compare heuristics for sliding time puzzles, including Gaschnig's heuristic, linear conflict, and using pattern databases. Key references are the following. Othar Hansson and Andrew Mayer. "Criticizing Solutions to Relaxed Models Yields Powerful Admissible Heuristics."

Yu Cao and Shawn Gause, presented on 2008-09-22

You will present the syntax, semantics (truth tables), and inference system (Lukasiewicz's axioms and rule of inference) of the propositional calculus and show that it is sound (i.e., every theorem is a tautology) and complete (every tautology can be proved). The key reference is chapter 9 of: Ann Yasuhara.

You will present the proof technique of natural deduction, as described in the following key reference: chapter 5 of: Steve Reeves and Michael Clarke.

Jordan Bradshaw, Virginia Walker, and Dylan Kane, presented on 2008-12-05

You will present the sound and complete theorem prover outlined in the following key reference: Donald W. Loveland and Mark E. Stickel. "A Hole in Goal Trees: Some Guidance from Resolution Theory."

You will present the basic formalism of consistency-based diagnosis, one of the most successful examples of logical representation and model-based reasoning. The key reference is: Raymond Reiter, "A Theory of Diagnosis from First Principles."

You will present the basic formalism of abductive diagnosis, one of the the most successful examples of logical knowledge representation and model-based reasoning. The key reference is: David Poole. "Normality and Faults in Logic-Based Diagnosis."