Pre-Major Totals. Includes all evaluations apart from Major and Reminor. Posted 18 Nov 2019.

All registrants

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

- Group 1. Thu 2-3PM. Supervised by: Sudeep Agarwal (cs5150295@iitd.ac.in)
- Group 2. Fri 2-3PM. Supervised by: Shubhani (anz168046@iitd.ac.in)
- Group 3. Mon 2-3PM. Supervised by: Raj Kamal (csz188013@iitd.ac.in)
- Group 4. Tue 2-3PM. Supervised by: Mehreen Jabbeen (csz187551@iitd.ac.in)

- 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 counterexample; proof by contraposition; proof by contradiction; mathematical induction; strong induction; recursive mathematical definitions; well orderings.
- 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.
- 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.

[LLM10] E. Lehman, F. T. Leighton, and A. R. Meyer. Mathematics for Computer Science, Lecture notes from Fall 2010, MIT Open Courseware.

- [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. - [GKP94] R. L. Graham, D. E. Knuth, O. Patashnik. Concrete Mathematics: A foundation for computer science, 2nd ed. Pearson, 1994. (Available in the Central Library and in affordable Indian edition).
- [Die16] Reinhard Diestel. Graph Theory, 5e, 2016.
- [SAK02] S. Arun-Kumar. Introduction to Logic for Computer Science (WWW draft), IIT Delhi, September 2002. Posted 5 September 2019.
- [Gallier08] Jean Gallier. Discrete Mathematics for Computer Science: Some Notes. arXiv:0805.0585, 2008. Posted 18 September 2019.
- [Wilf94] Herbert S. Wilf. generatingfunctionology, Academic Press, 1994. Posted 20 October 2019.
- [Goemans15] Michael Goemans. Generating functions, Lecture Notes for {\em Principles of Discrete Mathematics}, MIT, 2015. Posted 24 October 2019.
- [Bagchi17] Mutual independence, pairwise independence and $k$-wise independence: Events versus random variables, Notes for COL202, I Sem 2017-18, September 2017. Posted 7 November 2019.

- A. Bagchi. Guidelines for writing a good proof (adapted from Sec 2.7 of [LLM10]). Posted 29 July 2019.

Regarding this calendar please note

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

- Tut 12. Posted 7 November 2019.
- Tut 11. Posted 31 October 2019.
- Tut 10. Posted 24 October 2019.
- Tut 9. Posted 17 October 2019.
- Tut 8. Posted 10 October 2019.
- Tut 7. Posted 18 September 2019.
- Tut 6. Posted 12 September 2019.
- Tut 5. Posted 4 September 2019.
- Tut 4. Posted 29 August 2019.
- Tut 3. Posted 8 August 2019.
- Tut 2. Posted 2 August 2019.
- Tut 1. Posted 25 July 2019.

- 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 and clarity (not necessarily correctness). You will get marked out of 3 based on the grader's
*subjective*judgment on whether you have put in effort or not and on the level of clarity in what you have written. - 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 are given in the course calendar above.

- 8%: Quizzes. 4% per quiz. Only the best
**two**will be counted. - 12%: Tutorial exercises. 1.5% per tutorial exercise. Only the best
**eight**will be counted. - 22%: I Minor Exam.
- 22%: II Minor Exam.
- 36%: 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. There is no other attendance-based restriction in this course. Attendance will be through Timble and Timble issues will not be discussed (take them up with Timble admin).**Missed minors**. For missed minors there will be a single reminor 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 up to 2 of each.**Re-grading policy for quizzes and exams**.*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