Final Info

• Place and Time: The exam is on Wednesday 8 December 2004, from 8am to 11am in PHELP 3515 and 3523. Please be early so that you can start on time.
• Material: The exam will cover all the material that we discussed during the quarter. Hence it will consist of the material of the midterm plus Section 5.3 ("Complexity of Algorithms" and big-O notation) and Chapter 8 ("Counting and Probability"). Because we did not cover Markov chains, you do not have to study Section 8.11. You also do not have to study Sections 1.7 ("Circuit Diagrams") and 2.4 ("Boolean Algebras").
• Approximately 25% of the exam will focus on the material in Chapters 1,2 and Sections 3.1-3.2. The main part of the exam (75%) will be about Sections 3.3-3.6, 5.3 and Chapter 8.
• Students using the first edition of DMwC should not forget to study Section 4.1 ("Functions") as well (this is Section 2.8 in the second edition).
• The examination is open book: you can bring your books, notes, printouts et cetera with you. Don't forget to bring scrap paper.
• You are not allowed to use electronic gadgets. (This includes calculators.)
• The exam will be proctored by the two TAs.
• See the slides of the last week for some additional information on the final exam.

Announcements

• [Dec 16] The grades for CS40 have been determined. There are 12 As (of which one A+), 20 Bs, 21 Cs, 8 Ds and 2 Fs. You can email me with your name and student no. if you want to know your grade.
• [Dec 16] The answers to the Final have been posted below.
• [Dec 10] "Don't email us, we will email you..." The final has not been graded yet. WvD will let you know when it has.
• [Dec 6] Two changes have been made to the answer sheets. The answer to Question 1b in week 8 was incorrect: the probability is 5/72 not 7/72 (thanks go to the TAs for pointing this one out). Second, there is some confusion about Question 2 in week 6. See the new answer sheet for an explanation.
• [Dec 6] Note that WvD will be away from his office in the period Dec 6-9.
• [Dec 3] You can pick up the homework of the last three weeks on Monday morning at the office of CG (Theory Lab, 2nd floor of Engr. I). He will be there Monday 9:30-12:00, 13:00-16:00 and Tuesday 9:30-12:00.
• [Dec 2] You can email vandam@cs to get an estimate for your grade based on your midterm and the first four weeks of homework. See here for an explanation how this estimation is calculated.
• [Dec 1] Thursday 2 December will be the last class of CS40. It will be a Q&A session where the material for the final exam will be reviewed. Please bring questions.
• [Dec 1] The course evaluation forms will be handed out on Thursday, 2 December.
• [Dec 1] The answers to the homework questions of week 8 are posted below.
• [Nov 29] The answers to the homework questions of weeks 6 and 7 are posted below.
• [Nov 20] Latest and last homework posted (due Monday November 29, 5pm; no late submissions are allowed).
• [Nov 18] Today, Nov 18, WvD's office hours will be from 2 to 3pm.
• [Nov 15] This week (Nov 15-19) CG will not have office hours; the discussion sections will hosted by WvD.
• [Nov 15] Note the adjusted 'Late Homework Policy'
• [Nov 12] More homework announced that will be due Nov 19, 5pm.
• [Nov 9] New due date of homework: Friday November 19, 5pm.
• [Nov 9] WvD will not have office hours on Nov 10 and Nov 11.
• [Nov 5] New homework posted.
• [Oct 28] Midterm and Answers to Midterm have been posted.
• [Oct 28] There will be no new homework this weekend.
• [Oct 28] Today's discussion will go through as usual.
• [Oct 27] There has been a small glitch in the grading of the homework of week 2, question 2c ("How many different equivalence relations are there..."). If and only if your answer to this question was "5" and you got points subtracted, go to the TA and see if you should have received more points.
• [Oct 27] Solutions of homework of week 3 posted.
• [Oct 27] Slides of overview session posted.
• [Oct 24] Detailed description of Midterm material posted.
• [Oct 24] Solutions of previous homework posted.
• [Oct 24] Slides of week 4 posted.
• [Oct 17] Homework of week 3 posted; it is due Monday October 25, 5pm.
• [Oct 15] Slides of Thursday, week 3 posted.
• [Oct 12] 'Late submission of homework policy' posted (see below)
• [Oct 12] Slides of Tuesday, week 3 posted.
• [Oct 12] The UCSB bookstore will return the Fall 2004 textbooks on October 25. This means that if you want to buy the book from them, you should do that before the 25th. Also if you want to return your textbook, you should do that before the same date.
• [Oct 10] Some extra time to finish the homework: The homework that is due Monday the 11th, is due before 5pm.
• [Oct 10] Homework and slides of week 2 posted. The homework is due on Monday the 18th, before 5pm.
• [Oct 1] Homework and slides posted. By popular demand, the homework submission deadline is moved to Monday morning.
• [Sep 28] Homework is posted (see below in the Schedule/Slides section). It is due this Friday October 1 before 5pm. Put it in the proper CS40 box (on the 2nd floor of Engr. I). After 5pm this box is closed.
• [Sep 23] There will be no Discussion, Office hours or Homework this week.
• [September 21, 2004] Welcome to the CS40 web-site.

