CSC 244/444 Fall 2010 Calendar of Classes and Assignments

Readings other than the textbooks that do not appear with hyperlinks below can be found in by clicking Reserves on the left menu bar in Blackboard.

date classwork assignments
Thur Sept 2 1. Introduction to the course 1. Read B&L Chapter 1. Respond:
- What is knowledge?
- What is representation?
- What is reasoning?
Due by 10pm Monday Sept 6.
Tues Sept 7

2. Knowledge representation and reasoning

B&L Ch 1

2. Read B&L Ch 2.1-2.4. Respond:
- What is the difference between a "logical symbol" and a "non-logical symbol"?
- What is an "interpretation" of logic?
- What does it mean for a FOL sentence A to be a logical consequence of another sentence B?
- Write two specific sentences such that one is a logical consequence of the other, and explain in detail (using the definition of logical consequence) why that is the case.
Due by 10pm Monday Sept 13.

3. Read B&L Ch 2.5. Respond:
- Describe the relationship between logical consequence, unsatisfiability, and validity.
- What is the relationship between the entailment symbol "|=" and the logical connective "=>"?
Due by 10pm Wednesday Sept 15.

Thur Sept 9 class cancelled  
Tues Sept 14

3. The language of first-order logic

B&L Ch 2

Thur Sept 16

4. The language of first-order logic, continued

Read B&L Ch 3. Free-form response.
Due by 10pm Monday Sept 20.

Exercise Set 1: Interpretations & Models
Due (hardcopy) start of class Tuesday Sept 28.

Tues Sept 21

5. Expressing Knowledge

B&L Ch 3

4. Read B&L Ch 4. Respond:
- What is the important different between an empty clausal formula and a formula containing the empty clause?
- What is a resolution derivation?
- What does it mean to say resolution is "refutation complete"?
Due by 10pm Monday Sept 27

Thur Sept 23 class cancelled  
Tues Sept 28

6. Resolution

B&L Ch 5

Thurs Sept 30

7. Resolution, continued

Exercise Set 2: Resolution Proofs
Due (hardcopy) start of class Thursday Oct 7

