COL202: Discrete Mathematics

AnnouncementsMinor 3 will be held on Nov 16 from 8:15 to 9:15am.
Office hours: 1-2pm on Nov 9,10,13 in room 409 (Bharti), 1-2pm on Nov 16,17,18 in room 5xx (IMPECS Lab, Bharti)
Instructor Naveen Garg, 409 Bharti
Text Discrete Mathematics and its Applications, by Kenneth H. Rosen, McGraw-Hill
Reference Material DiscreteMathematics, Lecture Notes, Yale University, Spring 1999,L. Lov´asz and K. Vesztergombi
Mathematics for Computer Science, Lehman, Leighton & Meyer
Online resources complementing the book by Rosen
Course outline (tentative)
Topic Reading material
Introduction
Intro
Propositional logic, Predicate Calculus and Quantifiers, Proof Methods PropLogic, fologic, proofMethods
Induction and Invariant methods induction, invariants
Sets, functions, Cardinality, Infinity and Diagonalization, Pigeon hole principle sets, functions
Modular Arithmetic, Euclid's Algorithm, primes, Chinese Remainder, Public Key Cryptography  gcd, ModularArithmetic, ChineseRemainder, Cryptography
Basic Counting
basicCounting, moreCounting, Numberseq
Advanced Counting - formulating and solving recurrence relations, generating functions, inclusion-exclusion InclExcl, recurrences
Generatingfunctions
Polynomials, finite fields and Secret Sharing lecture notes, Slides
Coding Theory: Error correcting codes, Hamming codes, Hamming bound lecture notes
Relations  
Graph Theory - Eulerian, planar graphs, vertex coloring Graphs, Coloring
Matching Theory Matching
Tutorials Hours: Mon, Wed, Thu (1-2). All students should click here and specify the day they will be attending tutorials.

Month
Dates
Tutorial Sheet
Solutions
July
27, 29, 30
PropLogic

August
3, 5, 6
Predicates & Proof Methods
Solutions
10, 12, 13
Induction & Invariants
Solutions
17, 19, 20
Sets, functions, Cardinality
Solutions
24, 26, 27
Pigeon-hole Principle
Solutions
Sept
7,9,10
Modular arithmetic and gcd
Solutions
9, 10, 14


21, 23, 24
Congruences, Primes
Solutions
28, 30, 1
InclExcl, Counting
Solutions
Oct
5, 6, 7
Recurrence Relations
Solutions
12, 14, 15
Solving recurrences

26, 28, 29
Secret Sharing and Coding

Nov
4, 5,6
Graphs


Evaluation Lecture Quizzes (15, best 3 of 4), Tutorial Quizzes (5), Minors (3X15), Major (35). You can see your marks here (updated 1045, 27.11)
Attendance/missed tests Policy
The scores of your 4 best lecture quizzes would be counted towards the total. There is no further relaxation for falling ill, breaking limbs, attending family events etc. So please ensure that you do not miss more than 1 quiz.
If you miss a minor due to illness (medical certificate needed) then I will scale the marks you receive  in the other minor and major to award you marks in the missed minor. There is no reminor.