Computer Science Dartmouth College |
## Computer Science 19 / Math 19 / Engineering 66 |
## Winter 2006 |

In this course we shall get introduced to *Discrete
Mathematics*, a relatively modern branch of mathematics with close
ties to computer science. The major topics to be covered include
counting techniques, logic and proofs (including mathematical
induction), and some basics of probability theory and graph theory.
These topics are all motivated by applications from computer science and
where appropriate we shall study some of these applications.

One very important skill that students will be *required* to
pick up during this course is that of writing clear, convincing,
mathematical proofs. This is because the mathematics in this course is
not just about calculation; it is more about making (and clearly
presenting) mathematically rigorous arguments and about learning to
recognize faulty reasoning.

The above skill is quite a rarity, and is known to be hard to acquire. Students are therefore advised to ask themselves from time to time whether they are making good progress towards acquiring this skill.

- [Mar 9] Solutions to HW7 and HW8 have been posted. This completes the posting of all official solutions. You may (and should) refer to these as you work on the final exam.
- [Mar 8] The final exam is ready for download. Clicking the link will take you to a webpage with details about the exam. Please click it now. Your clock won't start until you fill out your password on that page.
- [Mar 3] Solution to Quiz 2 have been posted. Please read these carefully. Remember, all posted solutions are required reading.
- [Feb 27] Solutions to HW6 have been posted. Solutions to HW4 and HW5 had been silently posted a while ago!
- [Feb 5] Solutions to Quiz 1 and to HW3 have been posted.
- [Feb 3] Homework 4 has been posted. Solutions to HW3 will be posted lated today.
- [Feb 1] A handout on big-O, big-Omega and big-Theta notation has been posted. See the Feb 1 entry in the schedule table. Thanks to Tom Cormen for this handout.
- [Feb 1] Solutions to HW2 have been posted.
- [Jan 27] Homework 3 has been posted to the website. Solutions to HW2 have not yet been posted because we are still waiting for a couple of late submissions.
- [Jan 20] Homework 2 and solutions to Homework 1 have been posted to the website. See below.
- [Jan 11] This course website has been significantly updated. Please go through it all very carefully. Pay special attention to the administrative details page, which has important information you need about work due.
- [Jan 3] Please send a blitz to the instructor with your name (only first and last name, no initials) and a password for accessing your grades in the grades database.

Lectures |
Sudikoff 214 (may change) | 10 hour | MWF 10:00-11:05, X-hr Th 12:00-12:50 | ||||||||||

Instructor |
Amit Chakrabarti | Sudikoff 107 | 6-1710 | Office hours: Mon & Fri 14:00-16:00 or by appointment | ||||||||||

Teaching Assistants |
Chien-Chung Huang | Sudikoff 221 | 6-8753 |
Office hours: Mon 19:00-20:00, Tue 16:00-18:00, Fri 16:00-17:00
David Blinn | Sudikoff 114 | 6-5716 | Office hours: Mon 16:00-17:00, Tue 16:00-18:00 On Mon and Tue, please visit the TA who will be grading the homework due on Wed of that week. |
||||||||||

Textbook |
Discrete Mathematics for Computer Science.
K. P. Bogart, C. Stein, R. L. Drysdale.
Key College Publishing.
ISBN 1930190867. |
||||||||||

Prerequisites |
CS 5 or equivalent CS 15 or 18 (corequisite) MATH 8 or equivalent is very strongly recommended |
||||||||||

Work |
Please take note of the late homework policy. |

This schedule will be updated frequently. Please check back often,
and please remember to hit the RELOAD button to get the latest schedule.
The "Reading Due" column indicates the section(s) of your textbook that
you should read, and submit email
comments for, before coming to class. You should also work out, with
your team, the exercises within that section; they will be the class exercises for that class.
Sometimes, one or two additional class exercises may be added using the
notation P*i.j-k* (in
red): this refers to Problem *k* from Section *i.j* of
your textbook.