Course Info

Textbook:

• [Required] James A. Anderson, Discrete Mathematics with Combinatorics, Prentice Hall (2001, 2004)
• I'm using the second edition of DMwC (2004), but things should be fine when you use the first edition (2001).
• This is an expensive book and I encourage you to shop around. It's pretty straightforward to get the book for far less from (on-line) sources that specialize in (second hand) college textbooks.

Grading/Exams:

• 40% - Homework (worst one will be dropped)
• 20% - Midterm (week 5, in class)
• 40% - Final (Dec 6-11)

Typical Weekly Schedule (adjusted, Nov 15):

• Monday 10:00-11:00am: Office hour of CG
• Tuesday 9:30-10:45am: Class, return of homework (PHELP 3515)
• Wednesday 12:00-12:50pm: Discussion (PHELP 1425)
• Wednesday 1:00-2:00pm: Office hour of WvD
• Thursday 9:30-10:45am: Class (PHELP 3515)
• Thursday 1:00-2:00pm: Office hour of WvD
• Thursday 5:00-5:50pm: Discussion (PHELP 3523)
• Friday 10:00-11:00am: Office hour of CG
• Friday 5pm: Homework due
• Friday 5pm: Homework announced

Late Homework Policy (adjusted, Nov 15):

• The homework is due Friday 5pm.
• You have to tell/email me at least 24hrs before the deadline if you want to submit your homework late. Specify the reason.
• If you did not tell me beforehand, or if the given reason is not approved by me, I will subtract points from your score:
  • Minus 20 points if you submit between the Friday 5pm and Monday 5pm,
  • After Monday 5pm you will not get any points for your homework.

Contacting/Questions:

• I prefer that you use my office hours for your questions, rather than doing a lengthy Q&A exchange via email. Ideally, you could email me about the issue in advance so that I can look into it before my office hour session. Thanks. (WvD)

Schedule and Slides

• Week 0
  • [Sep 23] Introduction and formalities; Logical Propositions (ppt / pdf)
• Week 1
  • [Sep 28] Propositional Logic I: truth tables, equivalence (ppt / pdf)
  • [HW due Friday Oct 1] Homework, Solutions
  • [Sep 30] Propositional Logic II: proofs and more; Sets and operations on sets (ppt / pdf)
  • [HW due Monday Oct 11] Homework, Solutions
• Week 2
  • [Oct 5] Set Theory: Venn diagrams, relations and functions between sets (ppt / pdf)
  • [Oct 7] Predicate logic, quantifiers, Integers, proof by induction (ppt / pdf)
  • [HW due Monday Oct 18] Homework, Solutions
• Week 3
  • [Oct 12] More proofs by induction, number theory (ppt / pdf)
  • [Oct 14] Number theory: divisibility, primes (ppt / pdf)
  • [HW due Monday Oct 25] Homework, Solutions
• Week 4
  • [Oct 19] Modulo n calculations, RSA (ppt / pdf)
  • [Oct 21] Complexity of computation, big-O notation (ppt / pdf)
  • [HW] prepare for coming Midterm
• Week 5
  • [Oct 26] Q&A, review of midterm material (ppt / pdf)
  • [Oct 28] Midterm exam on material of previous weeks (Midterm, Answers to Midterm)
• Week 6
  • [Nov 2] Big-O notation, complexity theory, P versus NP (ppt / pdf)
  • [Nov 4] Counting and Probability I: adding and multiplying events, inclusion/exclusion principle (ppt / pdf)
  • [HW due Friday Nov 19] Homework, Solutions
• Week 7
  • [Nov 9] Counting II: permutations and combinations (ppt / pdf)
  • [Nov 11] no class
  • [HW due Friday Nov 19] Homework, Solutions
• Week 8
  • [Nov 16] Counting III: more combinatorics and probability theory (ppt / pdf)
  • [Nov 18] Counting IV: probability theory and expected values (ppt / pdf)
  • [HW due Monday 29] Homework, Solutions
• Week 9
  • [Nov 23] Discussion-like lecture about the topics of the previous week
  • [Nov 25] no class
• Week 10
  • [Nov 30] Retroactive advertisement: "Discrete mathematics and Computer Science"
  • [Dec 2] Q&A, review session
• Week 11
  • [Wednesday Dec 8, 8-11am] Final Examination (Final, Answers)

September 21, 2004 / last updated: December 16, 2004 by Wim van Dam (vandam@cs)