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

Please read guidelines for interacting with your TA.

- Group 1. Thu 1-2PM. Venue: LH 611.
- Group 2. Fri 1-2PM. Venue: LH 611.
- Group 3. Mon 1-2PM. Venue: LH 611.
- Group 4. Tue 1-2PM. Venue: LH 611.

- 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.
- Advanced probability: 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.

[LLM18] E. Lehman, F. T. Leighton, and A. R. Meyer. Mathematics for Computer Science, June 2018, 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.
- [Gallier08] Jean Gallier. Discrete Mathematics for Computer Science: Some Notes. arXiv:0805.0585, 2008.
- [Wilf94] Herbert S. Wilf. generatingfunctionology, Academic Press, 1994.
- [Goemans15] Michael Goemans. Generating functions, Lecture Notes for {\em Principles of Discrete Mathematics}, MIT, 2015.
- [MV08] Jiri Matousek and Jan Vondrak. The Probabilistic Method: Lecture Notes, Charles University, 2008.

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

- Tut 1. Posted 18 August 2022.
- Tut 2. Posted 25 August 2022.
- Tut 3. Posted 1 September 2022.
- Tut 4. Posted 8 September 2022.
- Tut 5. Posted 15 September 2022.
- Tut 6. Posted 6 October 2022. Updated 10 October 2022.
- Tut 7. Posted 13 October 2022.
- Tut 8. Posted 20 October 2022.
- Tut 9. Posted 27 October 2022.
- Tut 10. Posted 3 November 2022.

- Each tutorial is numbered. The numbers run from 1 to 10. In the course calendar above the date for each tutorial for each group is clearly marked. For example, T2 for G4 is on 30 August 2022.
- Please attend
*only*your own group's tutorial. - Each tutorial sheet corresponds to a tutorial session, i.e., the tutorial sheets will be numbered from 1 to 10.
- In each tutorial sheet
*one*question will be marked for submission. You must solve this problem at home on a sheet of paper with your name and entry number on it and bring it to the scheduled tutorial session and submit it*at the beginning of the class*, no later than 1:10PM. For example, students of grooup 4 will solve the submission question of tutorial sheet T2 and bring it to class on 30.08.2022. - You can only submit the tutorial submission if you come to class. You cannot send it with someone else. You cannot submit it late.
*No exceptions*. - Plagiarism penalties for the tutorial submission will be extremely harsh. Please see the section on plagiarism below.
- Tutorial solutions will be graded for clarity and completeness along with correctness. The 4 points in bold in "Guidelines for writing a good proof" will be considered mandatory and marks will be deducted if any of them are missing.

- 15%: Quizzes. 5% per quiz. Only the best
**three**out of five will be counted. - 16%: Tutorial exercises. 2% per tutorial exercise. Only the best
**eight**will be counted. - 29%: Minor Exam.
- 40%: 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).**Tutorial submissions**. Tutorial submissions will*only*be accepted during the tutorial session. If you miss the session you are not allowed to submit later or even send it along with a friend. This is a way of enforcing attendance in the tutorial sessions.**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.

**Plagiarism**. Since in the online semesters there has been a lot of cheating, we will have a very strict plagiarism policy. If you copy or allow anyone to copy in any tutorial submission then you will get -25% for the entire course. Both the person who has copied and the person whose work has been copied will get the same penalty. Copying includes: copying from each other, copying from a textbook or any internet source. For tutorial submissions you are allowed to discuss but*you have to write in your own words*. We have received a list of students who are repeating this course due to cheating penalties incurred in I Sem 2021-22. If any of these students is caught plagiarising then they will receive an automatic F grade.

Amitabha Bagchi