Discrete Mathematics
R. Inkulu at cse.iitg in Fall 2016
Proofs

Introduction
[R]: parts of 139, 5867, 7380, 9099; [note]

Wellordered induction
[R]: 299300; [AZ]: 63

Principle of infinite descent
[wiki]

Mathematical induction
parts of [R]: 273315

Program correctness
[R]: 108114

Also see lectures on combinatorial arguments and generating functions.
Few more examples on Proofs  NS

Guarding an art gallery
[AZ]: 231233

Estimating pi
[AZ]: 155158; [wiki]

Irrational numbers
[B]: 308309, 323; [AZ]: 3538

List coloring planar graphs
[D]: 131132
Number Theory

Greatest common divisor
[B]: 17, 2024, 2930, 132133

Prime numbers
[B]: 3942, 4648, 239; [AZ]: 8

Bertrand's postulate
[AZ]: 79  AR

Modular arithmatic
[B]: 6367, 7172

Linear congruences
[B]: 3334, 7677, 7980

Primality testing
[B]: 8890, 91, 9395
Sets, Relations, Functions

Terminology (review)
[R]: 121149, 459466, 482483

Equivalence relations to classify elements of a set
[R]: 493497

Cardinality based set classification
[R]: 168174

Element relation based set classification
[R]: 503506

More on partially ordered sets
[R]: 506512, 515; [R]: 506512, 515; [more]

Special functions
[CLRS]: 54, 5859, 573574  AR

Asymptotic growth of functions
[R]: 195205; [CLRS]: 5052
Sequences and Series

Tests for convergence
[A1]: 394409  AR

Summations
[CLRS]: 5557, 11501156; [AZ]: 1011; [note]

Binomial coefficients
[R]: 362367, 380, 426428  AR

Setting up recurrence relations
[R]: 392398

Generating functions in finding k^{th} term
[R]: 424425, 428435; [note]

Linear recurrence relations with const coeff
[R]: 402411  AR

Master theorem
[CLRS]: 93103

Generating functions in proving identities
[R]: 436, 439 exer 43
Counting

Preliminaries
[R]: 335341, 354360, 369374

Cardinalities of some set families
[AZ]: 179181

The pigeonhole principle
[R]: 347351

The principle of inclusionexclusion
[R]: 444, 446451

Using generating functions
[R]: 428432

Occupancy problems
[R]: 369378

Combinatorial arguments
[AZ]: 164165; parts of [R]: 362367; [note]
Graph Theory

Introductory terminology
[note]

Related to vertex degrees
[R]: 537; [AZ]: 170, 175; [more]

Bipartite graphs
[R]: 541; [D]: 18

Trees
[R]: 630632; [D]: 14

Spanning trees
[note]

Connectivity
[D]: 810

Tours
[D]: 2223, 308

Vertex coloring
[D]: 122123; [more]

Euler's formula for planar graphs
[R]: 595604; [AZ]: 7980, 266267; [D]: 120121

Few extremal problems
[D]: 9; [AZ]: 124, 235236
* [R]: Discrete Mathematics and its Applications by Kenneth Rosen, Seventh (Indian) Edition.
* [B]: Elementary Number Theory by David Burton, Seventh Edition.
* [AZ]: Proofs from the Book by Aigner and Ziegler, Fourth Edition.
* [D]: Graph Theory by Reinhard Diestel, Fifth Edition.
* [CLRS]: Introduction to Algorithms by Cormen, Leiserson, Riverst, and Stein, Third Edition.
* [A1]: Calculus Vol 1 by Tom M. Apostol, Second Edition.
* Theoretical Computer Science Cheat Sheet
* Prereq denotes that this topic is typically taught in an earlier course.
* AR stands for additional reading (no lecture delivered but included in syllabus).
* EP stands for a problem of importance but it is given as part of an exam.
* NS says that it is not part of the syllabus although it was taught.
When this course had eight credits, i.e. four hours of teaching per week instead of three hours, following topics were also taught (in additional fourteen hours).
Discrete Probability

The sample space and events
[F]: 724, 33, 3536, 43, 98100, 101102, 106107

Conditional probability
[F]: 11412

Stochastic independence
[F]: 125128

Random variables
[F]: 212216, 217220

Expectation of a random variable
[F]: 220223; [MU]: 2224, 3233

Conditional expectation of a random variable
[MU]: 2630

Variance of a random variable
[F]: 227230

Popular distributions
[F]: parts of 146169, 4344, 223224, 228229; [MU]: 3031

Random walk on grid
[F]: 342349; [note]

Tail inequalities
[MU]: 4445, 4849, 6367

Intro to probabilistic method
[MU]: 126131; [AZ]: 267268
* [F]: An introduction to probability theory and its Applications vol 1 by Willam Feller, Third Edition.
* [MU]: Probability and computing by Mitzenmacher and Upfal, First Edition.
* Few examples are also taken from the text: A first course in probability theory by Sheldron Ross, Ninth Edition.