CSCE 580: Artificial Intelligence

TTh 1400-1515 SWGN 2A24

Prerequisites: CSCE 350 (Data Structures and Algorithms).

Instructor: Marco Valtorta
Office: Swaeringen 3A55, 777-4641
Office Hours: 1100-1200 MWF

Any student with a documented disability should contact the Office of Student Disability Services at (803)777-6142 to make arrangements for proper accommodations.


Grading and Program Submission Policy

Reference materials:

David Poole and Alan Mackworth. Artificial Intelligence: Foundations of Computational Agents. Cambridge University Press, 2010 (ISBN 978-0-521-51900). Supplementary materials from the authors are also available.
Specific objectives of this course are that the students will be able to:
  • Analyze and categorize software intelligent agents and the environments in which they operate
  • Formalize computational problems in the state-space search approach and apply search algorithms (especially A*) to solve them
  • Represent domain knowledge using features and constraints and solve the resulting constraint processing problems
  • Represent domain knowledge about objects using propositions and solve the resulting propositional logic problems using deduction and abduction
  • Represent knowledge in Horn clause form and use the AILog dialect of Prolog for reasoning
  • Reason under uncertainty using Bayesian networks
  • Represent domain knowledge about individuals and relations using first-order logic
  • Do inference using resolution refutation theorem proving (if time allows)
  • Lecture Log

    Student Presentations


    Tests Final exam from fall 2011.

    Most lecture use notes from the authors of the texbook. (See link under "reference materials," above.)
    Overhead transparencies for [P] are linked to the main page for [P]; the specific link is here.

  • Introductory lectures, covering chapter 1 of [P]
  • Agent Architectures and Hierarchical Control, covering chapter 2 of [P]
  • States and Searching, covering chapter 3 of [P]
  • Grids for exercise 3.3 [P]
  • Uninformed (Blind) Search, covering chapter 3 of [AIMA-2] (as used in fall 2011)
  • Heuristic Search, covering chapter 4 of [AIMA-2] (as used in fall 2011)
  • Notes on properties of A*, as written in class of 2011-09-08
  • Notes on computing heuristics by problem relaxation, as written in class of 2011-09-13
  • Notes on Valtorta's Theorem on the complexity of heuristics for A*, as written in class of 2011-09-13
  • Features and Constraints, covering chapter 4 of [P]. (A description of IDA* is given at the beginning of this presentation.)
  • Valtorta's Thorem as described in: Stefan Edelkamp and Stefan Schroedl. Heuristic Search: Theory and Applications. Morgan-Kauffman, 2011.
  • Doug Fisher's video on Constraint Satisfaction (as Search) (7mins approx.)
  • Doug Fisher's video on Generalized Arc Consistency (16 mins approx.)
  • Doug Fisher's video on Features, Constraints, Machine Learning, Printing (15 mins, approx.)
  • Networks for exercises 4.3(c) and 4.4

    Quizzes (In-Class Exercises)
    Quiz 1 of 12-08-28 (with answer)
    Quiz 2 of 12-08-30 (with answer)
    Quiz 3 of 12-09-01 (with answer)
    Quiz 4 of 12-09-18 (with answer)

    The USC Blackboard has a site for this course.

    Some useful links:

    1. Brian Hayes. "The Manifest Destiny of Artificial Intelligence." American Scientist, Volume 100, Number 4 (July-August 2012), 282-287 (local copy) .
    2. Bruce G. Buchanan. "A (Very) Brief History of Artificial Intelligence." AI Magazine, Winter 2005, pp.53-60 (local copy), related links at, compiled by the author.
    3. Allen Newell. "Intellectual Issues in the History of Artificial Intelligence." From: Fritz Machlup and Una Mansfield, eds. The Study of Information: Interdisciplinary Messages. John Wiley and Sons, 1983, pp.187-227.
    4. An obituary of Ray Solomonoff, (co-inventor) of descriptive complexity (Kolmogorov complexity) and advocate of the use of probability in artificial intelligence, written by his wife, Grace (_Algorithms_ 2010, 3, 255-259).
    5. In this class, we write dates according to ISO Standard 8601. (Also see this).
    6. The Alan Turing Home Page, maintained by Andrew Hodges.
    7. Alan Turing's ``Computing Machinery and Intelligence,'' Mind, 49 (1950), pp.433-460 , in HTML format.
    8. Hart, P., Nilsson, N., and Raphael, B., "A Formal Basis for the Heuristic Determination of Minimum Cost Paths," IEEE Trans. Syst. Science and Cybernetics, SSC-4(2):100-107, 1968. (local copy).
    9. Hart, P., Nilsson, N., and Raphael, B., "Correction to 'A Formal Basis for the Heuristic Determination of Minimum-Cost Paths'," SIGART Newsletter, no. 37, pp. 28-29, December, 1972. (local copy).
    10. Judea Pearl. "On the Discovery and Generation of Certain Heuristics." AI Magazine, 4, 1 (Winter/Spring 1983), 23-34 (local copy).
    11. M. Valtorta. "A Result on the Computational Complexity of Heuristic Estimates for the A* Algorithm. Information Sciences, 34, 47-59 (1984), (local copy).
    12. John McCarthy's Obituary from the _New York Times_, 2011-10-25 (local copy).
    13. Local copy of Raymond Reiter, "A Theory of Diagnosis from First Principles." Artificial Intelligence, 32, 1, pp.57-96, 1987.
    14. Local copy of Russell Greiner, Barbara A. Smith, and Ralph W. Wilkerson. "A Correction to the Algorithm in Reiter's Theory of Diagnosis. Artificial Intelligence, 41, pp.79-88.
    15. George F. Luger and William A. Stubblefield. AI Algorithms, Data Structures, and Idioms in Prolog, Lisp, and Java. Addison-Welsey, 2009 (local copy).