Course Syllabus

The course provides the background in combinatorics, probability theory and graph theory required in design and analysis of algorithms, in system analysis, and in other areas of computer science.

Basic information
• Course Number: 01:198:206 Sections 01, 02, 03, and 07
• Instructor: Konstantinos Michmizos
• Email: michmizos@cs.rutgers.edu
• Course Type: Undergraduate
• Credits: 4
• Learning Management System (LMS): https://rutgers.instructure.com/courses/104702

  • Meeting Time: Mon & Thu 12:00 - 1:20 PM
  • Meeting Place: webex link available upon logging on canvas

Textbooks:

1) Mathematics for Computer Science
Lehman, Leighton, and Meyer, 2012
https://people.csail.mit.edu/meyer/mcs.pdf

2) K. Rosen, Discrete Mathematics and Its Applications, any recent edition.
3) J. K. Blitzstein and J. Hwang, Introduction to Probability, any edition
4) S. Ross, A First Course in Probability, any edition

Textbooks are not required. You don’t need to buy them in order to do well in the course.

In this course, we will study combinatorics and discrete probability.

  • Counting: binomial coefficients, permutations, combinations, partitions
  • Recurrence relations and generating functions
  • Discrete probability:
    • Events and random variables
    • Conditional probability, independence
    • Expectation, variance, standard deviation
    • Binomial, poisson and geometric distributions; law of large numbers
  • Some topics from graph theory: paths, components, connectivity, Euler paths, Hamiltonian paths, planar graphs, trees

Grading

Grades will be calculated out of 100 points:

Item Points
Homework 300
Quizzes 700

There will be around 4 homework assignments (1 per month).

There will be around 12 quizzes (1 per week).

Grade disputes must be raised within one week of grades being returned.

Late assignments are not accepted.

Schedule

Reading refers to the textbook: "Mathematics for Computer Science" by Eric Lehman, F. Thomson Leighton, Albert R. Meyer (CC BY-SA 3.0 (Links to an external site.))

Week Topic Reading
1 Counting LLM Ch 15
2 Counting LLM Ch 15
3 Counting LLM Ch 15
4 Generating functions LLM Ch 16
5 Probability spaces LLM Ch 17
6 Conditional probability LLM Ch 18
7 Random variables LLM Ch 19
8 Random variables LLM Ch 19
9 Deviation LLM Ch 20
10 Random walks LLM Ch 21
11 Recurrences LLM Ch 22
12 Directed graphs LLM Ch 10
13 Simple graphs LLM Ch 12
14 Planar graphs LLM Ch 13

Course Summary:

Date Details Due