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