Computer Science 2802: Discrete Structures  Honors
Spring, 2020
Prof. Joe Halpern
Latebreaking news:
 May 13
 I taught an optional class on graph theory today, focusing on
Eulerian paths and graph coloring. (You can watch the recording
on Canvas.) I've put my complete notes on graph theory, which
includes more material than I covered today, on the course web
sit.
 May 10
 I have updated the notes on automata theory and logic to clarify
a few things.
 The last official class will be on Monday. I will discuss
Godel's theorem (arguably the most important theorem in
mathematics in the 20th century, 01 laws (the fact that all
formulas in certain languages hold with probability 0 or
probability 1)  this is (what I think is) really interesting at
the intersection of logic and probability, and (if there's time)
the muddy children puzzle. If you think that math is fun, you
should enjoy this class. None of it will be on the final.
 I am willing to offer an optional class on Wednesday to
talk about some of the graph theory that I would have discussed
if we hadn't lost a week of classes. I will focus on Eulerian
paths (this is basically the Konigsberg bridge problem that I
discussed in the very first class) and chromatic numbers.
Again, none of this will be on the final. I've posted a poll in
Piazza to get a sense of how many people would attend this
class. Please don't vote yes on the poll unless you expect to
attend the class. I understand that you're all busy;
you definitely shouldn't feel guilty if you don't think you
can or want to attend!
 I'm still working on the final exam. It will be a
takehome, like the second prelim. I expect to post it on either
Thursday, May 21, or Friday, May 22. It will be due on Monday,
May 25, at 10 AM. Office hours will go on as usual until
the exam, unless you hear otherwise (e.g., if a TA has an exam,
and office hour might get canceled or postponed).
 April 20

Update on the prelim: I'll still post it on April 23 at 8 AM, but it
will be due on April 26 at 10 AM. I think it's almost as long as a
typical homework, so don't leave it to the last minute! But this
should accommodate people who have other prelims, or other
assignments. I'm also not going to bother with the integrity
statement, and just trust you not to cheat. You all know the
acamdic integrity policy. If in doubt as to what's acceptable,
feel free to ask!
 Towards the end of the week I'll start with finite automata.
This is not covered in our text. I've posted a handout on
CMS, from which the homework will be taken.
 I will be teaching CS 2802 again next fall (not in the
spring). If you like the material, and like teaching, and are doing
well in the course, you should consider applying to be a TA.
 April 13

We will have a takehome prelim on
April 23. I'll post it at 8 AM, and it will be due at 8 PM the next
day (so you'll have 36 hours). I realize that not everyone is in
the same time zone, but I'm hoping that this will work out for
everyone. If you anticipate having problems for any reason, let me
know. Just as before, you can use the web, the text, and the class
notes, but you can't talk to each other (or anyone else) about the
prelim between when I post it and when you hand it in.
I'm sure that some of you will be concerned that others will take advantage
of the situation. Although I will have all of you sign an academic
integrity form, just as I did for the first prelim, and we will check
for obvious types of cheating, I really am counting on the fact that
all of you have the strength of character to maintain the behavioral
expectations of Cornell students. If you have reason to believe
that, because of the stressful times or for other reasons, the
test will not provide a good representation of your abilities,
please contact me.
 I have posted some background material on the course notes page
about the Lucia de Berk case (where a nurse was accused of murdering
some of her patients), and a related case in England.
 April 7
 As announced on Piazza and email, yesterday's lecture was posted on
Canvas. (I won't bother announcing this in the future, but I plan
to post all lectures there; I'll try to do it within a few hours of
the lecture itself.) If you have any trouble accessing it, let me know!
 There's
a renewed
commitment to academic integrity and equitable intruction in
light of how things have changed since the advent of COVID19.
It has been endorsed by the Student Assembly, the Graduate and
Professional Student Association, and the Faculty Senate. Do check
it out.
 April 5
 Classes start again tomorrow, at the regular time (10:10  11
AM) on zoom
 Office hour info (in particular, times and zoom links) can be
found here.
Things may still change slightly.
 Feb. 28
 I will post 34 questions (out of 7) from the
prelim *on gradescope* Wednesday morning at 9 AM. I will also post
a form that you have to sign at 8 AM. You need to sign it and
return it to me *by 10 AM on Wednesday*. (Otherwise, you will get
0 on the posted questions.)
 Three public service announcements:
 Women interested in research may want to sign up
for this
 All of you interested in research may want to be involved
in the spring symposium
 If you like integration, you may want to participate
in the integration bee
 Jan. 29 You can view solutions to homework
on CMS. You
can log in to CMS using your netid.
 Jan. 23 One more update to the policy:
 Since the two midterms will be 1.5 hours each and the final
is 2.5 hours, I've switched the percentage of the final grade
allotted to each: it will be 40% for the midterms (20% each) and
35% for the final.
 Jan. 22 Some updates to policies:
 Homework will always be handed out on Mondays and due the
following Monday at 10 AM.
 I will
allow homework to be handed in late, up to Tuesday at 5 PM, for
a 15% penalty. (These will be the deadlines set by Gradescope,
which should keep track of late homework.) While I certainly don't
encourage you to hand in homework late, I think it's good for
you to get feedback on homework, so it's certainly better to
hand it in late than not to hand it in at all.
 Please register for CS 2802 gradescope using the code
MNEJXP and also sign up on Piazza. I encourage you to post your
questions on Piazza!
 As Arthur pointed out in class, the final exam is set for
May 15 at 2 PM.