-
Proofs
-
Propositions
[R]: 1-13, 30-42, 46-48, 81-86
-
A few proof techniques
[R]: 99-108
-
A few proof strategies
[R]: 111-123
-
Well-ordered induction
[R]: 427-428
-
Proof by infinite descent
[note]
-
Mathematical induction
[R]: 395-410, 419-426, 439-443
-
Also, refer to combinatorial proofs.
-
Number theory
-
Divisibility
[B]: 17, 20, 117-119
-
Greatest common divisor
[B]: 21-24, 26-27, 29, 30
-
Prime numbers
[B]: 39-42, 44-46, 48, 239
-
Modular arithmatic
[B]: 63-67, 71-72
-
Chinese remainder
[B]: 33-34, 76-77, 79-80
-
Fermat's, Wilson's
[B]: 88-91, 94
-
Relations
-
Equivalence classes
[R]: 626, 628-629, 665-672
-
Posets: topological order
[R]: 627-628, 677-685, 690-692
-
Posets: Dilworth's theorem
[note]
-
Closures of relations
[R]: 630-631, 654-659
-
Functions
-
Finite vs infinite sets
[R]: 186-192, 225-226
-
Countable vs uncountable sets
[R]: 226-235;
-
Ackermann's, lg*
[R]: 448 exer 50-54, 56, 63; [CLRS]: 574
-
Asymptotic growth
[R]: 270-282
-
Recurrences
-
Setting up
[R]: 211-214, 544-548
-
Guess and substitute
[CLRS]: 83-87, 88-92
-
Master method
[CLRS]: 93-96, 97-103
-
Characteristic roots
[R]: 557-568
-
Using OGFs
[R]: 583-588, 594-596
-
Counting
-
A few basic rules
[R]: 470-481
-
Permutations and combinations
[R]: 497-504, 516-522
-
Principle of inclusion-exclusion
[R]: 605-606, 608-613
-
Occupancy problems
[R]: 522-525
-
Using OGFs
[R]: 589-592, 596
-
A few special numbers
[note]
-
Combinatorial proofs
[R]: 507-514
-
Pigeonhole principle
[R]: 488-494
-
Graph theory
-
Degree-sum formula
[R]: 719-721; [W]: 44; [wiki]: 1, 2, 3
-
Walks
[R]: 749-757; [W]: 20-23, 71
-
Trees
[R]: 826-830; [W]: 68-69, 72
-
Spanning trees
[R]: 870-872, 884; [W]: 25
-
Tours
[R]: 764-775; [W]: 27-28, 288-289
-
Connectivity
[W]: 152-153, 161-163
-
Planar graphs
[W]: 792-797, 799-801;
-
Vertex coloring
[R]: 723; [W]: 191-193, 257-258
-
[R]: Discrete Mathematics and its Applications by Kenneth H. Rosen, Eighth (Indian) Edition.
-
[B]: Elementary Number Theory by David Burton, Seventh Edition.
-
[W]: Introduction to Graph Theory by Douglas B. West, Second Edition.
-
AR stands for additional reading (no lecture delivered but included in syllabus).