• 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.
• Group 2. Fri 2-3PM.
• Group 3. Mon 2-3PM.
• Group 4. Tue 2-3PM.

• Check your allotted TA from the link above. Note: Some groups have multiple TAs. Make sure to check the TA allotted to you and not your group.
• At the time allotted to your Group, go to the team 2001-COL202 DISCRETE MATHEMATICAL STRUCTUR on Teams.
• In the list of channels look for the channel with your TA's name, e.g., if your TA's name is Arindam then there will be a channel "TA-Arindam." Note: You will be asked to leave if you join the wrong TA's meeting without prior permission. We have made the channels public for your convenience so the occasional rescheduling is easy. Do not abuse the convenience.
• Your TA will set up a meeting within the channel for the scheduled time. Join this meeting at the given time.
• After the tutorial, you are expected to submit the solution on the same day on Gradescope. Even if Gradescope accepts solution after the deadline, no late submissions will be evaluated.

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.
• [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.
• [Bagchi17] Mutual independence, pairwise independence and $k$-wise independence: Events versus random variables, Notes for COL202, I Sem 2017-18, September 2017.

Miscellaneous

• A. Bubna. Elaborated proof of Lemma 1.5.5(ii) of [Die16]. November 2019.
• A. Bagchi. Guidelines for writing a good proof (adapted from Sec 2.7 of [LLM10]), July 2019.

Course calendar

Regarding this calendar please note

• Each lecture has text sections mentioned in parantheses after the topics. These sections may not have been covered in their entirety in the lecture. Nevertheless each section is in the syllabus in its entirety.
• Tutorial sheets will generally be based on the material covered in the previous week.

Tutorials

Tutorial sheets

• Tut 10. Posted 24 December 2020.
• Tut 9. Posted 17 December 2020.
• Tut 8. Posted 28` November 2020.
• Tut 7. Posted 20 November 2020.
• Tut 6. Posted 12 November 2020.
• Tut 5. Posted 1 November 2020.
• Tut 4. Posted 23 October 2020.
• Tut 3. Posted 16 October 2020.
• Tut 2. Posted 8 October 2020.
• Tut 1. Posted 2 October 2020.

Tutorial guidelines

• There will be 10 tutorial sessions. Each tutorial session has a number from T1 to T10. Please check the calendar to see which day which tutorial number is scheduled for your group.
• There will be 10 tutorial sheets, one for each session. You are expected to work on sheet number i in tutorial number i, i.e., in T1 you will work on Tut1, T2 on Tut2 etc. The sheets will be posted at least one day before the scheduled session.
• One or two problems in each tutorial sheet will be marked as for submission. You have to solve this problem and submit it via Gradescope by 11:59PM on the day of your 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. Then upload it to Gradescope.
• Your tutorial submission will be graded for effort and clarity (not necessarily correctness). You will get marked out of 4 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 late under any circumstances.

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

• Lecture delivery. There will be 24 live 80 min lectures delivered via MS Teams at the scheduled times per the time table. These lectures will be archived on Impartus within a day or two of being delivered. There will be 4 pre-recorded 80 min lectures posted on Impartus. The dates for posting these will be announced.
• Tutorial sessions. Tutorials will be conducted on MS Teams at the scheduled times. You are expected to read the tutorial sheet beforehand and be available on Teams with pen and paper handy.
• Quizzes. Five scheduled quizzes will be held during class timings in the first 15 minutes of class. The quiz will be emailed to you and you will have to upload your work to Gradescope. Please see the calendar for the schedule of quizzes. You will be given some extra time to upload the quiz.
• Plagiarism. Since this is an online semester with a lot of scope for cheating, we will have a very strict plagiarism policy. If you copy or allow anyone to copy in any tutorial submission, quiz or exam 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. The penalty will be same for weekly tutorial submissions and for the quizzes and exams. 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.
• Attendance. Since this is an online semester, as per the decision of the Senate there will be no attendance requirement. However, for this class attending lectures is highly recommended and attending tutorials should be considered mandatory. If you miss a tutorial due to internet issues you can take my permission and join the same tutorial with another group.
• Missed minor. If you miss a minor there will be a 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.