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 2-3pm, Hill 448
  • TA: Aditya Potukuchi, ap1311@cs.rutgers.edu, Office hours: Monday 6-7pm, Hill 257
  • TA: Jingjing Liu, jl1322@cs.rutgers.edu, Office hours: Tuesday 10am-11am, CBIM
  • Grader: Anivesh Bataram, ab1517@scarletmail.rutgers.edu, Office hours: TBA
  • Recitation 1: Tue 1:55-2:50pm Brr 4085, Jingjing Liu, section 05
  • Recitation 2: Fri 1:55-2:50pm Lsh B269, Aditya Potukuchi, section 06
  • Official Textbooks

    We will follows the following two sources

  • 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]
  • Recommended but not Required

  • Discrete Mathematics and Its Applications by K. Rosen
    [link]
  • A First Course in Probability by Ross
    [link]
  • Grading

  • Homeworks (20%)
  • In class quizzes (15%)
  • In class midterm 1 (15%) (Feb 28)
  • In class midterm 2 (15%) (April 11)
  • 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: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].

    Lectures

    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