Artificial Intelligence
Spring 2007
Qualifying Exam Information

Date: January 10, 2007 (Wednesday)
Time: 9:00am - 1:00pm (4 hours)


The exam will be closed book and notes. It will contain questions from the general material normally discussed in CS4811 and CS5811. In addition, three recent papers are included. A listing of the topics covered and this year's papers are below.

Textbooks:

Additional resources:

See the class web sites:

Topics covered:

  1. Agent-based architectures
    1. Specifying task environments
    2. Agent types: simple reflex, model-based reflex, goal-based, utility based, learning

    [RUSSELL-NORVIG]
       Chapter 2 (Intelligent Agents)

  2. Predicate calculus
    1. Propositional logic, propositional inference
    2. First-order logic
    3. Unification, lifting
    4. Resolution theorem proving

    [LUGER]
       Chapter 2 (The Predicate Calculus)
       Chapter 12 (Automated Reasoning)
    [RUSSELL-NORVIG]
       Chapter 7 (Logical Agents)
       Chapter 8 (First-Order Logic)
       Chapter 9 (Inference in First-Order Logic)
     
  3. Uninformed Search
    1. Depth-first search, breadth-first search, depth-limited search, iterative-deepening depth first search, bidirectional search
    2. Comparing uninformed search strategies

    [LUGER]
       Chapter 3 (Structures and Strategies for State Space Search)
    [RUSSELL-NORVIG]
       Chapter 3 (Problem Solving by Searching)
     
  4. Heuristic Search
    1. Best first search, A* search
    2. Admissability, monotonicity, informedness
    3. Designing heuristics
    4. Local search algorithms: hill-climbing, simulated annealing
    5. Constraint satisfaction problems
    6. Adversarial search, the minimax algorithm

    [LUGER]
       Chapter 4 (Heuristic Search)
       Chapter 6 (Building Control Algorithms for State Space Search)
    [RUSSELL-NORVIG]
       Chapter 4 (Informed Search and Exploration)
       Chapter 5 (Constraint Satisfaction Problems)
       Chapter 6 (Adversarial Search)
     
  5. Knowledge Representation
    1. Conceptual graphs
    2. Conceptual dependency graphs
    3. Truth maintenance systems
    4. Frames
    5. Semantic networks

    [LUGER]
       Chapter 7 (Knowledge Representation)
    [RUSSELL-NORVIG]
       Chapter 10 (Knowledge Representation)
     
  6. Expert Systems
    1. Rule-based expert systems
    2. Model-based sytems
    3. Inference and explanation in Expert Systems

    [LUGER]
       Chapter 8 (Strong Method Problem Solving)
     
  7. Planning
    1. Representing planning problems in PDDL
    2. Planning with state-space search
    3. Partial-order planning
    4. Planning graphs
    5. Satisfiability-based planning
    6. Planning with temporal and Resource Constraints
    7. Hierachical Task Network Planning
    8. Conditional Planning
    9. Execution Monitoring and Replanning

    [LUGER]
       Chapter 8 (Strong Method Problem Solving)
    [RUSSELL-NORVIG]
       Chapter 11 (Planning)
       Chapter 12 (Planning and Acting in the Real World)
     
  8. Natural Language Understanding
    1. Parsing using context-free grammars
    2. Parsing using context-sensitive grammars
    3. Parsing using augmented transition networks

    [LUGER]
       Chapter 14 (Understanding Natural Language)
     
  9. Machine Learning
    1. Version spaces
    2. Learning decision trees
    3. Clustering
    4. Reinforcement Learning
    5. Perceptron learning
    6. Neural networks

    [LUGER]
       Chapter 10 (Machine Learning: Symbol Based)
       Chapter 11 (Machine Learning: Connectionist)
    [RUSSELL-NORVIG]
       Chapter 18 (Learning from Observations)
       Chapter 19 (Knowledge in Learning)
       Chapter 20 (Statistical Learning Methods)
     
  10. Reasoning Under Uncertainty
    1. Fuzzy Logic
    2. Probability Theory
    3. Bayes' theorem
    4. Bayesian networks
    5. Exact inference in Bayesian networks
    6. Approximate inference in Bayesian networks

    [LUGER]
       Chapter 5 (Stochastic Methods)
       Chapter 9 (Reasoning under uncertain situations)
    [RUSSELL-NORVIG]
       Chapter 13 (Uncertainty)
       Chapter 14 (Probabilistic Reasoning)
     
  11. Decision Theoretic Reasoning
    1. Decision Theory
    2. Influence diagrams
    3. Representing problems as Markov Decision Processes (MDPs)
    4. Value iteration and policy iteration for solving MDPs


    [RUSSELL-NORVIG]
       Chapter 16 (Making Simple Decisions)
       Chapter 17 (Making Complex Decisions)
     

Papers covered:

  1. A Mixed-Initiative Approach to Rule Refinement for Knowledge-Based Agents. Cristina Boicu, Gheorghe Tecuci, Mihai Boicu In Mixed-Initiative Problem-Solving Assistants: Papers from the 2005 Fall Symposium, ed. David W. Aha and Gheorghe Tecuci, Technical Report FS-05-07. American Association for Artificial Intelligence, Menlo Park, California. pp. 1-6.
    ( local copy )
    ( original URL )
  2. A Mixed-Initiative Call Center Application for Appliance Diagnostics. William Cheetham. In Mixed-Initiative Problem-Solving Assistants: Papers from the 2005 Fall Symposium, ed. David W. Aha and Gheorghe Tecuci, Technical Report FS-05-07. American Association for Artificial Intelligence, Menlo Park, California. pp. 22-25.
    ( local copy )
    ( original URL )
  3. Mixed-Initiative in Computer Games: Algorithmic Content Creation in Open-ended Worlds. Liam Doherty, Max Whitney, Jurika Shakya, Mayo Jordanov, Patrick Lougheed, David Brokenshire, Shilpi Rao, Samir Menon, Vive Kumar In Mixed-Initiative Problem-Solving Assistants: Papers from the 2005 Fall Symposium, ed. David W. Aha and Gheorghe Tecuci, Technical Report FS-05-07. American Association for Artificial Intelligence, Menlo Park, California. pp. 46-50.
    ( local copy )
    ( original URL )