• Discrete Mathematics
• CS201 at IITG by R. Inkulu

---

• 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
  • On quantifiers      [R]: 49-58, 67-72, 74-75, 93-95
  • Invariance principle      [note]
  • Also, refer to combinatorial proofs.
• Number theory   --- covered for grad students
  • 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, 246-248
  • 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; [calkwilf]
  • 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
  • Sperner's, Erdos-Ko-Rado's      [wiki]: 1, 2
  • Using OGFs      [R]: 589-592, 596
  • A few special numbers      [note]
  • Combinatorial proofs      [R]: 507-514; [more]
  • Number of labeled spanning trees      [W]: 81-83
  • Pigeonhole principle      [R]: 488-494
  • Discrete probability      [note]   --- not covered this time
• Graph theory
  • Degree-sum formula      [R]: 719-721; [W]: 44; [wiki]: 1, 2, 3
  • Walks      [W]: 20-23, 71
  • Trees      [R]: 826-830, 833-836; [W]: 68-69, 72
  • Spanning trees      [R]: 870-872, 884; [W]: 25
  • Eulerian, Hamiltonian      [W]: 27-28, 288-289
  • Hall's, Konig's, Gallai's      [R]: 725-728; [W]: 112-115
  • Whitney's, Menger's      [W]: 152-153, 161-163, 167-168
  • Graph isomorphism      [R]: 741-744, 757-758
  • Planar graphs      [W]: 792-801; [pick's]; [szetro]
  • Vertex coloring      [R]: 723; [W]: 191-193, 257-258
  • With probabilistic method      [note]


• [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).

---