COL202 : Discrete Mathematics

Course Coordinator

Amit Kumar
Office : Room # 417, Bharti Building
Email : amitk@cse.iitd.ac.in
Phone : (ext) 1286.

Teaching Assistants

Jatin Batra, Chirag Agrawal, Ritesh Baldva, Mohammad Hafeezul Rahman

Announcements

Class Timings

Monday, Thursday: 9:30-10:50 am

Lecture Slides

Acknowledgement: Lecture slides by Prof. Lap Chi Lau (reproduced with his permission)
Lecture 1 Introduction
Lecture 2 Propositional Logic
Lecture 3 Predicate Logic
Lecture 4 Basic Proof Techniques
Lecture 5 Mathematical Induction, Quiz
Lecture 6 Strong induction, well-ordering principle, method of invariants
Lecture 7 More examples on invariants, introductions to sets, operations on sets
Lecture 8 Russell's paradox, Halting Problem, Quiz
Lecture 9 Countability, Pigeonhole principle
Lecture 10 Pigeonhole Principle, GCD
Lecture 11 GCD, Modular arithmetic
Lecture 12 Multipicative inverse, checksum, Quiz
Lectures 13,14,15,16 Fermat's Lemma, Chinese Remainder Theorem, Cryptography, Primality Testing
Lecture 17 Basic Counting Techniques, Quiz
Lecture 18 More Counting Techniques
Lecture 19 Counting by Inclusion Exclusion
Lecture 20 Counting by recurrence relations
Lecture 21 Generating Functions
Lecture 22 Fields, coding theory
Lecture 23 Coding theory, Berlekamp-Welch algortihm
Lectures 24-25 Graphs, Eulerian Graphs, Trees, Quiz

Tutorials

Monday, Tuesday, Thursday 1-2pm.
Week 1 : Aug 1,2, 4
Week 2 : Aug 8,10, 12
Week 3 : Aug 16,18, 22
Week 4 : for practice only
Week 5 : Sept 5,6,8
Week 6 : Sept 13, 15, 19
Week 7 : Sept 20, 22, 26
Week 8 : Sept 27, 29, Oct 3
Week 9 : Oct 4, 6
Week 10 Oct 17,18,20
Week 11 Nov 1, 3, 7
Week 12 Nov 8,10, 17
Week 13 (with solution hints for selected problem)

Topics

1. Introduction to Logic : Propositional logic, predicates, rules of inference
2. Basic proof techniques.
3. Group theory : application to number theory, Chinese Remainder Theorem, RSA.
4. Introduction to coding theory.
5. Counting Techniques : pigeonhole principle, inclusion-exclusion, recurrences, Polya's enumeration theorem.
6. Graph theory.

Books

Most of the topics covered can be found in the following book.

1."Discrete Mathematics and its applications", by Kenneth H Rosen.

Grading

20% : Quizzes
20% : Each minor exam
40% : Major exam