Teaching     Home
Dartmouth Logo
Computer Science
Dartmouth College

Computer Science 19 / Math 19 / Engineering 66
Discrete Mathematics in Computer Science

Amit Chakrabarti

Winter 2006

[ Announcements | Administrative Basics | Schedule and Homeworks | Solutions | Grades Database ]

Course Description

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.


Administrative Basics

Important! Please also read and familiarize yourself with the administrative details not covered in the outline below. Pay special attention to the section that describes how the honor code applies to this course; violations of the honor code will be treated seriously.


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

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.


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

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


Reading and email comments before each class [10 points]
Group work on class exercises. [15 points]
One homework per week. [30 points]
Two in-class quizzes. [20 points]
One take-home final exam. [25 points]

Please take note of the late homework policy.

Schedule and Homeworks

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 Pi.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.



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
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 Homework and Exam Problems

Grades Database

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

Your name, without initials or suffixes:
Your CS 19 password:

Teaching     Home