Computer Science
Dartmouth College
|
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.
| 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 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.
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. |
|||
If you are a registered student, you may verify your grades as entered in our database using the form below.