CS 206: Course Description

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: Combinatorics
  • Recap of basics -- sets, function, proofs, induction
  • Basic counting techniques
  • Pigeonhole principle
  • Recurrences and generating functions
  • Part II: Probability
  • Sample spaces and events
  • Basics of probability
  • Independence, conditional probability
  • Random variables, expectation, variance
  • Moment generating functions
  • Part III: Advanced Material
  • Randomized algorithms
  • Machine Learning and statistical inference
  • Staff and Office Hours

  • Instructor: Pranjal Awasthi, pranjal.awasthi@cs.rutgers.edu, Office hours: Wednesday 2pm-3pm, CoRE 308
  • TA: Aditya Potukuchi, ap1311@cs.rutgers.edu, Office Hours: Monday 7pm-8pm, Hill 257
  • TA: Vishvajeet Nagargoje, van20@rutgers.edu, Office Hours: Thursday 3:15pm-4:15pm, Hill 202
  • Grader: Chengguizi Han, chengguizi.han@gmail.com.
  • Recitation 1: Aditya, Tue 1:55-2:50pm TIL 116, section 05
  • Recitation 2: Vishvajeet, Thu 1:55-2:50pm LSH B269, section 06
  • Study Group 1: Monday 8:10-9:30pm TIL 111 P
  • Study Group 2: Thursday 8:10-9:30pm TIL 111 P
  • Official Textbooks

  • Discrete Mathematics and Its Applications by K. Rosen
    [link]
  • A First Course in Probability by Ross
    [link]
  • Recommended but not Required

  • Mathematics for Computer Science by Lehman, Leighton and Meyer
    [link]
  • Probability with Applications in Engineering, Science, and Technology by Carlton and Devore
    [PDF available from the library website]
  • Grading

  • Homeworks (20%)
  • In class quizzes (15%)
  • In class midterm 1 (15%) (Feb 27)
  • In class midterm 2 (15%) (April 10)
  • Final Exam (30%) (Date TBA)
  • Class participation (5%)
  • Homework Policy

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

    Lectures

    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