C676: Reasoning About Knowledge - Fall '00
- Instructor:
- Joe Halpern, 4144 Upson, halpern@cs, 5-9562
- Admin:
- Cindy Robinson, 4146 Upson, cindy@cs, 5-0985
- Classes:
- Tuesday, Thursday 10:10 - 11:25, Hollister 362
- Office hours:
- 11:30-12:30 Tuesdsay, Thursday (or by appointment)
- Text:
- Reasoning About Knowledge (Fagin, Halpern, Moses, Vardi).
(It should be available in the bookstore.)
- Grading:
- There will be no tests or final examination.
There will be problems handed out, typically 3 every Thursday, from the
book. The grade will be based completely on your performance on the
problems. Problems are always due two weeks after they're handed out.
If you hand them in one week after they're handed out, I will grade them
and return them the following week, and you get to hand them in again,
to improve your grade. On a redo, you can get a maximum of 1 point
less than the original value of the problem. (That is, if the problem
was originally out of 10, the most you can get is 9.) I will take the
higher grade.
- Academic Integrity:
- It's OK to discuss the problems with
others, but you MUST write up solutions on your own, and
understand what you are writing.
- Course Outline:
- We will be following the text very closely. Very roughly, we will be
covering one chapter per week. Topics include modal logic, common
knowledge, applying reasoning about knowledge in distributed systems
(and economics, depending on interest), knowledge-based programming,
dealing with logical omniscience, algorithmic knowledge.
Homework
- Week 1: handed out 8/24/00, due 9/7/00 (hand it in 8/31/00 for a
second chance)
- Read Chapter 1, 2.1-2.3
- Do 1.2, 2.4 (ignore the comment in 2(d) about explaning why it's
crucial to think of edges, not nodes, as disappearing)
- Solutions in postscript and pdf
- Week 2: handed out 8/31/00, due 9/14/00 (hand it in 9/7/00 for a
second chance)
- Read Chapter 2, 3.1
- Do 2.9, 2.10, 2.12
- Solutions in postscript and pdf
- Week 3: handed out 9/7/00, due 9/21/00 (hand it in 9/14/00 for a
second chance)
- Read Chapter 3.1, 3.2
- Do 3.10, 3.13, 3.14
- Solutions in postscript and pdf
Suppose $(\is, r, m) \sat \mi{dec - Week 4: handed out 9/14/00, due 9/28/00 (hand it in 9/21/00 for a
second chance)
- Read Chapter 3
- Do 2.11, 3.19, 3.20
- Solutions in postscript and pdf
- Week 5: handed out 9/21/00, due 10/5/00 (hand it in 9/28/00 for a
second chance)
- Read Chapter 4.1-4.4
- Do 3.17(b),(c), 3.18, 4.3
- Solutions in postscript and pdf
- Week 6: handed out 9/28/00, due 10/12/00 (hand it in 10/5/00 for a
second chance)
- Read Chapter 4
- Do 4.9, 4.20, 4.24
- Solutions in postscript and pdf
- Week 7: handed out 10/5/00, due 10/19/00 (hand it in 10/12/00 for a
second chance)
- Read Chapter 5
- Do 4.18, 4.25, 5.7
- Solutions in postscript and pdf
- Week 8: handed out 10/12/00, due 10/26/00 (hand it in 10/19/00 for a
second chance)
- Read Chapters 6.1-6.2
- Do 4.28, 6.2
- Solutions in postscript and pdf
- Week 9: handed out 10/19/00, due 11/2/00 (hand it in 10/26/00 for a
second chance)
- Read Chapters 6.1-6.4
- Do 6.6, 6.13
- Solutions in postscript and
pdf
- Week 10: handed out 10/26/00, due 11/9/00 (hand it in 11/2/00 for a
second chance)
- Read Chapters 6, 7.1-7.2 and Exercises 6.18, 6.19
- Do 6.15, 6.17, 6.21. (Note: for 6.15, you need to explain exactly
what the definition of deciding(N) is.)
- Solutions in postscript and
pdf
- A more detailed discussion of Theorem 6.4.2 and deciding(N), in
postscript and
pdf
- Week 11: handed out 11/2/00, due 11/16/00 (hand it in 11/9/00 for a
second chance)
- Read Chapter 7.
- Do 7.3, 7.4, 7.26
- Solutions in postscript and
pdf
- Week 12: handed out 11/9/00, due 11/22/00 (note that this is a day
early; 11/23 is Thanksgiving; as usual, hand it in 11/16/00 for a
second chance)
- Read Chapter 8 and 9.1-9.3
- Do 7.7, 8.5, 8.9
- Solutions in postscript and
pdf.
- Week 13: handed out 11/16/00, due 11/30/00; hand it in
11/22/00 (the Wednesday before Thanksgiving!) for a second chance)
- Read Chapters 9 and 10; read (but don't hand in) Exercise 9.45
- Do 9.8, 9.14, 9.22 (Note: it used to say 9.9, not 9.8; that was a
typo!)
- Solutions in postscript and pdf.