Computer Science Dartmouth College |
Computer Science 21 / Math 19 / Engg 66 |
Winter 2004 |
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, basic number theory, logic and proofs (including mathematical induction), and basic probability theory. Most of the topics will be motivated by applications from computer science; specifically, we shall learn about the RSA cryptosystem, the analysis of recursive algorithms, and hashing.
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 115 | 10 hour | MWF 10:00-11:05, X-hr Th 12:00-12:50 | |||||||||||||||
Instructor |
Amit Chakrabarti | Sudikoff 218 | 6-1710 | Office hours: MTh 14:00-16:00 or by appointment | |||||||||||||||
Tutorials |
Sudikoff 212 | TThSu 19:00-21:00 | |||||||||||||||
Teaching Assistant |
Gabriel Florin Constantin | Sudikoff 212 | 6-0949 | Office hours: Immediately after tutorials | |||||||||||||||
Textbook |
Required: "Discrete Math for Computer
Science Students." Bogart, Drysdale, and Stein. Click the title of the book to view it as a PDF file. For easy printing, here are the individual chapters: [ Contents and Chapter 1 | Chapter 2 | Chapter 3 | Chapter 4 | Chapter 5 | Chapter 6 and Index ] |
|||||||||||||||
Prerequisites |
CS 5 or equivalent CS 15 or 18 (corequisite) |
|||||||||||||||
Work |
One homework per class, due at the start of next class.
[25 points] Two evening midterms. [25 + 25 points] One final exam on Fri Mar 12, 08:00. [50 points] Please take note of the late homework policy. | |||||||||||||||
Grading Recipe |
Your grade will be based on your adjusted cumulative score
(ACS), calculated as follows:
Then, your ACS = h + m_{1} + m_{2} + f - min{ m_{1}, m_{2}, f / 2 }. Loosely speaking, your "worst exam" is dropped, with the finals counting as two exams. The idea behind this recipe is that students who get better as the course progresses can take advantage of the finals, while at the same time students don't get severely penalized for one bad exam. |
This schedule will be updated frequently. Please check back often, and please remember to hit the RELOAD button to get the latest schedule.
The homework problems are, for the most part, assigned from the textbook. In the table below, such problems are simply referred to using the section number and problem number from the textbook. When additional (outside the textbook) problems are assigned, they are numbered AP1, AP2, etc. To read the statements of these problems, see the additional problems page, or just click on the problem number in the table below.
Date |
Reading Due |
Homework Due |
Class Topic |
Jan 5 | — | — | Organization. Introduction to counting. |
Jan 7 | 1.1 | — | Permutations and subsets. |
Jan 8 (x-hr) | — | 1.1: # 1, 2, 7, 8, 10, 12, 13, 15 | Catch-up class to deal with aftereffects of fire alarm. |
Jan 9 | 1.2 | 1.2: # 2, 6, 7, 8, 12, 13, 15, 17, 19 | Binomial coefficients. |
Jan 12 | 1.3 | 1.3: # 2, 3a, 3d, 6, 8, 11, 15, 18; AP1 | Equivalence classes, quotients, multisets. |
Jan 14 | 1.4 | 1.4: # 1, 2, 6, 10, 14 (ignore 14c), 16 | Mathematical induction. |
Jan 16 | 4.1 | 4.1: # 3, 4, 6, 9, 12, 13; AP2 | Introduction to probability. Principle of inclusion and exclusion. |
Jan 19 | — | — | No class; MLK Jr. Day. |
Jan 21 | 5.1, 5.2 | 5.1: # 2, 3, 6, 11; AP3
[See Jan 15 5.2: # 1, 5, 10, 14; AP4 [announcement |
Conditional probability and independence. |
Jan 22 (x-hr) | 5.3 | — | Random variables. |
Jan 23 | 5.4 | 5.3: # 2, 3, 6, 8, 10, 11; AP5 | Probability calculations in hashing. |
Jan 26 | 5.5 | 5.4: # 5, 7, 15, 17 and 5.5: # 1, 4, 11 | Recursion, recurrences, growth rates |
Jan 26 | First midterm exam, Sudikoff 115, 19:00-21:00 | ||
Jan 28 | 4.2 | — | Growth rates continued |
Jan 29 (x-hr) | 4.3 | 4.2: # 7, 8, 11, 14 and 4.3: # 1b, 1d, 5, 8, 9 | The master theorem |
Jan 30 | 4.4 | 4.4: # 1, 7, 8, 9 | More general recurrences, median finding [See these notes] |
Feb 2 | 4.5, 4.6 | 4.6: # 1, 2; AP6, AP7 | Conditional expectation, recurrences and algorithms |
Feb 4 | 5.6 | 5.6: # 3, 4, 7, 11, 13 | Probability distributions and variance |
Feb 6 | 5.7, The Gold-Bug | 5.7: # 1, 2, 3, 4, 14, 16, 18 | Cryptography and modular arithmetic |
Feb 9 | 2.1 | 2.1: # 1, 4, 5, 9, 11, 12, 15 | Inverses and GCDs |
Feb 11 | 2.2 | 2.2: # 1, 2, 4, 7, 9, 12, 14; AP8 | The RSA cryptosystem |
Feb 12 (x-hr) | 2.3 | 2.3: # 6, 7, 8, 15, AP9 | Details of the RSA cryptosystem |
Feb 13 | — | — | No class; carnival holiday. |
Feb 16 | 2.4 | 2.4: # 12, 14, 15 | Logic: equivalence, implication, variables, quantifiers |
Feb 16 | Second midterm exam, Sudikoff 115, 19:00-21:00 | ||
Feb 18 | 3.1, 3.2 | 3.1: # 1, 4, 6, 12, 15; 3.2: # 2, 5, 7 | Quantifiers, inference, proofs |
Feb 20 | 3.2, 3.3 | 3.2: # 11, 12, 14 [Typo!]; 3.3: # 1, 6, 8, 11, 14 | Graphs, subgraphs, connectivity, trees |
Feb 23 | 6.1 | 6.1: # 3, 7, 9, 12, 13, 14, 15 | Rooted trees, Eulerian trails and tours |
Feb 25 | 6.2, 6.3 | 6.2: # 9, 10, 12; 6.3: # 5, 6; AP10 | Matchings: Hall's marriage theorem |
Jan 8 (x-hr) | — | — | Matchings: König-Egerváry theorem, Berge's theorem |
Feb 27 | 6.4 | 6.4: # 9, 10, 12, 15; AP11 | Planarity |
Mar 1 | 6.5 | 6.5: # 14, 15, 16 [Typo!], 17 | Graph coloring and the five-color theorem |
Mar 3 | 6.5 | 6.5: # 4, 5, 6, 7, 9 | Review session 1 |
Mar 5 | — | — | Review session 2: Counting, Recurrences |
Mar 8 | Entire book | — | Review session 3: Probability, Graphs |
Mar 12 | Final exam, 08:00-12:00 |
Here is a collection of links to PDF files containing solutions to problems from the textbook. Some of the solutions are detailed and explain all of the reasoning involved. But many of them are outlines only and in a homework or an exam you should provide a little more detailed reasoning. These solutions were prepared by Professors Ken Bogart, Scot Drysdale and Cliff Stein. Please do not distribute them.
There may be typos in the solutions. If you find any, please notify me so I can notify the authors.
Here are solutions to the additional problems for homework and to the exams. These problems and solutions are written by me. If you find typos (or worse, mistakes) please let me know right away. Again, please do not distribute these.
If you are a registered student, you may verify your grades as entered in our database using the form below.