CSCE 580 Presentations

Graduate student presentations:

1. Optimality of Dijkstra's algorithm.
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. Algorithms and Data Structures: Design, Correctness and Analysis, Second Edition. Addison-Wesley, 1997.
Laura Boccanfuso and Amber McKenzie, presented on 2008-09-10

2. Optimality of A*.
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. Search in Artificial Intelligence. Springer-Verlag, 1988.
Jimmy Cleveland and Jarrell Waggoner, presented on 2008-09-19

3. Heuristics for sliding-tile puzzles (including Gaschnig's heuristic, linear conflict, and using pattern databases).
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." Information Sciences, 63, pp.207-227, 1992. Richard E. Korf. "Recent Progress in the Design and Analysis of Admissible Heuristic Functions." Proceedings of SARA 2000, pp.45-55, 2000.
Yu Cao and Shawn Gause, presented on 2008-09-22

4. Soundness and completeness of the propositional calculus.
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. Recursive Function Theory and Logic.. Academic Press, 1971.

5. Natural deduction.
You will present the proof technique of natural deduction, as described in the following key reference: chapter 5 of: Steve Reeves and Michael Clarke. Logic for Computer Science Addison-Wesley, 1990. ( An online revised version is available.)
Jordan Bradshaw, Virginia Walker, and Dylan Kane, presented on 2008-12-05

6. A Prolog-Technology Theorem Prover.
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." IEEE Transactions on Computers, vol. C-25, No.4, pp.335-341, April 1976.

7. Consistency-Based Diagnosis.
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." Artificial Intelligence, 32, 1, pp.57-96, 1987.

8. Abductive Diagnosis.
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." Proceedings of the Twelfth International Joint Conference on Artificial Intelligence (IJCAI-91), Sydney, Australia, pp. 1129-1135, August 1991.