Discrete Mathematics in Computer Science

Computer Science 280 (Fall 2005)

Basic Info:

• Monday, Wednesday, Friday 1:25-2:15 pm. Olin 155.

Staff

• Instructor:
  • Jon Kleinberg, 5134 Upson Hall, 255-3600.
• Teaching Assistants:
  • Stephen Barrett, email: snb26
  • Kevin Canini, email: krc25
  • Andrew Costello, email: aoc6
  • Eric Frackleton, email: epf2
  • Hari Nathan, email: hsn4
  • Joel Ossher, email: jpo5
  • John Roberts, email: jwr23
  • Zachary Scherr, email: zls2
  • Ymir Vigfusson, email: ymir at cs dot cornell dot edu
• Support Staff: Bill Hogan, 4119 Upson, 254-8948, email: whh at cs dot cornell dot edu.

Getting in touch with us

Office hours for Wednesday (Dec. 14) before the final exam

• Wednesday 12:00-1:00, Andrew Costello
• Wednesday 2:15-3:00, Jon Kleinberg (5134 Upson)
• Wednesday 3:00-4:00, Stephen Barrett
• Wednesday 4:00-6:00 (2 hours) Eric Frackleton and Hari Nathan

Handouts

Handouts other than problem set solutions will be handed out in class and also available on the course home page. Problem set solutions will be available only as PDF files via CMS.

• Approximate syllabus.
• Student information sheet. (Please fill out and return.)

• Problem Set Cover Sheet. For each problem set, please print out a copy of this, fill it out, and staple it to the front of the assignment that you turn in. Notice that the grading table on the front has space for up to 10 problems; this doesn't mean that we expect each problem set to have 10 problems, but it gives us the flexibility to use as much of the grading table as we need for each assignment.

• Problem Set 1 (due 9/9).
• Problem Set 2 (due 9/16).
• Problem Set 3 (due 9/23).
• Information and Review Questions for Prelim 1 (9/30, in class).
• Problem Set 4 (due 10/14).
• Problem Set 5 (due 10/21).
• Problem Set 6 (due 10/28).
• Problem Set 7 (due 11/04).
• Information and Review Questions for Prelim 2 (11/09, in class).
• Problem Set 8 (due 11/18).
• Problem Set 9 (due 12/02).
• Information and Review Questions for Final Exam (12/15, 9:00-11:30 AM, Upson B-17).

Notes

Here are on-line notes for some of the early portions of the course that didn't correspond closely to specific sections in the book.

• A First Example: Reasoning about Voting Systems.
• Boolean Formulas and Game Trees.
• Quantifiers.
• Induction and Recursion.

Here are some on-line resources for other parts of the course.

• The problems that Paul Chew used in his lecture on the Pigeonhole Principle.
• R. Agrawal, R. Srikant. "Fast Algorithms for Mining Association Rules." Proc. 20th International Conf. Very Large Data Bases, 1994.
• D. Lewis. Naive (Bayes) at Forty: The Independence Assumption in Information Retrieval. Proceedings of ECML-98, 10th European Conference on Machine Learning, 1998.
• Ramin Zabih's notes from his lecture on statistical reasoning.
• A. Broder et al. Graph structure in the web. 9th International World Wide Web Conference, May 2000.
• R. Kumar, P. Raghavan, S. Rajagopalan, A. Tomkins. Trawling the web for emerging cyber-communities. 8th International World Wide Web Conference, May 1999.

Lectures

Here is a summary of the lecture topics, with pointers to sections in the book and to the on-line notes.

