CS 206 - Introduction to Discrete Structures II
Spring 2014
Course Overview
This course is an introduction to probability theory and
combinatorics, including their basic mathematical foundations as well as
several applications of each to computer science, and to life. Your work will
involve solving problems through rigorous mathematical reasoning, often constructing proofs, and the course is designed to
teach how to do this.
By studying probability theory you will learn to think about
randomness in a rigorous and sensical way. This is harder (and more
fun) than it sounds as first: One's intuition is easily misled when it comes
to probability, and we will discover surprisingly complex behavior in the world
around us by examining simple processes carefully.
Combinatorics is about counting the number of objects
fitting a given description. It is intimately related to probability theory:
Knowing the number of possibilities for a random outcome often goes a long way
to understanding that random process. But its relevance goes well beyond
probability and thus we will look at several other applications as well.
Course Topics
The course covers the following list of topics, which are broken into three parts. Lecture
summaries will be posted at the bottom of this page. You can also find
previous semesters' class web pages linked from my homepage.
- Part I: Sets, Basic Counting and Probability
- Review of prerequisites: Set basics, countability, proof by induction.
- Basic counting techniques: Addition and multiplication rules, binomial and multinomial coefficients.
- Basic probability: Random processes where all outcomes are equally likely.
- Part II: Probability Theory
- Formal probability theory: Sample spaces, events, probability
measures.
- Conditional probability, Bayes's Theorem, Independence
- Random Variables, with several examples
- Expectation and Variance
- Part III: Advanced Topics
- Advanced counting: Recurrences and Generating Functions
- Randomized data structures and algorithms
- Random walks and Markov chains
- Cryptography
General Information
- Instructor: David Cash (david.cash@cs.rutgers.edu, office Hill 411)
- Course website: http://www.cs.rutgers.edu/~dc789/206-spring-14
- Recommended textbook: H. Rosen, Discrete Mathematics and its Applications, any cheap edition
- Lecture meetings: Tuesday and Friday 12:00pm -- 1:20pm in Tillett Hall room 246 (Livingston Campus).
- Recitations:
- Section 05: Tuesday 1:55pm -- 2:50pm in Tillett Hall room 103C
- Section 06: Friday 1:55pm -- 2:50pm in Tillett Hall room 209
- Instructor office hours: 2:30pm -- 3:30pm Mondays in Hill 411 and by appointment
- Teaching assistants:
- Recitation: Fatma Durak (fbdurak@cs.rutgers.edu)
- Grading: Ana Paula Centeno (anapaula@cs.rutgers.edu)
Expectations, Assignments and Grading
You are expected to attend lectures, and to notify the instructor if you will
miss class. Required readings will be assigned from lecture notes on Sakai,
and optional readings from the text (if you have it) will be noted when
relevant.
Homeworks will be assigned every week. You are allowed to collaborate
on homeworks, but you must write up your own submission. Copying
someone else's work is considered a violation of the Honor Code and will be
addressed accordingly. Homework is worth a significant part of your grade, but
not as much as exams. I recommend viewing them as a chance practice thinking
about problems before exam time -- If you find solutions via collaboration you
will not likely get much out of them, only making things more difficult
later.
There will be two in-class midterms and one final exam. Tentative dates for the midterms are February 28 and April 4.
The final exam will be scheduled by the university.
Final grades will be an average of homework grades (20%), midterm grades (45%),
and final exam grades (35%). The lowest homework grade will be dropped from
the average.
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.
- Tue Jan 21 (Lecture 1): Introduction
- Topics: Review of set notation and concepts.
- Reading: 2.1, 2.2 of Rosen.
- Fri Jan 24 (Lecture 2): Basic Probability and Counting
- Topics: Sample spaces, events, probability when all outcomes are
equally likely. Operations on events. Counting: Addition and Multiplication Principles, with examples.
- Reading: 7.1 (probability), 6.1 (counting) of Rosen.
- Tue Jan 28 (Lecture 3): Counting
- Topics: Counting arrangements (orderings) of objects n objects
and r-out-of-n objects. The Birthday Problem. Counting unordered
selections of r-out-of-n objects. Several examples dealing with
counting strings and poker hands.
- Reading: 6.3 of Rosen and scan (on Sakai).
- Fri Jan 31 (Lecture 4): More Counting
- Topics: Counting arrangements without adjacent repetitions (the
antenna problem). Orderings when some objects are identical (the
BANANA problem). Multinomial coefficients. Selections with repetition
allowed (the "menu selection" trick).
- Reading: Scan (on Sakai).
- Tue Feb 4 (Lecture 5): Yet More Counting, Applications
- Topics: Other examples using counting methods. Combinatorial
identities, starting with Pascal's relationship. Binomial theorem
and simple applications.
- Reading: Scan (on Sakai).
- Fri Feb 7 (Lecture 6): Inclusion-Exclusion
- Topics: Inclusion-exclusion for two and three sets.
General inclusion-exclusion for many sets. de Montmort's card problem.
- Reading: Scan (on Sakai).
- Tue Feb 11 (Lecture 7): Conditional Probability
- Topics: Definition of conditional probability. Examples involving
conditions with cards, tossing balls into boxes.
- Reading: 7.2 of Rosen
- Fri Feb 14 (Lecture 8): Conditional Probability and Independence
- Topics: Multiplication rule for conditional probability and how
to apply it.
Bayes's theorem and an application. Definition of independence.
- Reading: 7.2 of Rosen
- Tue Feb 18 (Lecture 9): Independence
- Topics: Example problems dealing with independence. Reasoning
about probability measures abstractly. Prosecutor's fallacy. Pairwise,
k-wise, and mutual independence.
- Reading: 7.2 of Rosen
- Fri Feb 21 (Lecture 10): Applications of independence
- Topics: The probabilistic method. A lower bound for Ramsey
numbers. Secret sharing in cryptography.
- Reading: 7.2 of Rosen
- Tue Feb 25 (Lecture 11): Problem solving session
- Topics: Solving problems in review for midterm.
- Reading: Practice exam on Sakai.
- Fri Feb 28 (Lecture 12): Midterm
- Tue Mar 4 (Lecture 13): Random Variables
- Topics: Definition of a random variable. Range, partition, and
distribution of a random variable.
- Reading: Notes on Sakai. See also 7.2 and 7.4 of Rosen.
- Fri Mar 7 (Lecture 14): Joint distributions
- Topics: Joint distributions of random variables. Discussion
of the midterm.
- Reading: Joint distributions are not currently covered in the notes on Sakai. They will be updated soon.
- Tue Mar 11 (Lecture 15): Independent Random Variables; The Binomial Distribution
- Topics: Definition of independent random variables and examples.
Repeating independent trials. The Binomial distribution and its derivation.
- Reading: Notes on Sakai. Rosen 7.4 discusses independent random
variables and the binomial distribution.
- Fri Mar 14 (Lecture 16): Bernoulli, Geometric, and Negative Binomial Distributions
- Topics: Definitions and derivations of the Bernoulli, geometric,
and negative binomial distributions.
- Reading: Notes on Sakai.
- Tue Mar 25 (Lecture 17): Expectation
- Topics: Definitions of expectation and alternative formula.
Examples applying both formulas. Expectation of a binomial random
variable. Linearity of expectation.
- Reading: Notes on Sakai. Rosen 7.4.
- Fri Mar 28 (Lecture 18): Linearity of Expectation
- Topics: Method of indicators for computing expectations. Expectation of Geometric, Binomial, and Negative Binomial random variables. Expectation
and the birthday problem, balls into boxes, and coupon collecting.
- Reading: Notes on Sakai. Rosen 7.4.
- Tue Apr 1 (Lecture 19): Tricks with Expectation; Variance
- Topics: Formula for E(g(X)). E(XY) = E(X)E(Y) when X and Y
are independent. Definition of variance, the simpler formula,
and some basic calculations.
- Reading: Next set of notes on Sakai. Rosen 7.4.
- Fri Apr 4 (Lecture 20): Calculating Variance
- Topics: Variance of Bernoulli and geometric random variables.
Variance of sum of pairwise independent random variables, and applications to binomial and negative binomial random variables.
- Reading: Next set of notes on Sakai. Rosen 7.4.
- Tue Apr 8 (Lecture 21): Midterm II
- Fri Apr 11 (Lecture 22): Discussion of the Midterm; Markov's Inequality
- Topics: Solutions for the midterm. Markov's inequality, it's proof
and examples.
- Reading: Next set of notes on Sakai. Markov's Inequality is
only mentioned in problems 37 and 38 in Chpt 7 of Rosen.
- Tue Apr 15 (Lecture 23): Chebyshev's Inequality; Begin Generating
Functions
- Topics: Chebyshev's inequality (statement, proof, application
to examples, comparison to Markov). The idea of generating functions.
- Reading: Rosen 7.4 and scan on Sakai.
- Fri Apr 18 (Lecture 24): Generating Functions
- Topics: How to model a problem using generating functions.
Some "known" generating functions.
- Reading: Scan on Sakai.
- Tue Apr 22 (Lecture 25): Counting with Generating functions
- Topics: Several examples of counting problems solving
with generating functions.
- Reading: Scan on sakai.
- Fri Apr 25 (Lecture 26): Convolutions; Recurrence Relations
- Topics: Convolution formula for the coefficients of A(x)B(x),
with application. Solving recurrence relations using generating
functions.
- Reading: Convolutions are covered in the scan (with a similar
example). Rosen 8.4 covers using generating functions to solve
recurrence relations (I used examples 16 and 17 in class).