R. Inkulu at cse.iitg
Few more examples on Proofs --- NS
[R]: parts of 1-39, 58-67, 73-80, 90-99; [note]
[R]: 299-300; [AZ]: 63
Principle of infinite descent
parts of [R]: 273-315
Also see lectures on combinatorial arguments and generating functions.
Guarding an art gallery
[AZ]: 155-158; [wiki]
[B]: 308-309, 323; [AZ]: 35-38
List coloring planar graphs
Sets, Relations, Functions
Greatest common divisor
[B]: 17, 20-24, 29-30, 132-133
[B]: 39-42, 46-48, 239; [AZ]: 8
[B]: 63-67, 71-72
[B]: 33-34, 76-77, 79-80
[B]: 88-90, 91, 93-95
Sequences and Series
[R]: 121-149, 459-466, 482-483
Equivalence relations to classify elements of a set
Cardinality based set classification
Element relation based set classification
More on partially ordered sets
[R]: 506-512, 515; [R]: 506-512, 515; [more]
[CLRS]: 54, 58-59, 573-574 --- AR
Asymptotic growth of functions
[R]: 195-205; [CLRS]: 50-52
Tests for convergence
[A1]: 394-409 --- AR
[CLRS]: 55-57, 1150-1156; [AZ]: 10-11; [note]
[R]: 362-367, 380, 426-428 --- AR
Setting up recurrence relations
Generating functions in finding kth term
[R]: 424-425, 428-435; [note]
Linear recurrence relations with const coeff
[R]: 402-411 --- AR
Generating functions in proving identities
[R]: 436, 439 exer 43
[R]: 335-341, 354-360, 369-374
Cardinalities of some set families
The pigeonhole principle
The principle of inclusion-exclusion
[R]: 444, 446-451
Using generating functions
[AZ]: 164-165; parts of [R]: 362-367; [note]
Related to vertex degrees
[R]: 537; [AZ]: 170, 175; [more]
[R]: 541; [D]: 18
[R]: 630-632; [D]: 14
[D]: 22-23, 308
[D]: 122-123; [more]
Euler's formula for planar graphs
[R]: 595-604; [AZ]: 79-80, 266-267; [D]: 120-121
Few extremal problems
[D]: 9; [AZ]: 124, 235-236
* [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).
The sample space and events
[F]: 7-24, 33, 35-36, 43, 98-100, 101-102, 106-107
[F]: 212-216, 217-220
Expectation of a random variable
[F]: 220-223; [MU]: 22-24, 32-33
Conditional expectation of a random variable
Variance of a random variable
[F]: parts of 146-169, 43-44, 223-224, 228-229; [MU]: 30-31
Random walk on grid
[F]: 342-349; [note]
[MU]: 44-45, 48-49, 63-67
* [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.