CS 206 - Introduction to Discrete Structures II

Fall 2016


Course Overview:

Course Topics:

General Information:

  1. Instructor: Morteza Monemizadeh (first-name+m at dimacs dot rutgers dot edu, Core 407)
  2. Teaching Assistant: Hareesh Ravi (hr268 at scarletmail dot rutgers dot edu)
  3. Course Website: http://home.dimacs.rutgers.edu/~mortezam/DS2.html
  4. Textbook: Sheldon Ross, A First Course in Probability, 8th or 9th edition
  5. Lecture meetings: Wednesday 12--1:20pm and Friday 1:40pm--3:00pm in Tillett 254 (Livingston Campus)
  6. Recitations:
    1. Section 205: Wednesday 3:35pm--4:30pm in Hill 009
    2. Section 206: Friday 8:55am--9:50am in SEC 207
  7. Midterm (in lecture): Friday, November 4
  8. Final exam: at 8am on December 20 in Tillett 254 (Livingston Campus)
  9. Instructor office hours: 12:00--1pm Fridays in Core 407
  10. TA office hours: 2:30pm--3:30pm Mondays in Hill 270



Date Lectures (Sheldon Ross, A First Course in Probability, 8th or 9th edition) Comments Homework Due Date Solutions
Wednesday, September 7 Class organization and Introduction
Basic principle of counting and Permutations
Examples: 2a, 2b, 2c, 2d, 2e, 3b, 3c, 3d, 3e, 3f
Reading: Chapter 1 (Combinatorial Analysis) Sections 1.1., 1.2. and 1.3
Problem 3 in Assignment 2 is dropped. Homework 1 Wednesday, September 21 (12:20 pm)
(PASSED)
Solutions of HW 1
Wednesday, September 9 Combinations
The Binomial Theorem and its proof by Induction
Examples: 4a, 4b, 4c, 4d, 4e, 5b, 5c
Reading: Chapter 2 (Combinatorial Analysis) Section 1.4.
Wednesday, September 14 Sample space and Events
Axioms of probability, Simple propositions and Inclusion?Exclusion Identity
Examples: 3a, 3b, 4a,
Proposition 4.1, 4.2, 4.3, 4.4
Reading: Chapter 2 (Axioms of Probability) Sections 2.2, 2.3, 2.4.
Friday, September 16 Sample spaces having equally likely outcomes
Examples (See also Comments): 5a, 5b, 5d, 5g, 5i, 5l, 5n
Reading: Chapter 2 (Axioms of Probability) Section 2.5.
Solutions of the Examples
Wednesday, September 21 More examples on Induction and Probability
Reading: Chapter 1 and 2 (Combinatorial Analysis and Axioms of Probability) Problems Sections
Homework 2 Wednesday, September 28 (12:10 pm)
(PASSED)
Friday, September 23 Conditional Probability, Bayes's Formula, Independent Events,
Examples: 2b,3a, 3k, 4c
Reading: Chapter 3 (Conditional Probability and Independence) Sections 3.2, 3.3, 3.4
Wednesday, September 28 Examples: 2d, 2e, 3k, 3n, 4f
Reading: Chapter 3 (Conditional Probability and Independence) Sections 3.2, 3.3, 3.4
Homework 3 Wednesday, October 5 (12:10 pm)
(PASSED)
Friday, September 30 Examples: 3c, 3l, 4g, 4h, 4j
Reading: Chapter 3 (Conditional Probability and Independence) Sections 3.2, 3.3, 3.4
Wednesday, October 5 Examples: 1a, 1b, 2a, 3a, 3b, 4a, 5a
Reading: Chapter 4 (Random Variables) Sections 4.1, 4.2, 4.3, 4.4 and 4.5.
Friday, October 7 Proposition 4.1, Corollary 4.1, Examples: 5a, 6a, 6b
Reading: Chapter 4 (Random Variables) Sections 4.5 and 4.6.
Homework 4 Friday, October 14 (2:00 pm)
(PASSED)
Wednesday, October 12 The Poisson Random Variable, Expectation and Variance of Poisson Random Variable, Example: 7b
Reading: Chapter 4 (Random Variables) Sections 4.7.
Friday, October 14 Geometric, Negative Binomial and Hypergeometric Random Variables,
Expectation and Variance of Geometric, Negative Binomial and Hypergeometric Random Variables
Examples: 8a, 8b, 8d, 8f, 8g, 8i, 8j
Reading: Chapter 4 (Random Variables) Sections 4.8 and 4.9.
Homework 5 Friday, October 21 (3:00 pm)
Wednesday, October 19 Applications of Linearity of Expectation: Binomial, Geometric, Negative Binomial, and Hyper-Geometric Distributions.
Hat (Match) and Coupon Collecting Problems.
Examples: 2e, 2f, 2g, 2h,2i
Continuous Random Variables (definition, probability density function and cumulative distribution function)
Reading: Chapter 7 (Properties of Expectation) Sections 7.2
Reading: Chapter 5 (Continuous Random Variables) Section 5.1
Friday, October 21 Expectation and Variance of Continuous Random Variables.
Examples 1a, 1b, 1c, 2a,2b2c, and 2e.
Reading: Chapter 5 (Continuous Random Variables) Section 5.1 and 5.2
Homework 6 Friday, October 28 (3:00 pm)
Wednesday, October 26 Uniform Random Variables.
Examples: 3a, 3b, 3c,
Reading: Chapter 5 (Continuous Random Variables) Section 5.3
Friday, October 28 Normal Random Variables.
Examples: 4a, 4b, 4c, 4e, 4f, 4g, 4i
Reading: Chapter 5 (Continuous Random Variables) Section 5.4
No Homework ---
Friday, November 2 Normal Random Variables.
Examples: 4a, 4b, 4c, 4e, 4f, 4g, 4i
Reading: Chapter 5 (Continuous Random Variables) Section 5.4
Friday, November 4 Midterm (Chapters 1, 2, 3, and 4) No Homework ---
Wednesday, November 9 Section 6.1: Joint distribution and Marginal Distribution for discrete random variables, Example 1a
Section 6.2: Independent (Discrete) Random Variables, Example 2a
Section 6.3.4: The Distribution of X+Y for (Discrete) Random Variables, Example 3e
Section 6.4: Conditional Distribution for (Discrete) Random Variables, Examples 4a and 4b
Reading: Chapter 6 (Jointly Distributed Random Variables) Sections 6.1, 6.2, 6.3.4, 6.4
Friday, November 11 Section 6.1: Joint distribution and Marginal Distribution for discrete random variables, Example 1a
Section 6.2: Independent (Discrete) Random Variables, Example 2a
Section 6.3.4: The Distribution of X+Y for (Discrete) Random Variables, Example 3e
Section 6.4: Conditional Distribution for (Discrete) Random Variables, Examples 4a and 4b
Reading: Chapter 6 (Jointly Distributed Random Variables) Sections 6.1, 6.2, 6.3.4, 6.4
Homework 7 will be posted Friday, October 18 (3:00 pm)
Wednesday, November 16 Midterm Corrections and Questions Homework 7 Wednesday, November 23 (1:20 pm)
Friday, November 18 The class was cancelled.
Wednesday, November 23 Section 7.4: Covariance and Variance of Sums
Proposition 4.2 and Example 4b
Applications of Linearity of Expectation: Binomial, Geometric, Negative Binomial, and Hyper-Geometric Distributions.
Hat (Match) and Coupon Collecting Problems.
Reading: Chapter 7 (Properties of Expectation) Sections 7.2 and 7.4
Friday, November 25 The class was cancelled (Thanksgiving)
Wednesday, November 30 Section 7.7: Moment Generating Functions
Examples 7a, 7b, 7d, 7f,7g,7h
Reading: Chapter 7 (Properties of Expectation) Sections 7.7
Homework 8 Wednesday, December 7 (1:20 pm)
Friday, December 2 Markov's inequality (Proposition 2.1), Chebyshev's inequality (Proposition 2.1),
The weak law of large numbers (Theorem 2.1), The central limit theorem (Theorem 3.1)
Examples 2a, 3b, 3c, 3e
Reading: Chapter 8 (Limit Theorems) Sections 8.2 and 8.3
Wednesday, December 7 Review: Markov's inequality (Proposition 2.1), Chebyshev's inequality (Proposition 2.1),
Review: The weak law of large numbers (Theorem 2.1), The central limit theorem (Theorem 3.1)
Review: Examples 2a, 3b, 3c, 3e
Reading: Chapter 8 (Limit Theorems) Sections 8.2 and 8.3
Hareesh Ravi reviews Chapter 8
Friday, December 9 Reviewing Chapters 1-8
Review: Problems 8.1 and 8.2
Reading: Chapters 1-8
Wednesday, December 14 Reviewing Chapters 1-8
Reading: Chapters 1-8