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:[link]

[link]

[link]

[PDF available from the library website]

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:55pm 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 16 | Course organization and 205 recap | Chapters 1, 2 and 5 of Rosen |

Jan 19 | 205 recap and Basics of Counting | Chapters 1, 2 and 5 of Rosen |

Jan 23 | Basics of Counting | Chapters 1, 2 and 5 of Rosen Chapter 15 of Lehman, Leighton, Meyer |

Jan 26 | Basics of Counting | Chapters 6 of Rosen Chapter 15 of Lehman, Leighton, Meyer |

Jan 30 | Permutations/Combinations | Chapters 6 of Rosen Chapter 15 of Lehman, Leighton, Meyer |

Feb 2 | Permutations/Combinations | Chapters 6 of Rosen Chapter 15 of Lehman, Leighton, Meyer |

Feb 6 | Pigeonhole Principle and Inclusion/Exclusion | Chapters 6 of Rosen Chapter 15 of Lehman, Leighton, Meyer |

Feb 9 | Pigeonhole Principle and Inclusion/Exclusion | Chapters 6 of Rosen Chapter 15 of Lehman, Leighton, Meyer |

Feb 13 | Pigeonhole Principle and Combinatorial proofs | Chapters 6 of Rosen Chapter 15 of Lehman, Leighton, Meyer |

Feb 16 | Combinatorial proofs and Binomial Coefficients | Chapters 6 of Rosen Chapter 15 of Lehman, Leighton, Meyer |

Feb 20 | Binomial Coefficients | Chapters 6 of Rosen Chapter 15 of Lehman, Leighton, Meyer |

Feb 23 | Midterm Review | |

Feb 27 | Midterm I | |

March 2 | Probability | Chapter 2 of Ross |

March 6 | Probability | Chapter 2 of Ross |