Artificial Intelligence - Breadth and Depth Exams

  • Understanding of concepts pertaining to the following topics is required for the breadth examination.
  • In-depth understanding of these concepts and the ability to present formal arguments is required for the depth examination.
  • Preparation: Classes CS555, CS663 and additional reading from textbooks such as:
    1. S. Russell, P. Norvig, Artificial Intelligence, A Modern Approach, Prentice Hall, 1995.
    2. D. Poole, A. Mackworth, R. Goebel, Computational Intelligence, a logical approach, Oxford University Press, 1998
    3. M. Ginsberg, Essentials of Artificial Intelligence, Morgan Kaufmann, 1993
    4. N. J. Nilsson, Artificial Intelligence: a New Synthesis, Morgan Kaufmann, 1998
    5. G. Brewka, J. Dix, K. Konolige, A Tutorial on Nonmonotonic Reasoning  (CSLI Lecture Notes, No 73) (available from Prof. Truszczynski)
  • Topics:
    • Search
      • basic search techniques: depth-first search (Ref 1, Chapter 3; Ref 3, Chapter 3)
      • breadth-first search, iterative deepening (Ref 1, Chapter 3; Ref 3, Chapter 3)
      • informed search: best first, A* (Ref 1, Chapter 4; Ref 3, Chapter 4; Ref 4, Chapter 9; Ref 4, Chapter 8)
      • heuristic searching techniques (Ref 1, Chapter 4; Ref 3, Chapter 4)
      • local search, randomized search (Ref 1, Chapter 4; Ref 3, Chapter 4)
      • game trees, min-max theorem and alpha-beta pruning (Ref 1, Chapter 5; Ref 3, Chapter  5)
    • Constraint satisfaction (Ref 2, Chapter 4.7; Ref 4, Chapter 11.1)
    • Propositional and predicate logic
      • syntax and semantics (Ref 1, Chapters 6 and 7; Ref 3, Chapters 7 and 8)
      • Herbrand models (Ref 1, Chapters 7 and 9)
      • completeness, compactness (Ref 1, Chapter 9; Ref 3, Chapter 6)
      • universal theories, skolemization, normal forms (Ref 1, Chapter 9; Ref 3, Chapters 7 and 8)
    • Knowledge representation
      • closed world assumption (Ref 2, Chapter 7.4; Ref 4, Chapter 18; Ref 5)
      • logic programming, stable model semantics, well-founded semantics (Ref 5, Ref 1, Chapter 10)
      • default logic (Ref 5, Ref 3, Chapter 11; Ref 4, Chapter 18)
      • modal logics (Ref 5, Ref 4, Chapter 23.3; Ref 2, Chapter 7.8)
    • Assumption-based reasoning (Ref 2, Chapter 9)
      • abduction and diagnosis (Ref 2, Chapter 9; Ref 3, Chapter 10)
      • truth-maintenance systems
    • Knowledge-based systems,
      • knowledge engineering  (Ref 2, Chapter 6; Ref 3, Chapter 18; Ref 4, Chapter 17)
      • production systems (Ref 1, Chapter 10; Ref 4, Chapter 1)
      • expert systems (Ref 3, Chapter 18)
    • Planning
      • theory of actions (Ref 1, Chapter  11, 13;  Ref 2, Chapter 8; Ref 3, Chapter 14; Ref 4, Chapters 21, 22)
      • situation calculus (Ref 1, Chapters 11, 12, 13; Ref 2, Chapter8; Ref 3, Chapter 14, Ref 4, Chapter 21)
      • reasoning about actions (Ref 1, Chapter  11, 13;  Ref 2, Chapter 8; Ref 3 Chapter 14)
      • STRIPS (Ref 1, Chapter 11; Ref 2, Chapter 8; Ref 3, Chapter 14)
      • planning under uncertainty (Ref 1, Chapter  17)
    • Machine learning
      • version space algorithm (Ref 1, Chapter 18; Ref 3, Chapter 15)
      • decision trees (Ref 1, Chapter 18; Ref 3, Chapter 15)
      • ID3 algorithm (Ref 1, Chapter 18; Ref 3, Chapter 15)
      • neural networks (Ref 1, Chapter 19; Ref 4 Chapter 3)
    • Reasoning with uncertainty and incomplete information,
      • bayesian nets (Ref 1, Chapters 14, 15;  Ref 2, Chapter 10; Ref 4 Chapter 19)
      • fuzzy sets, fuzzy logic (Ref 1, Chapter 15)
    • natural language processing (Ref 1, Chapters 22, 23; Ref 3, Chapter )