Tuesdays and Thursdays from 10:30-Noon in GHC 4307.

This class is taught by Professors Geoff Gordon and Tuomas Sandholm. The TAs are Abe Othman and Erik Zawadzki.

Office hours are at noon after class on Tuesday (Tuomas - GHC 9205) and Thursday (Geoff - GHC 8105). Abe and Erik have their office hours Monday at 8pm and Wednesday at 4pm in GHC 9225. Recitations will take place Fridays at 3pm in GHC 4307.

January 11, 13, 18 - Logic. Propositional Logic. First-order Logic. Resolution and Unification. Proofs. Satisfiability. Reading: Chapters 7-9 of Russell & Norvig. Slides: Introduction. January 11 (annotated). January 13 (annotated). January 18 (annotated).

January 20, 25, 27, February 1 - CSPs/SAT. Theorem Proving as Search. Techniques for Constraint Satisfaction Problems including Ordering Heuristics, Forward Checking, Arc Consistency, Conflict-Directed Backjumping, Constraint/Clause Learning, Cutsets, Tree Decomposition, Phase Transitions, Iterative Refinement, and DPLL. Reading: Chapter 5 of Russel & Norvig. GRASP: A Search Algorithm for Propositional Satisfiability, Marques-Silva & Sakallah. Chaff: Engineering an Efficient SAT Solver, Moskewicz et al. BerkMin: a Fast and Robust Sat-Solver, Goldberg & Novikov. Conflict-Directed Backjumping Revisited, Chen & van Beek. Slides: FOL Resolution Strategies and Search I, January 20. January 25, January 27, February 1.

February 3, 8 - LP, duality. Reading:

- Section 4.3 and 4.3.1 of Convex Optimization, Boyd & Vandenberghe.
- Bertsimas and Tsitsiklis - Chapter 2 and 3
- Chaper 12 of Approximation Algorithms, Vazirani.

February 10, 15, 17, 22 - Informed search, IP. Slides: February 10, February 15.

February 24, March 1 - Planning. Partial Order Planning. Graphplan/SATplan. Reading: Chapters 11 and 12 of Russell & Norvig. Slides: February 24, March 1 (annotated).

March 3 - Probabilistic inference. Basic Probability including Marginals, Conditionals, and Integration/Summation. Maximum Likelihood and its relation to optimization. Slides: March 3.

*March 8, 10 - Spring break, no classes*

March 15, 17, 22, 24 - Probabilistic inference. Variable Elimination and Factor Graph Inference in Undirected Graphical Models (MRFs), and their relation to SAT. Gradient Descent Learning. Techniques for MCMC. Optional Reading: Factor graphs and the sum-product algorithm , Kschischang et al. Slides: March 15 (annotated), March 17, March 22 (annotated), March 24 (annotated).

*March 29 - Midterm Exam*

March 31 - MDP/POMDP. Slides: March 31 (annotated).

April 5, 7, 12 - Games. Game Types and Forms. Solutions Concepts and Complexity. Algorithms for Solving Normal Form Games. Sequential Games of Complete and Incomplete Information. Correlated Equilibrium. April 5 (annotated) (Geoff), April 5 (Tuomas I), April 5 (Tuomas II), April 12.

*April 14 - Carnival, no classes*

April 19, 21 - Games, cont. Slides: April 19 (revised), April 21 (revised).

April 26 - Multiagent Learning. No-external-regret and No-Phi-regret.

April 28 - Mechanism Design. Setting. The Gibbard-Satterthwaite Impossibility and the Vickrey-Clarke-Groves Mechanism. Auctions. Automated Mechanism Design. April 28

Homework One [tex]: Out January 18, In February 1.

Homework Two [tex]: Out February 1, In February 15. Problem files and verifier: [tgz]

Homework Three: Out February 15, In March 1. Relevant files: tracts.txt, neighbors.txt.

Homework Four: Out March 1, In March 22. Relevant file: times.txt.

Homework Five [tex]: Out March 29, In April 12. File of observations: [obs.dat].

Homework Six: Out April 26, In May 10.

The submission directory is

/afs/cs/user/aothman/dropboxLet Abe or Erik know if you have any problems using the directory.

The purpose of problem sets in this class is to help you think about the material, not just give us the right answers. If you happen to use any material other than that in the text book or from the lectures, it must be acknowledged clearly with a citation on the submitted solution.

Homeworks will be done individually: each student must hand in their own answers. In addition, each student must write their own code in the programming part of the assignment. It is acceptable, however, for students to collaborate in figuring out answers and helping each other solve the problems. We will be assuming that, as participants in a graduate course, you will be taking the responsibility to make sure you personally understand the solution to any work arising from such collaboration. In preparing your own writeup, you should not refer to any written materials from a joint study session. You also must indicate on each homework with whom you collaborated.

Project proposals are due March 3. These should be two or three pages and should discuss the problem you intend to explore and contingency plans depending on how much progress you are able to make.

A brief one-page progress report is due March 31. A longer three-page progress report, ideally with initial results, is due April 19.

Project presentations will take place May 9th between 1:30 and 4:30 in the GHC 7th floor atrium. Final project reports are due on May 9th as well. 6 double-column pages is a good target for length.

Project teams can have at most three members.

The course textbook is AIMA 3e by Russell and Norvig.

Grades are based on Class Participation (10%), Homeworks (45%), Final Project (25%) and the Exam (20%).

Homeworks are due at the begining of class, unless otherwise specified. You will be allowed **5 total late days** without penalty for the entire semester. Each late day corresponds to 24 hours or part thereof. Once those days are used, you will be penalized according to the policy below: Homework is worth full credit at the beginning of class on the due date. For the next 24 hours, it will be graded so that the highest possible score is equal to the 70th percentile of the distribution of scores of the on-time homeworks. For example, if your raw score is 80 out of 100 points, but the 70th percentile of the HW distribution is 85/100, then you will get credit for 80 * (85/100) = 68 points. For the following 24 hours, it will be graded out of the 40th percentile of the on-time homeworks. Thereafter, it will be worth nothing. You must turn in all of the homeworks, even if for reduced credit, in order to pass the course. Turn in all late homework assignments to Michelle (GHC 8001) or to Charlotte (GHC 8118).

Students entering the class should have a pre-existing working knowledge of linear algebra, calculus, algorithms and data structures, and basic knowledge of computational complexity though the class has been designed to allow students with a strong numerate background to catch up and fully participate. Students should also be able to program in C, C++, Java, Python, or Ruby.

**To audit the class**, you should first register, then fill out an audit form and have one of the instructors sign it. Auditors are required to complete a class project, but no homeworks or exams: that way they can choose to focus their efforts on whichever area of AI most interests them.

**To those outside CMU**, feel free to use the slides and materials available online here. If you use our slides, an appropriate attribution is requested. Please email the instructors with any corrections or improvements.