CS 206 - Introduction to Discrete Structures II
Spring 2013
Course Overview
This course is an introduction to probability and combinatorics,
including their basic mathematical foundations as well as several non-trivial
applications of each. The first topic explores how to think about random
processes in a rigorous and sensical way, and second is about techniques
for counting the number of objects fitting a given description. As
we will see, the techniques involved in both topics are strongly related.
Roughly, we expect to cover the following list of topics. Lecture summaries
will be posted at the bottom of this page.
- Review of prerequisites, set theory, countability
- Random experiments, sample spaces, events, probability measures
- Conditional probability, Bayes' Theorem, Independence
- Combinatorics and Counting
- Recurrences, Generating Functions
- Random Variables
- Bernoulli Trials
- Expectation, Variance
- Markov Chains
- Applications of Probability and Combinatorics
General Information
- Instructor: David Cash (david.cash@cs.rutgers.edu, office Hill 411)
- Course website: http://www.cs.rutgers.edu/~dc789/206-spring-13
- Recommended textbooks:
- S. Ross, A First Course in Probability, 8th Edition
- H. Rosen, Discrete Mathematics and its Applications, 7th edition
- Lecture meetings: Monday and Wednesday 5:00pm -- 6:20pm in Hill 116
- Recitations:
- Section 1: Monday 6:55pm -- 7:50pm in SEC 220
- Section 2: Wednesday 6:55pm -- 7:50pm in ARC 110
- Section 3: Monday 8:25pm -- 9:20pm in Hill 250
- Instructor office hours: Tuesday 3:00pm-4:00pm in Hill 411 and by appointment
- Teaching assistants:
- Recitation TA: Chetan Tonde (cjtonde@cs.rutgers.edu)
- Section 1 Grader: Fatma Betul Durak (fbdurak@cs.rutgers.edu)
- Section 2 Grader: Yan Wang (wangyanadam1988@gmail.com)
- Section 3 Grader: Erick Chastain (erickc@cs.rutgers.edu)
- Teaching assistant office hours:
- Chetan Tonde: Monday 3:00pm -- 4:30pm in Hill 402
- Fatma Betul Durak: Thursday 3:00pm -- 4:30pm in Hill 412
- Yan Wang: Thursday 1:00pm -- 2:00pm in Hill 202
- Erick Chastain: Tuesday 3:00pm -- 4:00pm in Hill 414
Assignments and Grading
Homeworks will be assigned roughly every 1.5 weeks. There will be one
in-class midterm and one final exam.
Final grades will be an average of homework grades (30%), midterm grades (30%),
and final exam grades (40%).
Homeworks
Homework assignments will be posted here and on Sakai.
Lecture Schedule
A brief summary of each lecture and the associated reading will be posted here.
- Wed Jan 23 (Lecture 1): Introduction
- Topics: Review of sets and induction. Samples spaces and events.
- Reading: Ross 2.1-2.2.
- Mon Jan 28 (Lecture 2): Probability measures
- Topics: Operations on events. Abstract definition of probability
measure. Equivalent definition for countable sample spaces. Basic
consequences of the definition.
- Reading: Ross 2.3-2.4 through Definition 4.3.
- Wed Jan 30 (Lecture 3): Begin counting and its applications
- Topics: Finish proof about probability of a union. Counting:
The multiplication rule, permutations of n objects and k-out-of-n objects.
The birthday problem. Permutations when some objects are indistinguishable. Counting walks on grids.
- Reading: Ross 2.4, 1.2, 1.3.
- Mon Feb 4 (Lecture 4): Combinations
- Topics: Deriving the formula for combinations. Basic identities
and examples. The antenna problem (Ex. 4c of Ross). Counting
divisions where all sets non-empty and where sets are allowed to be
empty.
- Reading: Ross 1.4 through Ex 4c, 1.6.
- Wed Feb 6 (Lecture 5): Binomial and Multinomial Coefficients
- Topics: Pascal's relationship and Pascal's triangle. The
binomial theorem and proofs by combinatorial reasoning and
induction. Some consequences and examples. Multinomial coefficients
and their applications to dividing groups and counting
strings.
- Reading: Ross 1.4, 1.5.
- Mon Feb 11 (Lecture 6): Multinomial Theorem, Counting Problems, Inclusion-Exclusion
- Topics: The multinomial theorem and applications. The "tree method"
for various counting problems involving card hands and committees.
Inclusion-exclusion.
- Reading: Ross 1.5, 2.4 from page 31 on.
- Wed Feb 13 (Lecture 7): More on Inclusion Exclusion, Conditional Probability
- Topics: de Montmort's problem. Conditional probability definition
and several examples. Example of conditioning with medical tests
for rare diseases.
- Reading: Ross 2.5 (especially example 5m), 3.1-3.2, (especially
example 3d).
- Mon Feb 18 (Lecture 8): Bayes's Theorem
- Topics: Bayes's theorem: Statement, examples, applications to
spam filtering and other fields. General version of Bayes's theorem
and the red/black hat problem.
- Reading: Ross 3.3. Also Rosen 7.3, which discusses spam filtering.
- Wed Feb 20 (Lecture 9): Independence
- Topics: Multiplication rule for conditional probability. Independent events: two equivalent definitions and several examples with cards and dice.
People v. Collins and the prosecutor's fallacy. Mutual independence.
- Reading: Ross 3.3, 3.4. Optional: People v.
Collions court opinion. See also the British case involving
Sally Clark.
- Mon Feb 25 (Lecture 10): Mutual Independence and Applications
- Topics: Definition of mutual independence. Examples.
Applications to biased coin flips, primality testing, and
the bound on Ramsey numbers.
- Reading: Ross 3.4. See also Rosen section 7.2.
The Ramsey number bound is example 4m in Ross and
Theorem 4 of section 7.2 of Rosen.
- Wed Feb 27 (Lecture 11): Midterm Review
- Topics: Review of all topics covered thus far.
- Reading: See slides available on Sakai.
- Mon Mar 4 (Lecture 12): Midterm Exam
- Wed Mar 6 (Lecture 13): Random Variables
- Topics: Definition of a random variable. Examples with dice and
coin tossing. Indicator random variables. Range, partition, and
frequency function of a random variable. Independent random
variables. Binomial frequency function.
- Reading: See notes part 3 on Sakai.
- Mon Mar 11 (Lecture 14): More on Random Variables; Expectation
- Topics: More on binomial random variables. Geometric
and negative binomial random variables. Definition of
expectation and the alternative formulation.
- Reading: See notes part 3 on Sakai.
- Wed Mar 13 (Lecture 15): Linearity of expectation
- Topics: Linearity of expectation. Expectation of
binomial, geometric, and negative binomial frequency functions.
Applications to computing expectations: Birthday problem, balls
into bins, and coupon collecting.
- Reading: See notes part 3 on Sakai.
- Mon Mar 25 (Lecture 16): Markov's Inequality; Begin Variance
- Topics: Markov's inequality for non-negative random variables.
Definition of variance and some calculations of variance.
- Reading: See notes part 4 on Sakai.
- Wed Mar 27 (Lecture 17): Computing Variances
- Topics: Expectation of a function of a random variable.
Variance of a sum of independent random variables.
Variance of the bernoulli, binomial, geometric, and negative
binomial distributions.
- Reading: See notes part 4 on Sakai.
- Mon Apr 1 (Lecture 18): Covariance and Chebyshev's Inequality
- Topics: Variance of a sum of dependent random variables
and the definition of covariance. Properties of covariance.
Independence implies correlation but the converse does not hold.
Statement of Chebyshev's inequality and a basic application.
- Reading: See notes part 4 on Sakai. Ross 7.4 and 8.2.
- Wed Apr 3 (Lecture 19): Applications of Chebyshev's; Begin Generating
Functions
- Topics: Proof of Chebyshev's inequality. Law of large
numbers. Confidence via sampling and public polling. Generating
functions: motivation and examples.
- Reading: See notes parts 4 and 5 and the scanned book sections on Sakai. Rosen 8.4 also covers generating functions.
- Mon Apr 8 (Lecture 20): Generating Functions
- Topics: Modeling counting problems with generating functions. Calculating several closed-form expressions for generating functions.
- Reading: Scanned book sections on Sakai. Rosen 8.4 also covers generating functions.
- Wed Apr 10 (Lecture 21): Generating Functions (continued)
- Topics: Some more calculations of generating functions. Sum
and product of two generating functions. Solving counting problems
using generating functions. Begin recurrence relations.
- Reading: Scanned book sections on Sakai. Rosen 8.4 also covers generating functions.
- Mon Apr 15 (Lecture 22): Solving recurrence relations
- Topics: Using generating functions to solve recurrence relations.
Several examples and the general approach. Finding a
formula for Fibonacci numbers.
- Reading: Notes parts 5 on Sakai. These use a slightly different
version of the same approach.