COL202: Discrete Mathematical Structures
I semester: 2017-18
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."
K. Chang, Marina Ratner, Emigre Mathematician Who Found Midlife Acclaim, Dies at 78, New York Times, 25 July 2017.
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.
- Group 1. Thu 1-2PM. Supervised by: Dishant Goyal (csz178060).
- Group 2. Fri 1-2PM. Supervised by: Anagh Prasad (cs5130277).
- Group 3. Mon 1-2PM. Supervised by: Gagan Madan (me1130015).
- Group 4. Tue 1-2PM. Supervised by: Shubhankar Suman Singh (csz168113).
- Basics of counting: Counting arguments; pigeonhole
principle; permutations and combinations; inclusion-exclusion,
recurrence relations, generating functions.
- Fundamental structures; Functions (surjections, injections, inverses,
composition); relations (reflexivity, symmetry, transitivity,
equivalence relations); sets (Venn diagrams, complements, Cartesian
products, power sets); pigeonhole principle; cardinality and
- Basic logic: Propositional logic: logical connectives;
truth tables; normal forms (conjunctive and disjunctive); validity;
predicate logic; limitations of predicate logic, universal and
existential quantification; modus ponens and modus tollens. Proof
techniques: Notions of implication, converse, inverse,
contrapositive, negation, and contradiction; the structure of formal
proofs; direct proofs; proof by couunterexample; proof by
contraposition; proof by contradiction; mathematical induction;
strong induction; recursive mathematical definitions; well
- Introduction to probability: Events, probability, probability of unions and intersections of events, independence and conditional probabilities, random variables, expectations, variances, basic tail inequalities.
- Intro to graph theory.
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.
- [Gallier08] Jean Gallier. Discrete Mathematics for Computer Science: Some Notes. arXiv:0805.0585, 2008. Posted 20 August 2017.
- [Arun-Kumar02] S. Arun-Kumar. Introduction to Logic for Computer Science (WWW draft), IIT Delhi, September 2002, retrieved 12 August 2017. Posted 14 August 2017.
- [Charikar02] Moses Charikar. Lecture slides for 7 Oct 2002, Handouts for Computer Science 341 (Discrete Mathematics) Fall 2002, Princeton University, 2002, retrieved 12 August 2017. Posted 14 August 2017.
- [Wilf94] Herbert S. Wilf. generatingfunctionology, Academic Press, 1994. Posted 7 August 2017.
- [LLM10] E. Lehman, F. T. Leighton, and A. R. Meyer. Mathematics for Computer Science, Lecture notes from Fall 2010, MIT Open Courseware. Posted 27 July 2017.
- [Bogart05] K. Bogart. Enumerative Combinatorics through Guided Discovery, 2005. Posted 23 July 2017.
Regarding this calendar please note
|Week ||Topics ||Source ||Tutorial Number ||Downloads |
|24.07-30.07 ||Basic Counting ||BSD05 Ch 1; Bogart05 Ch 1||No 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|
|07.08-13.08 ||Generating functions ||In class: Wilf94 Ch 1 |
Self study: LLM10 Ch 12
|T2 ||Tut 2|
|14.08-20.08 ||Generating functions contd. |
Relations and infinite sets
Arun-Kumar02, Ch 1
|T3 ||Tut 3|
|21.08-27.08 ||Partial orders ||Gallier08 Ch 4||T4 ||Tut 4|
|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|
|11.09-17.09||Elementary probability |
|Self study: BSD05 Ch 5.1, LLM10 Ch 14 ||T6 ||Tut 6|
|18.09-24.09 ||Conditional probability |
Independence, Random variables
|LLM10 Ch 15-17||T7 ||Tut 7|
|25.09-01.10 || ||T8 ||To be posted|
|02.10-08.10 || ||No tut: Minor 2 ||None|
|09.10-15.10 || ||T9 ||To be posted|
|16.10-22.10 || ||No tut: Sem break ||None|
|23.10-29.10 || ||T10 ||To be posted|
|30.10-05.11 || ||T11 ||To be posted|
|06.11-12.11 || ||T12 ||To be posted|
|13.11-19.11 || ||T13 ||To be posted|
- The source material for topics covered in lecture in a given week are mentioned under the column titled "Source".
- All the material given in the portions of the texts mentioned under "Source" may not have been covered in lecture. Nevertheless it is all in the syllabus.
- Tutorial sheets will generally be based on the material covered in the previous week.
- Tutorial sheets will be posted in the week before the tutorial is scheduled.
- One or two problems will be marked as for submission. You have to solve this problem and bring it to the tutorial. Write your solution on a plain piece of paper and put your name, entry number and the Tutorial number on top of the page.
- Your tutorial submission will be graded for effort in a pass/fail mode, i.e. you will get either 1 or 0 marks based on the grader's subjective judgment on whether you have put in effort or not.
- Your tutorial submission will not be accepted if you don't attend the tutorial, i.e. you cannot send your submission with a friend. Your tutorial submission will be graded only if you attend the relevant tutorial.
- The tutorial schedule and the sheets associated with each tutorial is given in the course calendar above.
- 32%: Quizzes. 4% per quiz. Only the best eight will be counted.
- 8%: Tutorial exercises. 1% per tutorial exercise. Only the best eight will be counted.
- 15%: I Minor Exam.
- 15%: II Minor Exam.
- 30%: Major Exam.
- Attendance. 75% attendance is an institute requirement for getting an I grade or for being allowed to take a remajor in case of getting an E. This will be enforced at the institute level. There is no other attendance-based restriction in this course.
- Missed minors. For missed minors there will be a single missed minor held after the major at an announced time. The syllabus will be the entire course.
- Missing other evaluations. There will be no re-quizzes or make-up tutorials for any reason even illness. We will have enough of both to ensure that you will not suffer for missing upto 4 of each.
- Quiz re-grading policy.
- No regrading requests by email, only through gradescope.
- Ask for regrading only if you think your solution is right but has been marked as wrong.
- No regrading for partial marks, i.e., if you have been given marks for attempting, that is a subjective decision and will not be reviewed.
- Frivolous regrading requests will get -0.5.
- You need to describe in detail why you think your marks should be increased. Saying "Recheck Q2" will be considered a frivolous request and treated accordingly.