|
COL202: Discrete Mathematics
|
| Announcements | Minor 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.
|