COL202, Spring Semester 2024

Discrete Mathematical Structures

Instructor: Rohit Vaish ()

Teaching Assistants:
Jatin Yadav (),
Surbhi Rajput (),
Akshay Pratap Singh (),
Soumil Aggarwal (),
Adit Malhotra ()


Course Information

What this course is about

This course will introduce its participants to fundamentals of discrete mathematics that they can apply to future courses in computer science and related areas.

An important goal of the course will be to develop familiarity with and an appreciation of rigorous mathematical reasoning (or proofs).

Who is this course aimed at

The course is designed for second and third year undergraduate students who want to do advanced courses in computer science in the future.

This offering of COL202 is for non-CS students; CS students should sign up for the Fall semester offering.

Prerequisites

This is a theoretical course that will require familiarity with high school (Standards 11 and 12) mathematics.

Reference texts
  • [LLM-Book] E. Lehman, F. T. Leighton, and A. R. Meyer. Mathematics for Computer Science, June 2018 [pdf]
  • [LLM-Notes] E. Lehman, F. T. Leighton, and A. R. Meyer. Mathematics for Computer Science, Course notes from Fall 2010, MIT OpenCourseWare [pdf]


Admin

Lecture and tutorial timings

Lectures: TWF 10-11AM. Venue: LH316.

Tutorials: M/T/Th/F 1-2PM. Venue: LH615. (Tutorial Groups).

Sign up on the Microsoft Teams channel of the course for announcements.

Evaluation policy

Tutorials: 24% (best eight x 3%)
Quizzes: 36% (best three x 12%)
Minor: 20%
Major: 20%

  • For missed minor and/or major exam due to a medical reason, a single exam will be held after the regular major exam (date will be announced later on May 04, 2024) for which the syllabus will be the entire course. The weightage of this make-up exam will be 20%.

    Only those who obtain prior approval from the instructor (before the date of the missed regular minor and/or regular major exam) and have at least 75% attendance will qualify for this exam. In particular, if you miss both the regular minor and the regular major exam, there will still be only one make-up exam (worth 20%).

  • For students with an E grade, a remajor exam will be held at the start of the next semester. Again, at least 75% attendance will be required.
Audit policy: To qualify for an NP grade, you need at least 50% score overall and at least 75% attendance.

Date Lectures Tutorials
Week 1
Jan 01 (Mon)
    No tutorial
