Semester 3Year 2 · OddCore Subject★★★ Moderate
MATH 201

Discrete Mathematics

Mathematical foundations for computer science including logic, sets, relations, and graph theory.

4Units
23Topics
4Credits
60hLecture hrs
100Max marks
Your Progress
0 / 23 topics
0% complete
Overview
🎯
Why it matters
Discrete Math is the mathematics of computer science. Cryptography uses number theory. Databases use set theory. Networks use graph theory. Compilers use logic. This IS the math you actually use in CS.
💼
Placement relevance
Directly tested in coding interviews: Graph problems, combinatorics (permutations/combinations), logic puzzles. Essential for cryptography roles. GATE CSE has ~8-10 marks from this subject.
🔗
Prerequisites for
Theory of Computation · Cryptography · Compiler Design · Graph Algorithms · Coding Theory · Database Theory
📚
Recommended books
Discrete Mathematics and Its Applications by Kenneth Rosen · Discrete Mathematics by Seymour Lipschutz · Discrete Mathematics for Computer Scientists by J.K. Truss
Curriculum — 4 Units
U1
Unit 1 · 6 Topics · 0% complete
Mathematical Logic
⚡ Key Formulae
Logical Equivalences:De Morgan: ¬(P∧Q) ≡ ¬P∨¬Q; ¬(P∨Q) ≡ ¬P∧¬Q
Implications:P→Q ≡ ¬P∨Q; Contrapositive: P→Q ≡ ¬Q→¬P
Propositional Logic
Logical Connectives
Truth Tables
Tautology & Contradiction
Logical Equivalence
Predicates & Quantifiers
U2
Unit 2 · 6 Topics · 0% complete
Set Theory & Relations
⚡ Key Formulae
Set Operations:|A∪B| = |A| + |B| - |A∩B|
Power Set:|P(A)| = 2^|A|
Relation Properties:Reflexive, Symmetric, Transitive, Antisymmetric
Set Operations
Venn Diagrams
Relations
Types of Relations
Functions
Equivalence Relations
U3
Unit 3 · 5 Topics · 0% complete
Combinatorics
⚡ Key Formulae
Permutations:P(n,r) = n!/(n-r)!
Combinations:C(n,r) = n!/[r!(n-r)!]
Binomial:(a+b)^n = Σ C(n,k) a^(n-k) b^k
Permutations
Combinations
Binomial Theorem
Pigeonhole Principle
Inclusion-Exclusion
U4
Unit 4 · 6 Topics · 0% complete
Graph Theory
⚡ Key Formulae
Handshaking Lemma:Σ deg(v) = 2|E|
Euler Path:Exists if exactly 0 or 2 vertices have odd degree
Tree Property:Tree with n vertices has n-1 edges
Graph Terminology
Types of Graphs
Graph Representation
Euler & Hamiltonian Paths
Trees
Graph Coloring
Previous Year Questions
Unit 42023 · End Semester8 marks
Determine if the graph G with 6 vertices and edges {(1,2),(1,3),(2,3),(2,4),(3,5),(4,5),(4,6),(5,6)} has an Euler path or Euler circuit. Justify your answer.
Unit 32022 · End Semester6 marks
How many 4-letter words can be formed from letters of 'COMPUTER' if: a) No letter repeats, b) Letters can repeat, c) Must start with vowel?
Exam Strategy
✅
Truth tables = easy marks
Logic questions: Always draw truth table even if question doesn't ask. Shows complete understanding. For 3 variables = 8 rows, systematic approach.
🎨
Venn diagrams help
Set theory problems become visual with Venn diagrams. Draw 2-3 circle diagrams, shade regions, count elements. Easier than algebraic approach.
🔢
Combinatorics: Permutation vs Combination
Order matters? → Permutation (P). Order doesn't matter? → Combination (C). Remember: nPr ≥ nCr. Practice word arrangement, selection problems.
Related Subjects
Semester 5
Theory of Computation
CS 503
Semester 3
Design and Analysis of Algorithms
CS 201