COL202, Spring Semester 2023
Discrete Mathematical Structures
Instructor: Rohit Vaish ()
Teaching Assistants:
Lakshay Saggi (),
Kanav Pruthi ()
Aniket Mishra (),
Rajdeep Dhingra ()
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 at LH 316.
Tutorials: M/T/Th/F 1-2PM at LH 613 (Tutorial Groups).
Sign up on the Microsoft Teams channel of the course for announcements. Evaluation policyTutorials: 16% (best eight x 2%)
Quizzes: 14% (best two x 7%)
Minor 1: 20%
Minor 2: 20%
Major: 30%
For audit pass, all three of the following conditions should be met:
- At least 75% attendance
- Overall score at least 40/100
- Score in Minors+Major at least 25/70
| Date | Lectures | Tutorials | |
|---|---|---|---|
| Week 1 | |||
| Jan 03 (Tue) | Lecture 1: What is a Proof? |
|
|
| Jan 04 (Wed) | Lecture 2: Propositional Logic |
|
|
| Jan 05 (Thurs) |
|
||
| Jan 06 (Fri) | Lecture 3: Patterns of Proof |
|
|
| Week 2 | |||
| Jan 09 (Mon) | Last date for course add-drop |
|
|
| Jan 10 (Tue) | Lecture 4: Induction |
|
|
| Jan 11 (Wed) | Lecture 5: Induction and Invariant Finalization of roll lists |
|
|
| Jan 12 (Thurs) |
|
||
| Jan 13 (Fri) | Lecture 6: Strong Induction |
|
|
| Week 3 | |||
| Jan 16 (Mon) |
|
||
| Jan 17 (Tue) | Lecture 7: Quiz 1 |
|
|
| Jan 18 (Wed) | Lecture 8: Well Ordering Principle |
|
|
| Jan 19 (Thurs) |
|
||
| Jan 20 (Fri) | Lecture 9: Number Theory I: GCD |
|
|
| Week 4 | |||
| Jan 23 (Mon) |
|
||
| Jan 24 (Tue) | Lecture 10: Number Theory II: GCD Applications |
|
|
| Jan 25 (Wed) | Lecture 11: Number Theory III: GCD Applications and Congruence |
|
|
| Jan 26 (Thurs) Republic Day |
|
||
| Jan 27 (Fri) | Lecture 12: Number Theory IV: Congruence and Euler's Function |
|
|
| Jan 28 (Sat) Thursday timetable |
|
||
| Week 5 | |||
| Jan 30 (Mon) |
|
||
| Jan 31 (Tue) | Lecture 13: Number Theory V: Euler's Theorem |
|
|
| Feb 01 (Wed) | Lecture 14: Number Theory VI: Secret Sharing and Public Key Cryptography |
|
|
| Feb 02 (Thurs) |
|
||
| Feb 03 (Fri) | Lecture 15: Office hour (Bharti 425) |
|
|
| Week 6 (Minor Test 1) | |||
| Feb 06 (Mon) |
|
||
| Feb 07 (Tue) | Minor 1: 1-2PM, LH 308 and LH 310 |
|
|
| Feb 08 (Wed) | No Lecture |
|
|
| Feb 09 (Thurs) |
|
||
| Feb 10 (Fri) | Lecture 16: Minor-1 Discussion and Graph Theory |
|
|
| Week 7 | |||
| Feb 13 (Mon) |
|
||
| Feb 14 (Tue) | Lecture 17: Graph Coloring and Matching |
|
|
| Feb 15 (Wed) | Lecture 18: Matchings: Perfect and Stable |
|
|
| Feb 16 (Thurs) |
|
||
| Feb 17 (Fri) | Lecture 19: Stable Matchings (Contd.) |
|
|
| Week 8 | |||
| Feb 20 (Mon) |
|
||
| Feb 21 (Tue) | Lecture 20: Stable Matchings (Contd., Again) |
|
|
| Feb 22 (Wed) | Lecture 21: Walks, Cycles, and Trees |
|
|
| Feb 23 (Thurs) |
|
||
| Feb 24 (Fri) | No Lecture Mid-Term Project Evaluation |
|
|
| Week 9 | |||
| Feb 27 (Mon) |
|
||
| Feb 28 (Tue) | Lecture 22: Quiz 2 |
|
|
| Mar 01 (Wed) | Lecture 23: Quiz 2 Discussion and Minimum Spanning Trees |
|
|
| Mar 02 (Thurs) |
|
||
| Mar 03 (Fri) | Lecture 24: Minimum Spanning Trees (Contd.) |
|
|
| Week 10 (Mid-Semester Break) | |||
| Mar 06-10 | No Lectures |
|
|
| Week 11 | |||
| Mar 13 (Mon) |
|
||
| Mar 14 (Tue) | No Lecture |
|
|
| Mar 15 (Wed) | Lecture 25: Euler Tours |
|
|
| Mar 16 (Thurs) |
|
||
| Mar 17 (Fri) | Lecture 26: Directed Graphs |
|
|
| Week 12 (Minor Test 2) | |||
| Mar 20 (Mon) |
|
||
| Mar 21 (Tue) | Lecture 27: Sums |
|
|
| Mar 22 (Wed) | Lecture 28: Sums and Asymptotics |
|
|
| Mar 23 (Thurs) |
|
||
| Mar 24 (Fri) | Minor 2: 1-2PM, LH 308 and LH 310 |
|
|
| Week 13 | |||
| Mar 27 (Mon) |
|
||
| Mar 28 (Tue) | Lecture 29: Minor-II Discussion and Recurrence |
|
|
| Mar 29 (Wed) Thursday timetable |
No Lecture |
|
|
| Mar 30 (Thurs) Ram Navami |
No Lecture |
|
|
| Mar 31 (Fri) | Lecture 30: Recurrence (contd.) |
|
|
| Apr 01 (Sat) Friday timetable |
Lecture 31: Linear Recurrences and Counting |
|
|
| Week 14 | |||
| Apr 03 (Mon) |
|
||
| Apr 04 (Tue) Mahavir Jayanti |
No Lecture |
|
|
| Apr 05 (Wed) | Lecture 32: Counting (Contd.) |
|
|
| Apr 06 (Thurs) |
|
||
| Apr 07 (Fri) Good Friday |
No lecture |
|
|
| Week 15 | |||
| Apr 10 (Mon) |
|
||
| Apr 11 (Tue) | Lecture 33: Combinatorial Proofs (and Probability) |
|
|
| Apr 12 (Wed) | Lecture 34: Quiz 3 |
|
|
| Apr 13 (Thurs) |
|
||
| Apr 14 (Fri) Vaisakhi |
No lecture |
|
|
| Week 16 | |||
| Apr 17 (Mon) |
|
||
| Apr 18 (Tue) | Lecture 35: Quiz 3 Discussion and Probability (contd.) |
|
|
| Apr 19 (Wed) | Lecture 36: Conditional Probability and Paradoxes |
|
|
| Apr 20 (Thurs) |
|
||
| Apr 21 (Fri) | Lecture 37: Independence |
|
|
| Week 17 | |||
| Apr 24 (Mon) |
|
||
| Apr 25 (Tue) | Lecture 38: Birthday Paradox and Random Variables |
|
|
| Apr 26 (Wed) | Lecture 39: Random Variables (contd.) and Probability Distributions |
|
|
| Apr 27 (Thurs) |
|
||
| Apr 28 (Fri) | Lecture 40: Expectation |
|
|
| Apr 29 (Sat) Friday timetable |
Lecture 41: Expectation (contd.) and Wrap-Up Last day of classes |
|
|
| Weeks 18 and 19 (Major Test) | |||
| May 04 (Thurs) | Major: 11AM-1PM, LH 308 and LH 310 |
|
|