• Lecture 01 (08/26): A First Example: Reasoning about Voting Systems. See notes on voting systems.
• Lecture 02 (08/29): Boolean Formulas. See notes on Boolean formulas and Sec. 1.1, 1.5, 3.1
• Lecture 03 (08/31): Game Trees. See notes on Boolean formulas and game trees.
• Lecture 04 (09/02): Quantifiers. See notes on quantifiers and Sec. 1.2, 1.3, 1.4
• Lecture 05 (09/05): Induction, Recursive Definitions, and the Fibonacci Numbers. See notes on induction and recursion, and Sec. 3.3, 3.4
• Lecture 06 (09/07): Induction: Recursive Algorithms, Paradoxical Outcomes, and Strategic Reasoning. See notes on induction and recursion, and Sec 3.5
• Lecture 07 (09/09): Cryptography and Number Theory Background. Sec 2.4.
• Lecture 08 (09/12): Prime Numbers and the Complexity of Arithmetic. Sec 2.4, 2.5.
• Lecture 09 (09/14): Euclid's Algorithm and the greatest common divisor. Sec 2.4, 2.5.
• Lecture 10 (09/16): The extended Euclidean Algorithm, primality testing, and the definition of RSA. Sec 2.6.
• Lecture 11 (09/19): Anaylzing RSA; using RSA for anonymous e-mail. Sec 2.6.
• Lecture 12 (09/21): Sets: terminology and basic operations. Sec 1.6, 1.7.
• Lecture 13 (09/23): Counting arguments: multiplying options and controlling for overcounting. Sec 4.1, 4.3.
• Lecture 14 (09/26): Pigeonhole Principle. See Paul Chew's notes and Sec 4.2.
• Lecture 15 (09/28): Further Applications of the Pigeonhole Principle: Infinite Loops and Family Trees. Sec 4.2.
• Lecture 16 (09/30): Prelim 1.
• Lecture 17 (10/03): Binomial Coefficients. Sec 4.4.
• Lecture 18 (10/05): Association rules for data mining. See paper by Agrawal and Srikant.
• Lecture 19 (10/07): Basic properties of error-correcting codes.
• Lecture 20 (10/12): Probability background: Sample spaces, events, conditional probability. Sec 5.1 and 5.2.
• Lecture 21 (10/14): Conditional probability, independence, and the Naive Bayes method for text classification. Sec 5.1 and 5.2, and paper by David Lewis.
• Lecture 22 (10/17): Union Bound, Indentifier Selection, Birthday Paradox, Contention Resolution. Sec 5.1 and 5.2, and Sec 13.1 in Randomized Algorithms handout.
• Lecture 23 (10/19): Random Variables and their expectations: linearity of expectation. Sec 5.3, and Sec 13.3 in Randomized Algorithms handout.
• Lecture 24 (10/21): The coupon collector problem; epidemic processes. Sec 5.3, and Sec 13.3 in Randomized Algorithms handout.
• Lecture 25 (10/24): Statistical consequences and maximum likelihood estimates. See Ramin Zabih's notes from his guest lecture.
• Lecture 26 (10/26): Variance, Markov's inequality, Chebyschev's inequality. Sec 5.3.
• Lecture 27 (10/28): Chebyschev's inequality, distributions of runs and streaks. Sec 5.3 and Ramin Zabih's notes.
• Lecture 28 (10/31): Hashing as an application of randomization. Sec. 13.6 in the Randomized Algorithms handout.
• Lecture 29 (11/02): Introduction to graphs. Examples of graphs: communication networks, social networks, information networks, transportation networks, and others. Basic graph terminology. Sec 8.1-8.2.
• Lecture 30 (11/04): Basic properties of trees. Sec 9.1.
• Lecture 31 (11/07): Induction arguments on graphs and trees; random processes that generate trees.
• Lecture 32 (11/09): Prelim 2.
• Lecture 33 (11/11): Breadth-first search and depth-first search. Sec 9.4, and Sec 3.2 in handout on graphs.
• Lecture 34 (11/14): Graph coloring and testing whether a graph is bipartite. Sec 8.8, and Sec 3.4 in handout on graphs.
• Lecture 35 (11/16): Basics of directed graphs: strong connectivity and applications to analyzing the Web graph. Sec 8.4 and paper by Broder et al.
• Lecture 36 (11/18): Directed acyclic graphs and topological ordering. Sec 3.6 in handout on graphs.
• Lecture 37 (11/21): Enumerating dense bipartite communities in the Web graph. See the paper by Kumar et al.
• Lecture 38 (11/28): Properties of relations; equivalence relations and partial orders. Sec 7.5-7.6.
• Lecture 39 (11/30): Partial orders and parallel computing. Sec 7.6.
• Lecture 40 (12/02): Infinite sets: countability and uncountability; why the set of possible computer programs is smaller than the set of possible computational problems. Sec 3.2. Sec 7.6.

Books

The course textbook is

• K. Rosen. Discrete Mathematics and Its Applications (5th edition). McGraw-Hill. 2003

Prerequisites

Prelims and Final

• Prelim 1: Friday, September 30, in class.
• Prelim 2: Wednesday, November 9, in class.
• Final: Thursday, December 15, 9-11:30 am.

Homework

There will be weekly homework sets, generally due on Fridays. Homework should be handed in in lecture, at the end of class, on the day it is due.

• Late homeworks will not receive credit. (If a genuine emergency situation prevents you from handing in an assignment on time, come talk to one of us and we can work something out.)

Grade Breakdown

Academic Integrity

You are expected to maintain the utmost level of academic integrity in the course. Any violation of the code of academic integrity will be penalized severely.

You are allowed to collaborate on the homework to the extent of formulating ideas as a group. However, you must write up the solutions to each problem set completely on your own. You must also list the names of everyone that you discussed the problem set with.