Study Guide
MCS-212 · Discrete Mathematics
Pass Strategy
40+ marksStudy Block 1 (Logic) + Block 4 (Graphs) basics only. From Q1: truth table + tautology + proof by contradiction = ~15 marks. From Q2–Q5: attempt 2 graph questions + 1 automata question = 30 marks. Total = ~45 marks.
40 marks
Target
45 marks
Estimated
~15 hours
Time needed
Units to study:
Propositions & Connectives, Truth Tables, Logical Equivalence, Tautology & Contradiction, CNF / DNF Normal Forms, Predicate Logic & Quantifiers, De Morgan's Laws
Direct Proof, Proof by Contradiction, Proof by Contrapositive, Mathematical Induction, Strong Induction
Graph Terminology, Degree of Vertex, Handshaking Theorem, Complete & Regular Graphs, Subgraphs, Isomorphism, Bipartite Graphs
Eulerian Graph & Circuit, Hamiltonian Graph, Dirac's Criterion, Ore's Criterion, Travelling Salesman Problem
Finite Automata (DFA/NFA), Regular Expressions, Kleene Closure, State Transition Diagrams, Moore & Mealy Machines
Distinction Strategy
72+ marksAdd Block 2 (Automata/Sets) + Block 3 (Counting) deeply. Know Floyd-Warshall + Vertex Colouring (trending last 3 papers). 20 Priority-1 answers memorized = 60+ marks minimum.
72 marks
Target
78 marks
Estimated
~40 hours
Time needed
High-return units:
Propositions & Connectives, Truth Tables, Logical Equivalence, Tautology & Contradiction, CNF / DNF Normal Forms, Predicate Logic & Quantifiers, De Morgan's Laws
Direct Proof, Proof by Contradiction, Proof by Contrapositive, Mathematical Induction, Strong Induction
Boolean Laws & Identities, Simplification, Logic Gates & Circuits, K-Map, De Morgan's Theorem
Set Types & Operations, Venn Diagrams, Symmetric Difference, Power Set, Relations & Properties, Equivalence Relations, Functions: Domain, Range, Composition, Inverse Functions
Finite Automata (DFA/NFA), Regular Expressions, Kleene Closure, State Transition Diagrams, Moore & Mealy Machines
Turing Machine, Halting Problem, Undecidable Problems, Turing Acceptable vs Decidable Language, P and NP Classes
Fundamental Counting Principle, Permutations, Combinations, Circular Permutations, Multinomial Theorem
Pigeonhole Principle, Generalized Pigeonhole, Inclusion-Exclusion Principle, Derangements, Surjective Functions
Order & Degree of Recurrence, Solving Recurrences, Fibonacci Numbers, Tower of Hanoi, Characteristic Equation
Graph Terminology, Degree of Vertex, Handshaking Theorem, Complete & Regular Graphs, Subgraphs, Isomorphism, Bipartite Graphs
Eulerian Graph & Circuit, Hamiltonian Graph, Dirac's Criterion, Ore's Criterion, Travelling Salesman Problem
Unit-by-Unit Topics
Unit 1 — Propositional Calculus
Must StudyPropositions & Connectives, Truth Tables, Logical Equivalence, Tautology & Contradiction, CNF / DNF Normal Forms, Predicate Logic & Quantifiers, De Morgan's Laws
Unit 2 — Methods of Proof
Must StudyDirect Proof, Proof by Contradiction, Proof by Contrapositive, Mathematical Induction, Strong Induction
Unit 3 — Boolean Algebra & Circuits
Must StudyBoolean Laws & Identities, Simplification, Logic Gates & Circuits, K-Map, De Morgan's Theorem
Unit 1 — Sets, Relations & Functions
Must StudySet Types & Operations, Venn Diagrams, Symmetric Difference, Power Set, Relations & Properties, Equivalence Relations, Functions: Domain, Range, Composition, Inverse Functions
Unit 2 — Automata & Languages
Must StudyFinite Automata (DFA/NFA), Regular Expressions, Kleene Closure, State Transition Diagrams, Moore & Mealy Machines
Unit 3 — Computability & Complexity
Must StudyTuring Machine, Halting Problem, Undecidable Problems, Turing Acceptable vs Decidable Language, P and NP Classes
Unit 1 — Combinatorics
Must StudyFundamental Counting Principle, Permutations, Combinations, Circular Permutations, Multinomial Theorem
Unit 2 — Advance Counting Principles
Must StudyPigeonhole Principle, Generalized Pigeonhole, Inclusion-Exclusion Principle, Derangements, Surjective Functions
Unit 3 — Recurrence Relations
Must StudyOrder & Degree of Recurrence, Solving Recurrences, Fibonacci Numbers, Tower of Hanoi, Characteristic Equation
Unit 4 — Partitions & Distributions
Stirling Numbers, Partitions of Sets, Distribution of Objects, Integer Solutions
Unit 1 — Basic Properties of Graphs
Must StudyGraph Terminology, Degree of Vertex, Handshaking Theorem, Complete & Regular Graphs, Subgraphs, Isomorphism, Bipartite Graphs
Unit 2 — Connectedness
Walk, Path, Circuit, Cycle, Connected Graphs, Spanning Trees, Floyd-Warshall Shortest Path, Tree and Forest
Unit 3 — Eulerian & Hamiltonian Graphs
Must StudyEulerian Graph & Circuit, Hamiltonian Graph, Dirac's Criterion, Ore's Criterion, Travelling Salesman Problem
Unit 4 — Graph Colourings
Vertex Colouring, Chromatic Number, Edge Colouring, Planar Graphs, Map Colouring