
COL202: Discrete Mathematics

Announcements  Minor 3 will be held on Nov 16 from 8:15 to 9:15am.
Office hours: 12pm on Nov 9,10,13 in room 409 (Bharti), 12pm 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, McGrawHill 
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, inclusionexclusion 
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 (12). 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

Pigeonhole 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.
