CSCE 580: Artificial Intelligence

TTh 1005-1120 300 Main B112

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. Note that you may have to configure java to allow the applets at and at to run, because they are self-signed applications. See this tutorial for details.

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

    Some assignments are only listed in the lecture log.


    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]
  • Notes on an example of transduction and belief states used in the 2014-01-30 class (pdf)
  • 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)
  • Photo of board showing a solution to HW2: Run by hand Dijkstra's Algorithm (as stated in slide 68 at h ttp:// on the example of Figure 3.2 [P] (also on slide 6 at; show the OPEN and CLOSED lists with the g values of the nodes on those lists for each iteration of lines 2-6 from beginning to end.
  • Heuristic Search, covering chapter 4 of [AIMA-2] (as used in fall 2011)
  • Example of A* search on the eight-tile puzzle, using the "number of misplaced tiles" heuristic, as used in class on 2014-02-25
  • Example of use Depth-First Search, Heuristic Depth-First Search, and Best-First Search, as written in class on 2014-02-25
  • Notes on properties of A*, as written in class on 2011-09-08
  • Notes on computing heuristics by problem relaxation, as written in class of 2011-09-13
  • Three properties of heuristics computed by problem relaxation, as written in class on 2014-03-04
  • Example of A* with a Non-Monotone Heuristic Re-Expanding Closed Nodes.
  • Notes on Dynamic Programming for State-Space Search, used on 2014-03-06.
  • Features and Constraints, covering chapter 4 of [P]. (A description of IDA* is given at the beginning of this presentation. A presentation of non-serial DP is given near the end of this presentation.)
  • Notes used on 2014-03-20.
  • Notes used on 2014-03-25.
  • Notes used on 2014-04-01 on exercise 4.3(b) [P].
  • Notes used on 2014-04-01 on exercise 4.3(c) [P].
  • Notes on Nonserial Dynamic Programming used on 2014-04-03; only the pages before "Globally Optimum Storage Patterns" were used.
  • Notes used on 2014-04-08 on assignment HW6 (exercise 4.11[P]).

    Quizzes (In-Class Exercises)
    Quiz 1 of 14-01-21 (with answer)
    Quiz 2 of 14-01-23 (with answer)
    Quiz 3 of 14-01-30 (with answer) (Note that the date on the quiz is incorrect.)
    Quiz 4 of 14-02-04 (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. -->
    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).