CS 6766: Reasoning About Uncertainty - Fall 2019

Instructor: Joe Halpern, 414 Gates, halpern@cs.cornell.edu, 5-9562
Admin: Randy Hess, 401 Gates, rbhess@cs.cornell.edu, 5-0985
TAs: Shawn Ong, Oliver Richardson
Classes:Tuesday, Thursday 2:55 - 4:10, 1120 Snee
Office hours
Halpern: Wednesdays, 2:30 - 3:30 in 414 Gates
Ong: Mondays 5:30-7 in Rhodes 657 Conerence Room
Richardson: Monday 5:30-7:00 in Rhodes 657 Conference Room
Text: Reasoning About Uncertainty (2nd edition) (Halpern). There is also a first edition of the book available; the second edition has about 60 extra pages, as well as correcting typos and minor problems in the first edition. (If you find further typos, let me know!) For the most part, you should be able to get away with the first edition. The library has online access to (one copy of) the second edition.

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/2019fa. Assignments will be posted there, as well as other class information. We will also have a Piazza site.



  • Week 1: handed out 9/3; due 9/17 (hand it in 9/10 for a second chance)
    • Read Chapters 1, 2.1-2.3
    • Do 2.5, 2.7, 2.8, 2.16
  • Week 2: handed out 9/10; due 9/24 (hand it in 9/17 for a second chance)
    • Read Chapter 2
    • Do 2.33, 2.41, 2.62(a),(c),(d)
  • Week 3: handed out 9/17; due 10/1 (hand it in 9/24 for a second chance)
    • Read Chapter 3
    • Do 3.6, 3.11, 3.12
    • Think about (but don't hand in) 2.30 and 2.31.
  • Week 4: handed out 9/24; due 10/8 (hand it in 10/1 for a second chance)
    • Do 3.28, 3.31, 3.48
  • Week 5: handed out 10/1; due 10/17 (hand it in 10/8 for a second chance)
    • Read Chapter 4
    • 3.51, 4.18, 4.24(a),(b),(c)
  • Week 6: handed out 10/8; due 10/24 (hand it in 10/17 for a second chance)
    • Note that the due date has been changed to 10/24 (from 10/22)
    • Read Chapter 5
    • Do 5.5, 5.8, 5.10
    • Think about (but don't hand in) 5.7
  • Week 7: handed out 10/17; due 10/31 (hand it in 10/24 for a second chance); note that homework is now being handed out and is due on Thursdays!
    • Read Chapter 6.1 - 6.5
    • 5.15, 5.36, 6.4. (New addition as of 10/24: for 5.15, you can assume that the set W of worlds is finite.
  • Week 8: handed out 10/24; due 11/7 (hand it in 10/31 for a second chance); note that homework is now being handed out and is due on Thursdays!
    • Read Chapter 6
    • Do 6.6, 6.7, and the following problem: construct a protocol for Alice in the second-ace puzzle so that, after the first step, the probability (according to Bob) that Alice has both aces is 1/5, and after the second step, the probability that she has both aces if 1/3, both if she says "I have the ace of spades" and if she says "I have the ace of hearts". (Think about why it doesn't follow that Bob can already say at step 1 that the probability that Alice has both aces is 1/3.)
    • Think about, but don't hand in, 6.14.
  • Week 9: handed out 10/31; due 11/14 (hand it in 11/7 for a second chance).
    • Read Chapter 7
    • Do 6.18, 7.10, 7.20
  • Week 10: handed out 11/7; due 11/21 (hand it in 11/14 for a second chance). Since there's no class during the regular class time on 11/14, I'll leave it to Oliver and Shawn to figure out how you should hand in the homework for those of you not handing it in online.
    • Read Chapter 8.1
    • Do 7.21, 7.25, 8.5
    • Class next week will be held at 8:45 - 10:00 PM on Monday and Wednesday next week, since I'll be in China. (There were two people who could make 8:30 - 9:45 but couldn't make 9-10:15, and two who could make 9-10:15 but couldn't make 8:30-9:45. I'm hoping that by splitting the difference, all four of them can attend most of it. I realize that there are still some people who will have to miss a lecture; unfortunately there were no times that worked for everyone. The lectures will be videotaped, so you can watch what you missed. The instructions for attending class are as before: just go to https://cornell.zoom.us/j/7829125613. Recall that when you join the meeting/class, your microphone will be muted. Don't forget to unmute it if you want to ask a question!
    • Since I won't be in town next week, my office hours are canceled. But if you have questions, don't hesitate to email me (and/or go to Oliver/Shawn's office hour).
  • Week 11: handed out 11/14; due 12/3 (hand it in 11/21 for a second chance).
    • Read Chapter 8
    • Do 8.7(a),(b), 8.28, 8.34 (do it only for \M^{ps}, \M^{poss}, \M^{tot}, and \M^{qual}), 8.37(a),(b)
    • Think about (but don't hand in) 8.13, 8.14, 8.20, 8.26 (they're easy, but good for intuition).
    • Zoom problems: I'm having problems getting zoom to work in China. The only way I seem to be able to do it is to use my cell phone as a hot spot. But for some reason I then get meeting url as https://cornell.zoom.us/j/121469180, not https://cornell.zoom.us/j/7829125613. I would suggest that you try both, and see which one I'm on (most likely the first). Connectivity may not be great with my cell phone ...
    • Here are my slides for my two classes this week. (The slides are are slightly expanded and corrected from what I actually presented last class.) I made it to roughly slide 18/30 (page 47 of the pdf) in the first class, but I'll start reviewing from slide 15, to hopefully bring everyone to the same page. Unfortunately, because of the zoom problems, neither class was videotaped. Sorry about that ...
  • Week 12 (the last one!): handed out 11/21; due 12/10 (hand it in 12/3 for a second chance).
    • Read Chapter 10
    • Do 8.38, 10.18, 10.24
    Since attendance on Tuesday (nov. 26) was pretty sparse, here are my my slides for the second part of the class, which covered applying PS structures to security (which is also covered in Section 10.5 of the text).