• 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
• 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]




• --- as the course progress, topics covered in lectures are listed here ---



---



• 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, primitive recursion, setting up recurrences, solving recurrences, generating functions, counting principles, combinatorial proofs, special numbers, pigeonhole principle, elementary discrete probability, 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)	3*(≥4)	15 minutes each; not scheduled beforehand
  homework	0	one/two problems posted after every lecture
  class participation	4	-

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

---