Announcements

• [Dec 15] By popular demand, here are the statistics of the grades: 11 As, 25Bs, 16Cs, 4Ds and 3Fs.
• [Dec 13] The grades have been determined. Email WvD your name and student number if you want to know your grade.
• [Dec 10] The December 7 corrections to the answers were incorrect. A third version of the answers has been posted.
• [Dec 7] Corrected, second version of the answers to the Final has been posted. (In the original answer to Question 1b the sets A and B were interchanged.)
• [Dec 6] The answers to the Final have been posted below.
• [Dec 2] SP will have extra office hours on Monday December 12, from 1pm to 3pm in Phelps 1413.
• [Dec 2] Slides of Week 10 posted.
• [Dec 2] Solutions to homework of Week 9 posted.
• [Nov 28] This week's Tuesday lecture (November 29) will be about some applications of the material that you learned in class this quarter. Thursday's class will be an overview session of the material for the Final.
• [Nov 28] This week, SP's office hours on Thursday are from 3 to 5pm.
• [Nov 21] Solutions to homework of Week 8 posted.
• [Nov 21] In case you are away from UCSB this week, you can email WvD your answers to the Homework of Week 9. However, you will have to email WvD before Saturday November 26 that you plan on doing so. Please describe in your email which file format you will use (plain ASCII text, LaTeX, dvi, ps, pdf, MSWord are all okay). The same deadline applies: Monday November 28, 13:30 Pacific Time.
• [Nov 21] Please note the class/discussion/office hours schedule of this Week 9.
• [Nov 19] Homework of Week 9 is posted (due Monday November 28, 13:30).
• [Nov 17] Slides of Tuesday and Thursday, Week 8 posted.
• [Nov 17] Solutions to homework of Week 7 posted.
• [Nov 13] Homework of Week 8 is posted (due Monday November 21, 13:30).
• [Nov 13] Slides of Thursday, Week 7 posted.
• [Nov 7] Second version of homework of Week 7 posted (Question 3 is removed from the earlier version).
• [Nov 7] Solutions to homework of Week 6 posted.
• [Nov 6] Homework of Week 7 is posted (due Monday November 14, 13:30).
• [Nov 3] Slides of Thursday, Week 6 posted.
• [Nov 3] The Midterm will be returned next Tuesday and Wednesday (Nov 8 and 9) during the Discussion sessions.
• [Nov 3] Next Tuesday (Nov 8) there will be no regular class; instead SP will have her discussion session in 387 101 at 12:30-13:45.
• [Nov 3] Slides of Tuesday, Week 6 posted.
• [Oct 31] Homework of Week 6 is posted (due Monday November 7, 13:30).
• [Oct 30] Slides of Thursday, Week 5 posted.
• [Oct 26] Second, corrected version posted of the solutions to the Midterm (the corrections concern the answer to Question 2).
• [Oct 26] Solutions to the Midterm posted.
• [Oct 24] Solutions to homework of Week 4 posted.
• [Oct 20] Slides of Thursday, Week 4 posted.
• [Oct 19] SP will have the homework of Week 3 graded on Monday the 24th. You can pick it up at her extra office hours that day between 13:00 and 15:00.
• [Oct 18] Slides of Tuesday, Week 4 posted.
• [Oct 18] SP will not have office hours on Thursday October 27; instead she will have extra office hours on Monday October 24, 14:00-16:00 13:00-15:00.
• [Oct 17] Solutions to homework of Week 3 posted.
• [Oct 16] Homework of Week 4 is posted (due Monday October 24, 13:30).
• [Oct 16] The homework deadline is extended by half an hour to 1:30pm.
• [Oct 14] Slides of Thursday, Week 3 posted.
• [Oct 11] Slides of Tuesday, Week 3 posted.
• [Oct 11] Solutions to homework of Week 2 posted.
• [Oct 9] Homework of Week 3 posted (due Monday October 17, 13:00 13:30).
• [Oct 6] Slides of Thursday, Week 2 posted.
• [Oct 4] Corrected version of the solutions to the homework of Week 1 posted.
• [Oct 4] Slides of Tuesday, Week 2 posted.
• [Oct 4] Note: deposit the homework in the homework box, not in WvD's mail box. If it is not in the proper box, your homework will be considered 'late'.
• [Oct 3] New homework posted (due Monday October 10, 13:00).
• [Oct 3] Solutions to homework of Week 1 posted.
• [Oct 3] Slides of Thursday, Week 1 posted.
• [Oct 1] Note: the homework box is in room 2108, Engr. I.
• [Sep 27] Homework of Week 1 posted.
• [Sep 27] Slides of Tuesday, Week 1 posted.
• [Sep 26] Slides of Week 0 posted.
• [Sep 23] Judging by the tables of Contents of editions 3, 4 and 5 of Grimaldi's Discrete and Combinatorial Mathematics, there does not appear to be any crucial difference between the different versions. If you are willing to tolerate some small differences between your text book and the official, 5th edition of the course, then you should be fine using some of the older editions. Doing so could save you a bundle of money.
• [Sep 21] At the moment CS40 "Foundations of Computer Science" is heavily over-enrolled (there is a waiting list of at least 10). Given that this course will be taught in both Winter and Spring as well, I would like to encourage you to consider taking this course another quarter, when the class size will be smaller.
• [Sep 21] For those on the waiting list: it is okay to crash tomorrow.
• [September 19, 2005] Welcome to the CS40 web site of Fall 2005.

