This is an introductory course in combinatorics and probability theory, two branches of mathematics that are of fundamental importance in computer science. Below is an outline of the topics covered during the course

Part I:We will follows the following two sources

[link]

[PDF available from the library website]

[link]

[link]

All homeworks must be submitted on sakai. You can either typeset them in LaTex/Word or scan handwritten work. It is your responsibility that your writing is legible. Failure to do so will result in less or no points at all. Homeworks must be submitted by 11:59pm EST of the due date. **Late homeworks are not accepted**. Due to the large size of the class, we will not accommodate any requests for regrading. The TA/Grader's decision in all such matters will be final. Homeworks will consist of an easy section and a hard section. You are supposed to solve the easy section on your own. For the hard section, you are allowed to discuss in groups of 2 or 3, provided you have spent enough time(> 24 hrs) thinking about the solution yourself. A discussion is meant to be a collaborative effort to help everyone involved understand the problem better. Asking for solutions is not considered a collaborative effort. **In the end, you must write all the solutions in your own words.** You must also write the names and Rutgers id's of the people that you discussed the homework problems with. We will follow the [Rutgers academic policy on cheating].

Date | Subject | Reading |
---|---|---|

Jan 17 | Course organization and 205 recap | Chapters 1, 4 and 6 of Lehman, Leighton, Meyer |

Jan 20 | Basics of Counting | Chapter 15 of Lehman, Leighton, Meyer |

Jan 24 | Counting II | Chapter 15 of Lehman, Leighton, Meyer Chapter 6 of Rosen book |

Jan 27 | Permutations/Combinations | Chapter 15 of Lehman, Leighton, Meyer Chapter 6 of Rosen book |

Jan 31 | Permutations/Combinations and Pigeonhole Principle | Chapter 15 of Lehman, Leighton, Meyer Chapter 6 of Rosen book |

Feb 3 | Advanced counting techniques | Chapter 15 of Lehman, Leighton, Meyer Chapter 6 of Rosen book |

Feb 7 | Inclusion/Exclusion | Chapter 15.12 of Lehman, Leighton, Meyer |

Feb 10 | Inclusion/Exclusion | Chapter 15.12, 15.13 of Lehman, Leighton, Meyer |

Feb 17 | Combinatorial Proofs | Chapter 15.13 of Lehman, Leighton, Meyer |

Feb 21 | Binomial/Multinomial Coefficients | Chapter 6.4 of Rosen book |

March 3 | Probability | Chapters 1.1, 1.2 of Carlton and Devore |

March 7 | Conditional Probability, Independence | Chapters 1.4, 1.5 of Carlton and Devore |

March 10 | Law of Total Probability, Bayes Theorem | Chapter 1.4 of Carlton and Devore |

March 21 | Random variables | Chapters 2.1, 2.3 of Carlton and Devore |

March 24 | Random variables and Expectation | Chapters 2.1, 2.3 of Carlton and Devore |

March 28 | Random variables and Expectation | Chapters 2.1, 2.3 of Carlton and Devore |

March 31 | Conditional Expectations, Law of Total Expectation | Chapter 4.4 of Carlton and Devore |

April 4 | Variance and Standard Deviation | Chapter 2.3 of Carlton and Devore |

April 14 | Variance and Standard Deviation | Chapter 2.3 of Carlton and Devore |

April 18 | Variance and probablity inequalities | Chapter 2.3 of Carlton and Devore |

April 21 | Probablity inequalities | Chapter 2.7 of Carlton and Devore |