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

Timings and Venues

Lecture

Tutorial

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

Topics

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

Texts

Other Texts

• [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.

Miscellaneous

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

Course calendar

Tutorials

Tutorial sheets

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

Tutorial guidelines

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

Evaluation

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

Policies

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