Computer Science 2802: Discrete Structures - Honors
Spring, 2020

Prof. Joe Halpern

• Course policies and general information
• Staff (including office hours)
• Lecture notes
• Homework assignments

• 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, 0-1 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 take-home 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 COVID-19. 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 3-4 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.