COL202: Discrete Mathematical Structures

I semester: 2017-18

Amitabha Bagchi

Etienne Ghys, a mathematician at Ecole Normale Superieure de Lyon in France, recalled spending six months trying to understand the results of Marina Ratner's dynamics research to present them at a seminar. When he discussed the papers with her, he told her that he had the feeling that she had written the papers not for other mathematicians to understand but mainly to convince herself that the theorems were correct.

Dr. Ghys said Dr. Ratner replied: "Yes! Exactly! You understood why and how I write mathematics."

Excerpted from

K. Chang, Marina Ratner, Emigre Mathematician Who Found Midlife Acclaim, Dies at 78, New York Times, 25 July 2017.

End term instructions

Grading related:
Grade related:

Meet the class mascot: P L Butwhy! --->

All registrants must read:

Timings and Venues


Mon Thu 9:30AM to 10:50AM, LH 316.


All tutorials will be conducted in Room LH 604.



The primary text book for this class will be:
[BSD05] K. Bogart, S. Drysdale, C. Stein. Discrete Math for Computer Science Students.
For the purposes of this class the book has been mirrored locally.

Additional Material


Course calendar

Week Topics Source Tutorial Number Downloads
24.07-30.07 Basic Counting BSD05 Ch 1; Bogart05 Ch 1No tutorial Quiz 1
31.07-06.08 Series sums, Recurrences In class: LLM10 Ch 9.4, 10.1, 10.2.
Self study: LLM10 Ch 9.1-9.3, 9.5, 9.6, 10.3.
T1 Tut 1
Quiz 2
07.08-13.08 Generating functions In class: Wilf94 Ch 1
Self study: LLM10 Ch 12
T2 Tut 2
Quiz 3
14.08-20.08 Generating functions contd.
Relations and infinite sets
Arun-Kumar02, Ch 1
T3 Tut 3
Quiz 4
21.08-27.08 Partial orders Gallier08 Ch 4T4 Tut 4
Quiz 5
28.08-03.09 No lecture: Minor 1 No tut: Minor 1 None
04.09-10.09 Partial orders contd. In class: Gallier08 Ch 4
Self study: LLM10 Ch 7.6-7.9
T5 Tut 5
Minor 1
Quiz 6
11.09-17.09Elementary probability
Probability spaces
Self study: BSD05 Ch 5.1, LLM10 Ch 14 T6 Tut 6
Quiz 7
18.09-24.09 Conditional probability
LLM10 Ch 15-16T7 Tut 7
Quiz 8
25.09-01.10 Random variables
Mean, variance
Prob. generating fns
LLM10 Ch 17, 18, 19.1-19.3
GKP94 Ch 8.3
T8 Tut 8
02.10-08.10 No lecture: Minor 2 No tut: Minor 2 None
09.10-15.10 Graph Theory:
Diestel16 Ch 1.1-1.3T9 Minor 2
Quiz 9
16.10-22.10 No lecture: Sem break No tut: Sem break None
23.10-29.10 Connectivity, Trees Diestel16 Ch 1.4, 1.5T10 Tut 10
Quiz 10
30.10-05.11 Bipartite Graphs,
Euler Tours
Diestel16 Ch 1.6, 1.8T11 Tut 11
Quiz 11
06.11-12.11 Logic: Propositions
and predicates
LLM10 Ch 1
BSD05 Ch 3.1, 3.2
T12 Tut 12
13.11-19.11 Proofs LLM10 Ch 2
BSD05 Ch 3.3
T13 Tut 13

Update: All quizzes are now publicly available from outside IITD as well.
Click here to download as a single zip. Posted 26 February 2018.

Regarding this calendar please note




Amitabha Bagchi