Any part of the schedule that is greyed out is tentative and subject to change.

L# |
Date |
Reading Due |
Homework Due |
Class Topic |

1 | Jan 4 | — | — | Welcome, administrivia, overview; Quiz 0 |

2 | Jan 6 | — | — | A teaser: pancake numbers (thanks: Anupam Gupta) (slides) |

3 | Jan 9 | — | — | Sets and operations on sets (slides) |

4 | Jan 11 | L3 slides | — | Relations and functions (slides) |

5 | Jan 12 (X-hr) | L4 slides | — | Logic and logical notation (slides) |

6 | Jan 13 | 3.1, 3.2; L5 slides | — | More on logic: variables and quantifiers (slides) |

Jan 16 | — | — | No class; MLK day | |

7 | Jan 18 | 1.1; P1.1-9 | HW1 | Basic counting |

8 | Jan 19 (X-hr) | 1.2 | — | Counting lists and permutations |

9 | Jan 20 | 1.3 | — | Permutations and combinations (subsets) |

10 | Jan 23 | P1.3-5, P1.3-7 | — | Binomial coefficients and the binomial theorem |

11 | Jan 25 | 1.4 up to "Multisets" |
HW2 | Equivalence relations and the quotient principle Note: For the reading, you may stop right before the "Multisets" subsection |

12 | Jan 27 | — | — | Proofs by contradiction and by mathematical induction (slides) |

13 | Jan 30 | 4.1; L12 slides | — | More on mathematical induction |

14 | Feb 1 | 4.2 | HW3 | Recurrences and their connection to induction and
recursion Important: Please read and understand this
handout on O, Ω and
Θ notation |

Feb 2 (X-hr) | — | — | Quiz 1: closed-notes, in-class | |

15 | Feb 3 | 4.3; L14 handout | — | Recurrences and growth rates |

16 | Feb 6 | 4.4, 4.5 | — | The master theorem; recurrence inequalities |

17 | Feb 8 | Reread 4.5 | HW4 | Wrinkly induction proofs |

18 | Feb 9 (X-hr) | 5.1 | — | Probability |

Feb 10 | — | — | No class; carnival holiday | |

19 | Feb 13 | — | — | Sample spaces and probability measures (class exercises from Sec 5.1) |

20 | Feb 15 | 5.2 | HW5 | The principle of inclusion and exclusion |

21 | Feb 17 | 5.3 | — | Conditional probability and independence |

22 | Feb 20 | 5.4 | — | Random variables |

23 | Feb 22 | 5.5 | HW6 | Probability calculations in hashing |

25 | Feb 23 (X-hr) | — | — | Quiz 2: closed-notes, in-class |

26 | Feb 24 | 5.6 | — | Randomized recursive algorithms and their analysis |

27 | Feb 27 | 6.1 | — | Graphs |

28 | Mar 1 | 6.1, 6.2 | HW7 | Trees and spanning trees (reading: skip "breadth-first search" and "rooted trees" from 6.2) |

29 | Mar 3 | 6.3 | — | Eulerian graphs (reading: skip "Hamiltonian paths" and the rest of 6.3 from there on) |

31 | Mar 6 | 6.4 up to p362 | — | Matchings I: Berge's Theorem |

32 | Mar 8 | Rest of 6.4 | HW8 | Matchings II: König-Egerváry and Hall's Theorems |

Mar 14 |
Take-home 24-hour final exam, due at 5:00pm sharp Please the click the above link for info on the final exam. Your clock won't start until you fill out your password on that page. |

- Solutions to HW1
- Solutions to HW2
- Solutions to HW3
- Solutions to HW4
- Solutions to HW5
- Solutions to HW6
- Solutions to HW7
- Solutions to HW8
- Solutions to Quiz 1
- Solutions to Quiz 2

If you are a registered student, you may verify your grades as entered in our database using the form below.