Office : Room # 417, Bharti Building

Email : amitk@cse.iitd.ac.in

Phone : (ext) 1286.

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 |

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) |

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.

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

20% : Each minor exam

40% : Major exam