• Discrete Mathematics
• CS201 at IITG by R. Inkulu

---

• Elementary logic
  • Propositions      [R]: 1-12, 26-37, 73-78
  • Predicates      [R]: 40-46
  • Quantifiers      [R]: 47-51, 60-65, 67-68, 79-82
• Proofs
  • A few proof techniques      [R]: 84-93
  • A few proof strategies      [R]: 96-107
  • Well-ordered induction      [R]: 361-362
  • Proof by infinite descent      [note]
  • Mathematical induction      [R]: 331-346, 354-359, 372-376
  • Invariants      [note]; [R]: 393-397
  • Also, refer to combinatorial proofs.
• Relations
  • Closures of relations      [R]: 607-608, 628-633
  • Equivalence relations      [R]: 639-646
  • Partial orderings      [R]: 604-605, 650-658
  • Topological sorting      [R]: 659-661
  • Dilworth's decomposition      [note]
• Functions
  • Finite vs infinite sets      [R]: 147-156; [note]
  • Countable vs uncountable sets      [R]: 180-184
  • Asymptotic growth      [R]: 216-228
  • Acker, invAcker, logstar      [CLRS]: 573-574; [pr]
• Recurrences
  • Setting up      [R]: 527-533
  • Guess and substitute      [CLRS]: 83-87, 88-92
  • Master theorem      [CLRS]: 93-96, 97-103
  • Characteristic roots      [R]: 540-550
  • Using OGFs      [R]: 572-575, 577 exer 44
  • Fibonacci, Catalan, Harmonic      [note]
• Counting
  • A few basic rules      [R]: 406, 409, 413
  • Combinations      [R]: 429-432, 446-448, 450-451
  • Inclusion-exclusion      [R]: 583, 585-591
  • Occupany problems      [R]: 451-454
  • Double counting      [R]: 433-434, 440-443
  • Bijective proofs      [note]
  • Sperner's theorem      [note]: 3
  • Using OGFs      [R]: 569-572
  • Pigeonhole principle      [R]: 420-426
• Graph theory
  • Introduction      [note]
  • Handshaking lemma      [R]: 686-688; [W]: 44
  • Sperner's, Mantel's, Turan's      [W]: 388-389, 41-42; [wiki]
  • Walks      [W]: 20-22, 24, 71
  • Trees, spanning trees      [W]: 68-69, 72
  • Cayley's formula      [W]: 81-83
  • Bipartite graphs      [W]: 25
  • Isomorphic graphs      [W]: 7-10
  • Berge's, Hall's      [W]: 108-111
  • Konig's, Gallai's, DS      [W]: 111-116
  • Eulerian, Ham-cycles      [W]: 27-28, 288-289
  • Connectivity: Whitney's      [W]: 152-153, 161-162
  • Connectivity: Menger's      [W]: 167-168
  • Planar graphs      [R]: 753-758
  • Vertex coloring      [W]: 191-194, 257-258



---



• This is a core course for second-year undergrads. It introduces basic discrete mathematical structures commonly used across all subareas of computer science while emphasizing proofs. The significant topics covered include the following -
  
  Elementary logic, proof techniques, transitive closure, equivalence relations, partially ordered sets, (in)finite sets, (un)countable sets, special functions, asymptotic growth of functions, setting up recurrences, solving recurrences, generating functions, counting principles, combinatorial proofs, special numbers, pigeonhole principle, and introductory graph theory.
  
  All through, these are all motivated by famous problems and theorems.



• Texts:
• Discrete Mathematics and its Applications by Kenneth H. Rosen, Eighth Edition.   [R]
• Introduction to Graph Theory by Douglas B. West, Second Edition.   [W]
• [Additional resources are provided where necessary.]


• Prereqs: High school math, CS101.


• Lectures are held in 5104 in Slot A: Tue 9-9:55 am, Wed 10-10:55 am, Th 11-11:5510-10:55 am.
  
• The academic calendar is here.


• Teaching Assistants: aditis1001@, h.simhadri@, j.architha@.
• The set of guidelines for TAs is here.


• The grading is relative, and it is based on the total marks obtained in the following:
  
  

  exam1	14 points	10 am to 11:40 am on 16th Aug (Sat) in 5G4 & 5205
  mid-sem	18	2 hours; refer to institute time table
  exam3	15	10 am to 11:40 am on 18th Oct (Sat) in 5G4 & 5205
  end-sem	25	3 hours; refer to institute time table
  surprise (4 to 6)	4*(≥4)	20 minutes each; not scheduled beforehand
  homework	0	one/two problems posted after every lecture
  class participation	4	-

• The headcount at each lecture, out of 125 registrants, is here.

---