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
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.
This is a theoretical course that will require familiarity with high school (Standards 11 and 12) mathematics.
Reference texts
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 policyTutorials: 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 lateron 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.
| Date | Lectures | Tutorials | |
|---|---|---|---|
| Week 1 | |||
| Jan 01 (Mon) |
|
||
| Jan 02 (Tue) | Lecture 1: What is a Proof? |
|
|
| Jan 03 (Wed) | Lecture 2: Propositional Logic |
|
|
| Jan 04 (Thurs) |
|
||
| Jan 05 (Fri) | Lecture 3: Patterns of Proof |
|
|
| Week 2 | |||
| Jan 08 (Mon) | Last date for course drop |
|
|
| Jan 09 (Tue) | Lecture 4: Induction |
|
|
| Jan 10 (Wed) | Lecture 5: Induction and Invariant Last date for adding courses in lieu of dropped courses |
|
|
| Jan 11 (Thurs) | Finalization of roll lists |
|
|
| Jan 12 (Fri) | Lecture 6: Strong Induction |
|
|
| Week 3 | |||
| Jan 15 (Mon) |
|
||
| Jan 16 (Tue) | Lecture 7: Well Ordering Principle |
|
|
| Jan 17 (Wed) | Lecture 8: Quiz 1 |
|
|
| Jan 18 (Thurs) |
|
||
| Jan 19 (Fri) | Lecture 9: Number Theory I: GCD |
|
|
| Jan 20 (Sat) Friday timetable |
Lecture 10: Number Theory II: GCD Applications |
|
|
| Week 4 | |||
| Jan 22 (Mon) |
Moved to Jan 24 (Wed), 5PM, Bharti 501 |
||
| Jan 23 (Tue) | Lecture 11: Number Theory III: GCD Applications and Congruence |
|
|
| Jan 24 (Wed) | Lecture 12: Number Theory IV: Congruence and Euler's Function |
|
|
| Jan 25 (Thurs) |
|
||
| Jan 26 (Fri) Republic Day |
No lecture |
|
|
| Week 5 | |||
| Jan 29 (Mon) |
|
||
| Jan 30 (Tue) | Lecture 13: Number Theory V: Euler's Theorem |
|
|
| Jan 31 (Wed) | Lecture 14: Number Theory VI: Secret Sharing and Public Key Cryptography |
|
|
| Feb 01 (Thurs) |
|
||
| Feb 02 (Fri) | Lecture 15: Quiz 2 |
|
|
| Week 6 | |||
| Feb 05 (Mon) |
|
||
| Feb 06 (Tue) | Lecture 16: Graph Theory |
|
|
| Feb 07 (Wed) | Lecture 17: Graph Coloring and Matching |
|
|
| Feb 08 (Thurs) |
|
||
| Feb 09 (Fri) | Lecture 18: Perfect Matchings |
|
|
| Week 7 | |||
| Feb 12 (Mon) |
|
||
| Feb 13 (Tue) | Lecture 19: Matchings: Perfect and Stable |
|
|
| Feb 14 (Wed) | Lecture 20: Stable Matchings (Contd.) |
|
|
| Feb 15 (Thurs) |
|
||
| Feb 16 (Fri) | Lecture 21: Walks, Cycles, and Trees |
|
|
| Week 8 | |||
| Minor: Rescheduled to Week 9 |
|
||
| Week 9 (Mid-Term Exams) | |||
| Feb 28 (Wed) | Minor: LH 108 and LH 111, 8-10AM |
|
|
| Week 10 | |||
| Mar 04 (Mon) Friday timetable |
Lecture 22: Recap and Minimum Spanning Trees |
|
|
| Mar 05 (Tue) | Lecture 23: Minimum Spanning Trees (Contd.) |
|
|
| Mar 06 (Wed) | Lecture 24: Euler Tours |
|
|
| Mar 07 (Thurs) |
|
||
| Mar 08 (Fri) Maha Shivaratri |
No lecture |
|
|
| Week 11 | |||
| Mar 11 (Mon) |
|
||
| Mar 12 (Tue) Friday timetable |
No lecture |
|
|
| Mar 13 (Wed) | Lecture 25: Directed Graphs |
|
|
| Mar 14 (Thurs) |
|
||
| Mar 15 (Fri) | Lecture 26: Sums |
|
|
| Week 12 | |||
| Mar 18 (Mon) |
|
||
| Mar 19 (Tue) | Lecture 27: Sums and Asymptotics |
|
|
| Mar 20 (Wed) | Lecture 28: Quiz 3 |
|
|
| Mar 21 (Thurs) |
|
||
| Mar 22 (Fri) | Lecture 29: Recurrence |
|
|
| Week 13 (Mid-Semester Break) | |||
| Mar 25-29 | No Lectures |
|
|
| Week 14 | |||
| Apr 01 (Mon) |
|
||
| Apr 02 (Tue) | Lecture 30: Recurrences: Divide & Conquer and Linear |
|
|
| Apr 03 (Wed) | Lecture 31: Recurrences (contd.) and Counting |
|
|
| Apr 04 (Thurs) |
|
||
| Apr 05 (Fri) | Lecture 32: Counting (Contd.) |
|
|
| Apr 06 (Sat) Monday timetable |
|
||
| Week 15 | |||
| Apr 08 (Mon) |
|
||
| Apr 09 (Tue) | Lecture 33: Counting (contd.), Combinatorial Proofs and Probability |
|
|
| Apr 10 (Wed) | Lecture 34: To Infinity and Beyond |
|
|
| Apr 11 (Thurs) Eid-ul-Fitr |
|
||
| Apr 12 (Fri) | Lecture 35: Quiz 4 |
|
|
| Apr 13 (Sat) Thursday timetable |
|
||
| Week 16 | |||
| Apr 15 (Mon) |
|
||
| Apr 16 (Tue) | Lecture 36: Probability (contd.) |
|
|
| Apr 17 (Wed) Ram Navami |
No lecture |
|
|
| Apr 18 (Thurs) |
|
||
| Apr 19 (Fri) | Lecture 37: Conditional Probability and Paradoxes |
|
|
| Apr 20 (Sat) Wednesday timetable |
Lecture 38: Independence |
|
|
| Week 17 | |||
| Apr 22 (Mon) |
|
||
| Apr 23 (Tue) | Lecture 39: Birthday Paradox and Random Variables |
|
|
| Apr 24 (Wed) | Lecture 40: Random Variables (contd.) and Probability Distributions |
|
|
| Apr 25 (Thurs) |
|
||
| Apr 26 (Fri) Monday timetable |
|
||
| Apr 27 (Sat) Tuesday timetable Last Teaching Day |
Lecture 41: Expectation and Wrap up |
|
|
| Week 18 (Major Exams) | |||
| May 03 (Fri) | Major: Venue and Time (TBA) |
|
|
| May 04 (Sat) | Make-Up Exam for missed Minor and/or Major: Venue and Time (TBA) |
|
|