CS 21 (Winter 2004): Amit Chakrabarti

Teaching Home

Computer Science 21 / Math 19 / Engg 66
Discrete Mathematics in Computer Science

Amit Chakrabarti

Winter 2004

[ 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, 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.

Announcements

[Mar 10] On Page 201 (Chapter 5) of the textbook, the equation after (5.12) is very wrong. Here is the corrected equation; please make the change in your textbook.
[Mar 7] A practice final exam has been posted to the course mailing list. Try it, and time yourself.
[Feb 29] There is another typo in Sec 6.5 Problem 16. At the end of the sentence "degree 4" should read "degree at most 4".
[Feb 16] There is a typo in the statement of Sec 3.2 Problem 14. In the first sentence (the one beginning "Find a reason...") the final OR sign should be an AND sign.
[Feb 10] For some very interesting, entertaining and informative reading about RSA and cryptography, see the Crypto FAQ, over at RSA Security. In fact, the entire RSA Labs website is recommended reading: use the navigation bar on the left to get to the various sections. You can learn a lot about RSA and cryptography beyond the little that we cover in this course. There's a section called Challenges which even gives you an opportunity to win some serious money! [Note, added Oct 29, 2010: The Crytpo FAQ link is broken, and here is a more comprehensive reference, sent to me by Julie Elan.]
[Jan 22] A new section containing solutions to homework and exam problems has been added to this webpage.
[Jan 15] Since there is no class on Jan 19, there are two homeworks (5.1 and 5.2) due on Jan 21. As compensation, the homeworks are shorter than usual.
[Jan 14] The midterms will be open book and open notes, which means that studentis may consult their textbook, any notes handed out in class, their own notes, and their own homework solutions during the exams. Students may not consult anything else and must work on the exam problems by themselves.
[Jan 14] The two evening midterms will be held on Jan 26 and Feb 16 in Sudikoff 115. They are tentatively scheduled for 19:00-21:00 on these days. Watch this space for further announcements.

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.

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:

Unit Max possible score Your score
Homework 25 h
Midterm 1 25 m₁
Midterm 2 25 m₂
Final 50 f

Then, your ACS = h + m₁ + m₂ + f - min{ m₁, m₂, 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.

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

Solutions to Homework and Exam Problems

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.

: 1.1 1.2 1.3 1.4

: 2.1 2.2 2.3 2.4

: 3.1 3.2 3.3

: 4.1 4.2 4.3 4.4 4.5 4.6

: 5.1 5.2 5.3 5.4 5.5 5.6 5.7

: 6.1 6.2 6.3 6.4 6.5

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.

: Additional Problems
First Midterm Exam
Second Midterm Exam
Final Exam

Grades Database

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