August 22 (Fri), 2008 Quiz 1 (Q1). Administrative information: textbook, syllabus, grading policy. Q1 is based on a video of a panel on AI at the Charlie Rose show: http://www.youtube.com/watch?v=oEstOd8xyeQ.
August 25 (Mon), 2008 Q2. Video completed, with discussion. More administrative information. Graduate student presentations: overview of the first three topics.
August 27 (Wed), 2008 No quiz. HW1 assigned. A little music before starting the lecture: Glenn Gould's 1955 performance of Bach's Goldberg Variations, re-performed by a computer program in 2006. Definitions of AI, subareas, a bit of history (Ch.1 [AIMA]). Chapter 2 [AIMA]: Intelligent Agents, to p. 36.
August 29 (Fri), 2008 No quiz. HW2 assigned. First three graduate presentations assigned. Chapter 2 [AIMA] completed.
September 3 (Wed), 2008 Q3. Issues from Ch.1 [P]: Succinctness (conciseness) of representations: state-space, features or propositions, objects and relations; Bounded rationality and anytime algorithms; complexity of some representational frameworks. Beginning of Ch.3 [AIMA]: Blind search.
September 5 (Fri), 2008 HW3 assigned. More on issues from Chs. 1 and 2 of [P]
September 8 (Mon), 2008 Ch.3 [AIMA]: Blind search. (Note: some changes to the slides on the linear placement problem were made on 09/09.)
September 10 (Wed), 2008 First graduate student presentation: Optimality of Dijkstra's Algorithm
September 12 (Fri), 2008 HW4 assigned. More on Dijkstra's Algorithm---notes from various sources; see slides in notes section of this web site for outline and sketches of proofs.
September 15 (Mon), 2008 Greedy Best-First Search. A*.
September 17 (Wed), 2008 HW3 collected. Proof of admissibility of A* from Judea Pearl's _Heuristics_ (1984), in detail: handout. Beginning of presentation on the optimality of A* by Waggoner and Cleveland.
September 19 (Fri), 2008 No new HW assigned. Midterm will be Wednesday, September 24. Exercises recommended to prepare for midterm: 4.1, 4.5, 4.12, 4.14 [AIMA]; 3.3, 3.8, 3.9 [P]. Presentation on the optimality of A* by Waggoner and Cleveland, completed.
September 22 (Mon), 2008 Reminder: midterm will be on Wednesday, September 24. Discussion of exercise 3.4 (8 puzzle states are divided into two disjoint sets), with Dylan Kane presenting his solution. Q&A on exercise 3.14. First part of presentation on sliding tile puzzle heuristics by Cao and Gause.
September 24 (Wed), 2008 MT1.
September 26 (Fri), 2008 Discussion of MT1 results. PR1 assigned: exercises 1,3,4,6 from handout on the object-oriented design of programs for state-space search and their implementation in Java, due Wednesday, October 8. There will be guest lectures on Monday, September 29 and Friday, October 3. There will be no class on Wednesday, October 1. Office hours are canceled for next week.
September 29 (Mon), 2008 Presentation by Hannah T. Nicol of the career center. Students are required to sign up to JobMate for quiz credit.
October 1 (Wed), 2008 No class
October 3 (Fri), 2008 Jingsong Wang presents the design and implementation of several search algorithm (depth-first, breadth-first, best-first) in Java.
October 6 (Mon), 2008 PR1 due date moved to Monday, October 13. Constraint Propagation. Presentation following Chapter 4 [P], through section 4.4.
October 8 (Wed), 2008 Discussion of PR1 submission format. Constraint propagation, through section 4.6: arc consistency.
October 13 (Mon), 2008 PR1 collected. Constraint propagation, using the applets at AISpace.
October 15 (Wed), 2008 HW5 will consist of exercises 5.1, 5.3, 5.5, 5.8, and comments to Ch.4 [P]. Complexity analysis of GAC (AC-3 arc consistency algorithm for CSP). Discussion of how the complexity of UNIQUE-SAT implies that GAC (AC-3) is not complete for UNIQUE-SAT instances. Propositional CSPs. Variable elimination, presented using relational algebra.
October 17 (Fri), 2008 HW5 assigned: exercises 5.1, 5.3, 5.5, 5.8 [AIMA] and comments to Ch.4 [P], due Wednesday, October 22, 2008. Exploiting problem structure in CSPs" cutset conditioninng and join (junction) trees. Non-serial dynamic programming.
October 20 (Mon), 2008 Non-serial dynamic programming: extensions, with samples of problems that can be solved using it; glimpse of Shenoy's axioms for the applicability of NSDP; the original (1960) Davis-Putnam algorithm for satisfiability of clausal-form propositional formulas.
October 22 (Wed), 2008 Local search (section 4.8 [P]), with several demonstrations using the AIspace applet for stochastic local search.
October 24 (Fri), 2008 HW6 assigned: exercises 4.13 [P]; 5.11 & 5.12 [AIMA]; comments on 10.1-10.3 (except 10.2.3) [P], due Wednesday, October 29, 2008.
October 27 (Mon), 2008 Ch. 7 [AIMA] (Logical Agents) started: through section 7.3, and an introduction to propositional logic using the first few pages of the Yasuhara handout (ch. 9 of: Ann Yasuhara. _Recursive Function Theory and Logic_. Academic Press, 1971.)
October 29 (Mon), 2008 Brief discussion of PR1 results. Propositional logic continued. Yasuhara handaout, through section 9.3, and brief coverage of the rest.
October 31 (Fri), 2008 HW7 assigned: exercises 7.1, 7.2, 7.4, 7.5, 7.6, 7.8, 7.9, 7.10, 7.12, 7.16 [AIMA]; read sections 5.1 and 5.2 [P] and post as usual. Propositional logic through the resolution inference rule.
November 3 (Mon), 2008 Brief Q&A on HW7. Clausal form, conjunctive normal form. Resolution and resolution refutation1 with example. Horn clauses. Definite clauses as a subset of Horn clauses.
November 5 (Wed), 2008 Definite clauses: examples, bottom-up algorithm (forward chaining) with proof of soundness and completeness; examples. Queries and answer clauses. Top-down algorithm (backward chaining).
November 7 (Fri), 2008 HW7 deadline extended to Monday, November 10. Mr. Wang will guest lecture (on Prolog) on Monday. Satisfiability for Horn clauses (including indefinite ones): Uwe Schoening's sound and complete algorithm (placed on slide for Ch.7). Satisfiability for the general propositional case: (1) DPLL, a sound and complete algorithm; (2) WalkSAT, a local constraint propagation algorithm that is sound but not complete. Complexity of SAT problem instances and the 4.3 ratio between clauses and propositions (or literals?). Limited expressivity of propositional logic exemplified by the Wumpus game. Circui-based logic agents as an example of agents with state. Limitations of the circuit-based approach. Ch. 7 completed.
November 10 (Mon), 2008 Guest lecture on Prolog: Mr. Jingsong Wang.
November 12 (Wed), 2008 First-Order Logic: Ch.8 through section 8.3
November 14 (Fri), 2008 HW8 assigned (see homework list on web site). Ch.8 completed.
November 17 (Mon), 2008 Inference in First-Order Logic: Ch. 9 started: propositionalization (with skolemization and Herbrand's theorem: section 9.1) and unification (section 9.2, started).
November 19 (Wed), 2008 HW8 updated (see Homework section of web site), with deadline of Friday, November 21; exercise 8.14 on Lists is no longer due; it was soleved and discussed in class. Forward chaining, with mention of the rete algorithm and an example with definite clauses without functions (a datalog KB).
November 21 (Fri), 2008 No new HW assigned. Backward chaining, Prolog, incompleteness of backward chaining, adding contrapositives and ancestor checking, Prolog Technology Theorem Prover. Binary resolution is incomplete: the Barber's example (started).
November 24 (Mon), 2008 HW9 assigned, due Wednesday, December 3, 2008. (See homework section on web site.) Three undergraduate students taking the course for graduate credit will present their research on natural deduction, very likely on December 5. A review session will take place during the week of December 1, very likely outside of class time. Ch. 9 completed.
December 1 (Mon), 2008 Q&A on HW9. Learning by Observation: Introduction.
December 3 (Wed), 2008 Discussion of skolemization, with exercise 9.19(f) as example. Learning decision trees (19.3 [AIMA]), completed. There will be a review session from 11-12 on Thursday, December 4, 2008, in room 3A75. Update: notes from the review session are linked to the main web site for the course.
December 5 (Fri), 2008 Student presentation on natural deduction. Discussion of boosting (AdaBoost, in particular) and a very brief introduction to computational learning theory. End of course.