5. Reading: B&L Ch 4 Exercises 5 and 6 (don't solve them, just read them); also Section 2.3 of the paper by Gomes et al., Satisfiability Solvers, 2008 (See course reserves).
- Create an example, different from the one in the text, of using the "big dot" operator defined in Exercise 5.
- Answer 6(a): show how you could modify the pseudo-code for DP to return a satisfying assignment (set of literals).
- What might be the relationship between your modified DP algorithm and the "tree of partial interpretations" that I presented in the proof of completeness of resolution in class today?
- If you consider DP and Walksat to be search algorithms, what is the difference between the state space searched by DP and the state space searched by Walksat?
Due by 10pm Wednesday Oct 6th.

Tues Oct 5

8. Resolution, continued


Thur Oct 7

9. Resolution, continued

Programming Assignment 1: Build a SAT Solver
Due by turn-in by 11:59pm Tuesday Oct 26
Tues Oct 12

10. Basic satisfiability algorithms

B&L Ch 5 exercises 5 and 6

Section 2.3 of C. P. Gomes, H. Kautz, A. Sabharwal, & B. Selman, Satisfiability Solvers, in F. van Harmelen, V. Lifschitz, & B. Porter, Eds., Handbook of Knowledge Representation, in the series Foundations of Artificial Intelligence, Vol. 3, Elsevier, 2008. (See course reserves)

Read the section in R&N on "Planning with Propositional Logic" (2nd Edition, Sec. 11.5; 3rd Edition, Sec. 10.4.1). Write a short (one paragraph) response summarizing the basic idea of how planning problems can be turned into SAT. Due by 10pm Wednesday Oct 13. The Subject: line of your response should be exactly the following:
Subject: Reading Oct 13 SATPLAN
Thur Oct 14

11. Planning as satisfiability

A. Blum and M. Furst, Fast Planning Through Planning Graph Analysis, Artificial Intelligence, 90:281-300 (1997).

Henry Kautz and Bart Selman, Pushing the Envelope: Planning, Propositional Logic, and Stochastic Search, Proc. AAAI-96.

Tues Oct 19

12. Modern satisfiability algorithms

C. P. Gomes, H. Kautz, A. Sabharwal, & B. Selman, Satisfiability Solvers, in F. van Harmelen, V. Lifschitz, & B. Porter, Eds., Handbook of Knowledge Representation, in the series Foundations of Artificial Intelligence, Vol. 3, Elsevier, 2008. (See course reserves)

Midterm Review Sheet

Read the section B&L Chapters 5 and 6. Respond to the questions:
- Complete the sentence: "In SLD resolution, the leaf at the top of the tree is aways the _________, and the leafs along the left side of the tree are ___________."
- For the propositional case, why is forward-chaining more efficient than backward chaining for reasoning with Horn clauses?
- Why does the book call PROLOG an example of "procedural control of reasoning"?
Due by 10pm Monday Oct 25. The Subject: line of your response should be exactly the following:
Subject: Reading Oct 25 PROLOG
Thur Oct 21 Midterm exam  
Tues Oct 26

13. Horn Clauses

B&L Ch 5

Thur Oct 28

14. Prolog

B&L Ch 6

Reading: B&L Ch 11, Sections 11.1, 11.2.1-11.2.4, and 11.4. Respond:
- What is the connection between "negation as failure" (Sec. 6.7) and the closed world assumption?
- Is the closed world assumption always consistent when applied to a Horn theory?
- How can the closed world assumption be written in Default Logic?
Due: Monday Nov 1, 10:00pm by Blackboard Turn In (NOT email)

Tues Nov 2

15. More Prolog


Thur Nov 4

16. Default Reasoning

Quasigroup Demo

B&L Ch 11

Programming Assignment 2: Problem Solving in Prolog
Due by Blackboard Turn In 11:59pm on Thursday December 9th.

Reading: B&L Ch 13. Respond:
- Is every abductive diagnosis also a consistency based diagnosis? What about the reverse? Why?
- Describe a real life example where you would be happy to accept a consistency-based diagnosis, and one where you would insist on an abductive diagnosis.
Due: Monday Nov 8, 10:10pm by Blackboard Turn In (NOT email)

Tues Nov 9

16. Explanation and diagnosis

B&L Ch 13

Homework: Problem 3, pg 283 in B&L. Due Nov 16 in class.
Thur Nov 11

17. SAT-modulo theories

C. Barrett, R. Sebastiani, S. A. Seshia, & C. Tinelli, Satisfiability Modulo Theories, in A. Biere, H. van Maaren, M. Heule and Toby Walsh, Eds., Handbook of Satisfiability, IOS Press, 2009.(See course reserves)

Example of eager encoding

Homework (due Nov 18 in class)

TDPLL Online Schema.pdf

Tues Nov 16

19. Reasoning about the knowledge of multiple agents

J. Halpern, Reasoning about knowledge: a survey, in D. Gabbay, C. J. Hogger, and J. A. Robinson, Eds.,Handbook of Logic in Artificial Intelligence and Logic Programming, Vol. 4, Oxford University Press, 1995.

Homework (due Nov 23 in class)
Thur Nov 18

20. Limited and approximate inference

Liu, Y., Lakemeyer, G., and Levesque, H., A logic of limited belief for reasoning with disjunctive information, Proc. of the KR-2004 Conference, Whistler, BC, 2004.

H. Kautz and B. Selman, A General Framework for Knowledge Compilation, Proceedings of the First World Conference on the. Fundamentals of Artificial Intelligence, Paris, 1991.

Homework - due Nov 30 in class
Tues Nov 23

21. Bayesian networks

B&L 12.1-12.4; R&N 14.5

Homework: Problem 4 in section 12.6 (pg 265) of the B&L textbook with the following changes: do only parts a, b, d(i-iii). Due Nov 30 in class.
Thur Nov 25 Thanksgiving break  
Tues Nov 30

22. Bayesian reasoning using MAX-SAT and model-counting

J. D. Park, Using Weighted MAX-SAT Engines to Solve MPE, Proceedings of the Eighteenth National Conference on Artificial Intelligence (AAAI-02), Edmonton, Alberta, 2002, pages 682-687.

T. Sang, P. Beame, & H. Kautz., Solving Bayesian Networks by Weighted Model Counting, Proceedings of the Twentieth National Conference on Artificial Intelligence (AAAI-05), Pittsburgh, PA, 2005.

Slide deck 1

Slide deck 2

Homework - due in class Dec 7

Thur Dec 2

23. Markov logic

P. Domingos & D. Lowd, Markov Logic: An Interface Layer for Artificial Intelligence, Synthesis Lectures on Artificial Intelligence and Machine Learning, Morgan & Claypool, 2009. (See course reserves)

Homework - due in class Dec 9

Tues Dec 7

24. Markov logic, continued (additional slides)

Thur Dec 9

25. Review of course since midterm and limits of logic

pdf version of slides

Mon Dec 20 Take-home final exam. Available for download from this page on Monday Dec 13. Due by turn-in by 11:59pm on Monday Dec 20. The exam will be designed to be completed in approximately 3 hours.  

Back to course home