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

Lecture

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

Tutorial

All tutorials will be conducted in Room LH 604.

Topics


Texts

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

Miscellaneous


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
Charikar02
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
Independence
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:
Basics
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
Regarding this calendar please note

Tutorials


Evaluation

Policies


Amitabha Bagchi