• 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

Tutorials

• Group 1. Mon 1-2PM. Venue: LH 520.
  TA: Hridayansh, mcs242447
  Office hours: Wed 4PM-5PM, Venue: Teams (click here to join).
• Group 2. Tue 1-2PM. Venue: LH 520.
  TA: Ankit, cs1210229
  Office hours: Mon 4PM-5PM, Venue: Teams (click here to join).
• Group 3. Thu 1-2PM. Venue: LH 520.
  TA: Sahil, csz248490
  Office hours: Tue 4PM-5PM, Venue: SIT 309
• Group 4. Fri 1-2PM. Venue: LH 520.
  TA: Shashwat, csz248012
  Office hours: Tue 3PM-4PM, Venue: Teams (click here to join).

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 9 January 2025.
• Tut 2. Posted 16 January 2025.

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 24 January 2025.
• 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. This submission is to be written in class in front of your TA in the manner of an invigilated exam with all devices placed at a distance from you. The papers will be given at 1PM and collected at 1:12PM and regular tutorial activity will commence. If you arrive late you will not get extra time.
• If you leave the tutorial after submitting the paper, your paper will not be graded.
• 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.
• No make up submissions under any circumstances, including medical reasons. Since only the best 7 out of 10 will be considered, you can miss up to 3 tutorials without any loss. Anyone who misses more than 3 tutorials should consider withdrawing the courses.

Evaluation

• 28%: Tutorial exercises. 4% per tutorial exercise. Only the best 7 out of 10 will be counted.
• 28%: Midterm Exam.
• 44%: Major Exam.

Policies

• Grading. The following rules will be followed for grading
  • Any score strictly below 20 will get an F.
  • A score from 20 to any value strictly less than 30 will get an E and be eligible for a remajor if the attendance requirement is met.
  • A grades will be given at a score which is at least 80. However, there is no guarantee that you will get an A if you have a score of 80.
  • All other grades are discretionary and no discussion on them will be entertained.
• Attendance.
  • Lecture attendance will be taken by calling out names in class. If you arrive after your name is called you will not be given attendance. To make this fair, I will choose a random number between 1 and the number of students in the class every day and begin reading from that point (with wrap around).
  • Lecture attendance will not be taken for the first three lectures.
  • For the purposes of 75% attendance in lectures, the following formula will be used: if #lectures attended by you + 3 + no of classes cancelled >= floor(0.75 * 42) = 31, then you will be deemed to have attended 75% of lectures. Note that the first 3 classes are being given to you for free.
  • If your lecture attendance is <75% by the formula above then you will receive one letter grade lower than what you would normally get based on your score. This rule will not apply to the D grade. E will be downgraded to F and you will not be eligible for a remajor.
  • Tutorial attendance will not be considered in order to make up lecture attendance.
• Missed midterm. If you miss the midterm due to medical reasons there will be a make up 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.
• 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.
• Unfair means. All submissions are under invigilation this semester but, despite that, if we catch any use of unfair means, strict action will be taken. A minimum penalty of 10% of the course marks will be levied. However, if this lower your marks below 30 your grade will not be lowered below a D. A similar penalty will be enforced if any case of proxy attendance is caught, and it will be applied to the person who marked the proxy attendance as well as the person whose attendance was marked.
• Audit policy. To get an audit pass grade a student must have (1) 75% lecture attendance as defined above (2) at least 50% marks in the quiz component and (3) at least 50% marks overall.