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.

Homework 1: Assigned Jan 22, Due Jan 28
Homework 2: Assigned Jan 28, Due Feb 4
Homework 3: Assigned Feb 4, Due Feb 11
Homework 4: Assigned Feb 11, Due Feb 18
Homework 5: Assigned Feb 18, Due Feb 25
(No homework assigned Feb 25 -- Midterm on Feb 28)
Homework 6: Assigned Mar 4, Due Mar 11
Homework 7: Assigned Mar 11, Due Mar 25

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