CS6766Reasoning about Uncertainty

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.
News:

I won't be in town next Monday-Wednesday (Sept. 30 - Oct. 2). That means that my office hours next Wednesday (Oct. 2) are canceled (sorry!) and I'll be teaching next Tuesday's class over the web. You'll be able to access the class at the regular time (2:55 PM) at the url https://cornell.zoom.us/j/7829125613. Note 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! (You can also call in to the class at 646 876 9923, and then use the Meeting ID 782 912 5613. That's not optimal though -- if you call in, you'll be able to hear the audio, but won't be able to see the video. Since I'll be using slides, you'll definitely miss important material that way.)
Here are my slides for the Oct. 1 class. You can watch the video here.
Since Wednesday is Yom Kippur (a Jewish religious holiday), I won't be in. That means that my office hours will be canceled. But if you have questions, don't hesitate to email me. If necessary, I'll see if we can find another time to meet.
I'll be in China the week of Nov. 11-18. We'll still have class over zoom. Because it will be a 13-hour time difference to China then, we can't have class at the regular time (I don't plan to be up at 3:55 AM to teach the class if I can help it!). Please complete the doodle poll here to determine the best time to teach the class. Note that the Monday, Tuesday, and Thursday time listed as 8:30 - 10 AM are really meant to be 8:40 - 9:55 (to match up with the time of the first Cornell morning class); Doodle doesn't seem to allow times that aren't on the quarter hour, half hour, or hour.

Homework

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)
c
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).

Homework