Course Info

Description:

• Counting, propositional predicate logic, set theory, functions and relations, mathematical induction and recursion.

Required Textbook:

• Discrete and Combinatorial Mathematics, 5th edition, Ralph P. Grimaldi, Addison Wesley, 2003.
• Note: you can buy this book significantly cheaper if you use one of the many used books web sites that are out there. See also the Announcement of September 23.

Prerequisites:

• Computer Science 10 or 12; and Mathematics 3C.

Grading/Exams:

• 40% Homework + 20% Midterm + 40% Final Examination

Weekly Schedule:

• Monday 13:30 Homework due (typically); homework boxes are in Engr. I, 2108
• Tuesday 12:30-13:45 Class (387 101)
• Tuesday 14:00-16:00 Office hours WvD (Engr. I, 5109)
• Wednesday 12:00-12:50 Discussion (KJ) PHELPS 1425
• Wednesday 13:30-15:30 Office hours (KJ) PHELPS 1413
• Thursday 12:30-13:45 Class (387 101)
• Thursday 14:00-16:00 Office hours (SP) PHELPS 1413
• Friday 14:00-14:50 Discussion (SP) PHELPS 1508
• Weekend: Howework announced (typically)

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.

Schedule and Slides

• Week 0 [September 19 - September 25]
  Thursday Sep 22: Class starts
  Thursday slides (ppt|pdf): Introduction, formalities.
  
  
• Week 1 [September 26 - October 2]
  Homework (due Monday October 3, 13:00) / Solutions
  Tuesday slides (ppt|pdf): Counting, Chapter 1
  Thursday slides (ppt|pdf): Counting, Chapter 1
  
  
• Week 2 [October 3 - October 9]
  Homework (due Monday October 10, 13:00) / Solutions
  Tuesday slides (ppt|pdf): Counting, Logic, Chapters 1 and 2
  Thursday slides (ppt|pdf): Logic, Chapter 2
  
  
• Week 3 [October 10 - October 16]
  Homework (due Monday October 17, 13:00 13:30) / Solutions
  Tuesday slides (ppt|pdf): Rules of inference, predicates, Chapter 2
  Thursday slides (ppt|pdf): Set theory, Chapter 3
  
  
• Week 4 [October 17 - October 23]
  Homework (due Monday October 24, 13:30) / Solutions
  Tuesday slides (ppt|pdf): Set theory, inclusion/exclusion principle, relations, functions, Chapters 3 and 5
  Thursday slides (ppt|pdf): Set theory, cardinality, countable versus uncountable sets, Chapter 5, Appendix 3
  
  
• Week 5 [October 24 - October 30]
  Tuesday October 25: Midterm examination on counting, logic, and set theory / Solutions
  Material: Chapters 1-1.4, 2-2.6, 3-3.2. See Slide 4 of Tuesday Week 4 for more details.
  WvD will be away October 23-26
  SP will be away October 25-28
  Thursday slides (ppt|pdf): More on relations and functions, Chapters 5 and 7
  
  
• Week 6 [October 31 - November 6]
  Homework (due Monday November 7, 13:30) / Solutions
  Tuesday slides (ppt|pdf): Mathematical induction
  Thursday slides (ppt|pdf): Mathematical induction, divisability, primes
  
  
• Week 7 [November 7 - November 13]
  Homework (due Monday November 14, 13:30) / Solutions
  Thursday slides (ppt|pdf): division, greatest common divisor, least common multiplier, Euclid's gcd algorithm
  Tuesday Nov 8: Discussion session of SP instead of class.
  Friday Nov 11: No Discussion (Veterans' day)
  
  
• Week 8 [November 14 - November 20]
  Homework (due Monday November 21, 13:30) / Solutions
  Tuesday slides (ppt|pdf): big O, computational complexity, factoring
  Thursday slides (ppt|pdf): computational complexity, modular arithmetic
  
  
• Week 9 [November 21 - November 27]
  Homework (due Monday November 28, 13:30) / Solutions
  Office hours SP: Monday 13:30-14:30 (Engr. I, 3158) and Wednesday 11:00-12:00 (Phelps 1413)
  Office hours KJ: Tuesday 14:00-16:00 (Phelps 1413b)
  Tuesday's class: joint homework discussions for both Wednesday and Friday groups
  Wednesday Nov 23: No Discussion
  Thursday Nov 24: No class (Thanksgiving)
  Friday Nov 25: No Discussion (Thanksgiving)
  
  
• Week 10 [November 28 - December 4]
  Office hours of SP will be Thursday 15:00-17:00 (instead of the usual 2-4pm)
  Tuesday slides (ppt|pdf): Overview of theoretical computer science
  Thursday slides (ppt|pdf): Q and A, review session
  
  
• Finals Week [December 5 - December 10]
  SP has extra office hours on Monday 13:00-15:00 (Phelps 1413)
  Final examination: Tuesday, December 6, 12:00-15:00 (answers)

	This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 2.5 License.
Created September 18, 2005 / last updated December 15, 2005 by vandam@cs