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

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

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

Miscellaneous

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

Course calendar

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.

Tutorials

Tutorial sheets

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

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

Evaluation

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

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