CS 6766: Reasoning About Uncertainty - Spring 2013
- Instructor: Joe Halpern, 4130 Upson, halpern@cs.cornell.edu, 5-9562
- Admin: Megran McGrane, 4130B Upson, mm2496@cornell.edu 5-0893
- TA: Adam Bjorndahl, Malott 218,
abjorndahl@math.cornell.edu.
- Classes:Tuesday, Thursday 10:10 - 11:25; Upson 315
- Office hours
- Halpern: Wednesdays, 4-5 (in Upson 4130)
- Bjorndahl: Tuesdays 11:30 - 12:30 (in Upson 360, Bay C)
- Text: Reasoning About Uncertainty (Halpern).
(It should be available in the bookstore. The paperback version is
marginally better (and should be cheaper), but the hardcover version is
OK too. The paperback version
corrects a number of typos and minor errors in the hardcover version.)
Unfortunately, there are still typos in paperback version; a list of
those that have been discovered so far can be found at
http://mitpress2.mit.edu/catalog/item/default.asp?ttype=2&tid=10758&xid=13&xcid=8006.
I'm sure there are even more lurking in the book; if you discover any,
let me know!
- 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. You can then redo any problem that
you seriously attempted and hand it 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 approaches to
representing uncertainty, updating, representing uncertainty in
multiagent systems, logics of reasoning about uncertainty, and default
reasoning. The material should be relevant to philosophy and game
theory as well as CS; I'll try to bring out the connections as we go along.
- Webpage: The course URL is
http://www.cs.cornell.edu/courses/cs6766/2013sp. Assignments will be
posted there, as well as other class information.
Homework
Note: you can find your grades and solutions to the homework at
CMS.
Week 1: handed out 1/24; due 2/7 (hand it in 1/31 for a second chance)
- Read Chapters 1, 2.1-2.3
- Do 2.5, 2.14, 2.16. In 2.5, change the second two occurrence of >=
to >.
Week 2: handed out 1/31; due 2/14 (hand it in 2/7 for a second chance)
- Read Chapter 2
- Do 2.28, 2.36, 2.57
Week 3: handed out 2/7; due 2/21 (hand it in 2/14 for a second chance)
- Read Chapter 3.1 - 3.3
- Do 3.2, 3.7, 3.8
Week 4: handed out 2/14; due 2/28 (hand it in 2/21 for a second chance)
- Read Chapter 3
- Do 3.16 (5 points), 3.23, 3.41 (5 points), 3.44
Week 5: handed out 2/21; due 3/7 (hand it in 2/28 for a second chance)
- Read Chapter 4
- Do 3.47, 4.18, 4.24(a),(b),(c)
Week 6: handed out 2/28; due 3/14 (hand it in 3/7 for a second chance)
- Read Chapter 5
- Do 4.8, 5.5, 5.8 (there's a typo in 5.8: the subscript on E should
be calligraphic P, not \mu)
Week 7: handed out 3/7; due 3/28 (hand it in 3/14 for a second chance)
- Read Chapter 6
- Do 5.10, 5.15, 6.4
Week 8: handed out 3/14; due 4/4 (hand it in 3/28 for a second chance)
Week 9: handed out 3/28; due 4/11 (hand it in 4/4 for a second chance)
- Read Chapter 7
- Do 6.18, 7.10, 7.11
Week 10: handed out 4/4; due 4/18 (hand it in 4/11 for a second chance)
- Read Chapter 8.1-8.2
- Do 7.22, 7.26, 8.5. For 7.26, you should find two structures M and
M' that have the same set W of worlds and the same interpretation \pi.
For each worldld w in and each formula phi in L_n^{QU}, we have
(M,w)|= phi iff (M',w)|= phi, so M and M' agree on formulas in L_n^{QU}
in this strong sense. However, M and M' disagree on the formula
e_1(p+q) > 1/2.
You can take M and M' so that there is only 1 player, |W|=3, all the
worlds in M agree on the set of probability measures and there are only
2 of them, while in M' there are 3 of them.
Week 11: handed out 4/11; due 4/25 (hand it in 4/11 for a second chance)
- Read Chapter 8
- Do 8.28, 8.34, 8.48
Week 12: (final homework!) handed out 4/18; due 5/2 (hand it in 4/25 for
a second chance)
- Read Chapter 9
- 8.38, 9.7, 9.15.