Jan 02 (Tue) Lecture 1: What is a Proof?
  • Slides
  • Additional reading: LLM-Book 1.1-1.4
    • No tutorial
    Jan 03 (Wed) Lecture 2: Propositional Logic
  • Slides
  • Additional reading: LLM-Notes Chapter 1
  • Veritasium: Math's Fundamental Flaw
    Jan 04 (Thurs)
      No tutorial
    Jan 05 (Fri) Lecture 3: Patterns of Proof
  • Slides
  • Additional reading: LLM-Notes Chapter 2
  • 3Blue1Brown: How to lie using visual proofs
    • No tutorial
    Week 2
    Jan 08 (Mon) Last date for course drop
    Jan 09 (Tue) Lecture 4: Induction
  • Slides
  • Additional reading: LLM-Notes Ch 3, Sec 3.2
  • Puzzles and Paradoxes in Mathematical Induction
  • Jan 10 (Wed) Lecture 5: Induction and Invariant
  • Slides
  • Additional reading: LLM-Notes Chapter 3, Sec 3.3.4

  • Last date for adding courses in lieu of dropped courses
    Jan 11 (Thurs) Finalization of roll lists
    Jan 12 (Fri) Lecture 6: Strong Induction
  • Slides
  • Additional reading: LLM-Notes Chapter 3, Sec 3.4
  • Week 3
    Jan 15 (Mon)
    Jan 16 (Tue) Lecture 7: Well Ordering Principle
  • Slides
  • Additional reading: LLM-Book Chapter 2
  • Jan 17 (Wed) Lecture 8: Quiz 1
  • Solutions
    Jan 18 (Thurs)
    Jan 19 (Fri) Lecture 9: Number Theory I: GCD
  • Slides
  • Additional reading: LLM-Book Chapter 9, Sec 9.1-9.2.2
  • Jan 20 (Sat)
    Friday timetable
    Lecture 10: Number Theory II: GCD Applications
  • Slides
  • Additional reading: LLM-Book Chapter 9, Sec 9.2.3-9.4
  • Week 4
    Jan 22 (Mon)
    Jan 23 (Tue) Lecture 11: Number Theory III: GCD Applications and Congruence
  • Slides
  • Additional reading: LLM-Book Chapter 9, Sec 9.6
  • Jan 24 (Wed) Lecture 12: Number Theory IV: Congruence and Euler's Function
  • Slides
  • Additional reading: LLM-Book Chapter 9, Sec 9.9 and 9.10.1
    Jan 25 (Thurs)
    Jan 26 (Fri)
    Republic Day
    No lecture
      No tutorial
    Week 5
    Jan 29 (Mon)
    Jan 30 (Tue) Lecture 13: Number Theory V: Euler's Theorem
  • Slides
  • Additional reading: LLM-Book Chapter 9, Sec 9.10
  • Jan 31 (Wed) Lecture 14: Number Theory VI: Secret Sharing and Public Key Cryptography
  • Slides
  • Additional reading: LLM-Book Chapter 9, Sec 9.11
  • The 'R' in RSA on Numberphile
    Feb 01 (Thurs)

    Feb 02 (Fri) Lecture 15: Quiz 2
  • Solutions
  • Week 6
    Feb 05 (Mon)
    Feb 06 (Tue) Lecture 16: Graph Theory
  • Slides
  • Additional reading: LLM-Book Chapter 12, Sec 12.1, 12.2, and 12.6
  • Feb 07 (Wed) Lecture 17: Graph Coloring and Matching
  • Slides
  • Additional reading: LLM-Book Chapter 12, Sec 12.5 and 12.6
    Feb 08 (Thurs)
    Feb 09 (Fri) Lecture 18: Perfect Matchings
  • Slides
  • Additional reading: LLM-Book Chapter 12, Sec 12.5
  • Week 7
    Feb 12 (Mon)
    Feb 13 (Tue) Lecture 19: Matchings: Perfect and Stable
  • Slides
  • Additional reading: LLM-Book Chapter 12, Sec 12.5 and Chapter 6, Sec 6.4
  • Feb 14 (Wed) Lecture 20: Stable Matchings (Contd.)
  • Slides
  • Additional reading: LLM-Book Chapter 6, Sec 6.4
    Feb 15 (Thurs)

    Feb 16 (Fri) Lecture 21: Walks, Cycles, and Trees
  • Slides
  • Additional reading: LLM-Notes Chapter 5, Sec 5.4-5.7
  • Week 8
    Minor: Rescheduled to Week 9
      Week 9 (Mid-Term Exams)
      Feb 28 (Wed) Minor: LH 108 and LH 111, 8-10AM
    • Solutions
      • Week 10
        Mar 04 (Mon)
        Friday timetable
        Lecture 22: Recap and Minimum Spanning Trees
      • Slides
      • Additional reading: LLM-Notes Chapter 5, Sec 5.7.3-5.7.4
      • Mar 05 (Tue) Lecture 23: Minimum Spanning Trees (Contd.)
      • Slides
      • Additional reading: LLM-Notes Chapter 5, Sec 5.7.4
      • Mar 06 (Wed) Lecture 24: Euler Tours
      • Slides
      • Additional reading: LLM-Notes, Chapter 5, Sec 5.6.3-5.6.5
      • How Euler tours help in genome sequencing
        Mar 07 (Thurs)

        Mar 08 (Fri)
        Maha Shivaratri
        No lecture
          No tutorial
        Week 11
        Mar 11 (Mon)

        Mar 12 (Tue)
        Friday timetable
        No lecture
        Mar 13 (Wed) Lecture 25: Directed Graphs
      • Slides
      • Additional reading: LLM-Notes, Chapter 6, Sec 6.1.2 and LLM-Book, Chapter 10, Sec 10.5
        Mar 14 (Thurs)

        Mar 15 (Fri) Lecture 26: Sums
      • Slides
      • Additional reading: LLM-Book, Chapter 14, Sec 14.1-14.3
        • No tutorial
        Week 12
        Mar 18 (Mon)
        Mar 19 (Tue) Lecture 27: Sums and Asymptotics
      • Slides
      • Additional reading: LLM-Book, Chapter 14.3-14.7
      • Mar 20 (Wed) Lecture 28: Quiz 3
      • Solutions
        Mar 21 (Thurs)

        Mar 22 (Fri) Lecture 29: Recurrence
      • Slides
      • Additional reading: LLM-Notes, Chapter 10, Sec 10.1-10.2
      • Week 13 (Mid-Semester Break)
        Mar 25-29 No Lectures
          No tutorials
        Week 14
        Apr 01 (Mon)
        Apr 02 (Tue) Lecture 30: Recurrences: Divide & Conquer and Linear
      • Slides
      • Additional reading: LLM-Notes, Chapter 10, Sec 10.3-10.5
      • Akra and Bazzi (1998) and Leighton (1996)
      • Apr 03 (Wed) Lecture 31: Recurrences (contd.) and Counting
      • Slides
      • Additional reading: LLM-Notes, Chapter 10, Sec 10.3-10.5 and LLM-Book, Chapter 15, Sec 15.8
      • The Pigeon Hole Principle: 7 gorgeous proofs
        Apr 04 (Thurs)

        Apr 05 (Fri) Lecture 32: Counting (Contd.)
      • Slides
      • Additional reading: LLM-Book, Chapter 15, Sec 15.1-15.9
      • Apr 06 (Sat)
        Monday timetable

          No tutorial
        Week 15
        Apr 08 (Mon)
        Apr 09 (Tue) Lecture 33: Counting (contd.), Combinatorial Proofs and Probability
      • Slides
      • Additional reading: LLM-Book, Chapter 15, Sec 15.10 and Chapter 17, Sec 17.1 and 17.2
      • Apr 10 (Wed) Lecture 34: To Infinity and Beyond
      • Slides
      • How An Infinite Hotel Ran Out Of Room
      • An "obvious" theorem about infinite sets
      • Additional reading: LLM-Book, Chapter 8
        • Apr 11 (Thurs)
          Eid-ul-Fitr

            No tutorial
          Apr 12 (Fri) Lecture 35: Quiz 4
        • Solutions
        • Apr 13 (Sat)
          Thursday timetable
            No tutorial
          Week 16
          Apr 15 (Mon)
          Apr 16 (Tue) Lecture 36: Probability (contd.)
        • Slides
        • Additional reading: LLM-Book, Chapter 17, Sec 17.1 and 17.2 and Chapter 18, Sec 18.1-18.4
        • Apr 17 (Wed)
          Ram Navami
          No lecture
          Apr 18 (Thurs)
          Apr 19 (Fri) Lecture 37: Conditional Probability and Paradoxes
        • Slides
        • Additional reading: LLM-Book, Chapter 18, Sec 18.4-18.6
        • Simpson's paradox in Covid-19 data
        • Apr 20 (Sat)
          Wednesday timetable
          Lecture 38: Independence
        • Slides
        • Additional reading: LLM-Book, Chapter 18, Sec 18.7-18.8
          • No tutorial
          Week 17
          Apr 22 (Mon)
          Apr 23 (Tue) Lecture 39: Birthday Paradox and Random Variables
        • Slides
        • Additional reading: LLM-Book, Chapter 17, Sec 17.4 and Chapter 19, Sec 19.1-19.3
        • Birthday paradox at play at the Football World Cup
        • Apr 24 (Wed) Lecture 40: Random Variables (contd.) and Probability Distributions
        • Slides
        • Additional reading: LLM-Book, Chapter 19, Sec 19.1-19.3
          Apr 25 (Thurs)
          Apr 26 (Fri)
          Monday timetable

            No tutorial
          Apr 27 (Sat)
          Tuesday timetable
          Last Teaching Day
          Lecture 41: Expectation and Wrap up
        • Slides
        • Additional reading: LLM-Book, Chapter 19, Sec 19.4-19.6

          • No tutorial
          Week 18 (Major Exams)
          May 03 (Fri) Major: 10:30AM-12:30PM, LH 114
        • Solutions
          May 04 (Sat) Make-Up Exam: 8-10AM, Bharti 425