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

All registrants

- Why should a CS student study this course? What should your learning goals be? Some rules for this class.
- How to write an email to your professor or TA

- 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 countability.
- 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 orderings.
- 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.

[BSD05] K. Bogart, S. Drysdale, C. Stein.

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.

- A. Bagchi. Quiz 1 solution (local access only). Posted 28 July 2017.
- A. Bagchi. Why should a CS student study this course? What should your learning goals be? Some rules for this class. Posted 24 July 2017.

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 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 4 | T4 | 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.09 | Elementary probability Probability spaces | Self study: BSD05 Ch 5.1, LLM10 Ch 14 | T6 | Tut 6 Quiz 7 |

18.09-24.09 | Conditional probability Independence, Random variables | LLM10 Ch 15-17 | T7 | Tut 7 Quiz 8 |

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.

Amitabha Bagchi