MCA-101 Discrete Structures Notes from Unnati Educations cover all 4 units of the GGSIPU MCA Semester 1 paper in 87 pages, with 86 solved examples, 48 short-answer questions with answers and 36 long practice questions. They follow the MCA syllabus in force from academic session 2025-26 onwards, for the batch admitted in 2025-26 and later.
Written by Prateek Talwar, Founder, Unnati Educations · Reviewed by Ritik Rawat, B.Tech, Senior Full Stack Developer · Checked against the GGSIPU MCA Scheme of Examination and Detailed Syllabus (approved by BoS of USIC&T, 28 Jul 2025) · Updated 14 October 2026 · Editorial policy
Scheme: MCA (2 years), A.S. 2025-26 onwards | Applies to: batch admitted 2025-26 onwards | Verified against: MCA Scheme of Examination and Detailed Syllabus, BoS 28 Jul 2025, AC Sub Committee 01 Aug 2025
MCA-101 Discrete Structures at a glance: GGSIPU MCA Sem 1 credits, units and exam pattern
MCA-101 is the only Semester 1 theory paper with a tutorial hour, hence 4 credits. It sits with the other GGSIPU MCA Semester 1 papers in the first-year scheme.
| Code and title | MCA-101 Discrete Structures |
|---|---|
| Course and semester | MCA (2 years), First Semester |
| Category and credits | Core theory paper · L 3, T 1 · 4 credits |
| Marks | 100 in total; end-term paper 60. The internal figure is not printed separately (100 − 60 = 40). |
| Applies to | Batch admitted 2025-26 onwards |
| End-term pattern | Q1 compulsory short answers (12) + one question per unit (4 × 12) = 60 marks |
| Units and teaching hours | 4 units: 11, 12, 11 and 10 hours (44 in total) |
| Paired lab | None |
The official PDF prints no unit titles, so unit names here are our notes' titles.
MCA-101 Discrete Structures Notes unit-wise: 86 solved examples and 48 short answers across 4 units
These GGSIPU MCA Sem 1 Discrete Structures notes follow the official topic order, each unit ending with an exam corner and revision table. One page per unit is in the sample PDF above. Notes for the other MCA papers are listed under GGSIPU MCA notes.
MCA-101 Unit 1: Sets, Relations, Functions, Combinatorics and Recurrences
Unit I (pages 5-26) proves set identities by the element method and applies inclusion-exclusion to divisibility and survey counts. Relations follow (Hasse diagrams, Warshall closures), then function types, permutations, combinations with repetition, the pigeonhole principle and first-order recurrences.
Count: 24 solved examples, 5 figures, 12 short answers, 9 long questions.
| Property | Rule | Matrix test |
|---|---|---|
| Reflexive | (a, a) in R for every a | Every diagonal entry is 1 |
| Symmetric | aRb gives bRa | M equals its transpose |
| Antisymmetric | aRb and bRa only when a = b | mij = 1 with i ≠ j forces mji = 0 |
| Transitive | aRb and bRc give aRc | Boolean product M ⊙ M ≤ M |
Quick look: testing a relation from its matrix (from page 12)
- Property
- Reflexive
- Rule
- (a, a) in R for every a
- Matrix test
- Every diagonal entry is 1
- Property
- Symmetric
- Rule
- aRb gives bRa
- Matrix test
- M equals its transpose
- Property
- Antisymmetric
- Rule
- aRb and bRa only when a = b
- Matrix test
- mij = 1 with i ≠ j forces mji = 0
- Property
- Transitive
- Rule
- aRb and bRc give aRc
- Matrix test
- Boolean product M ⊙ M ≤ M
MCA-101 Unit 2: Formal Logic, Methods of Proof, Lattices and Boolean Algebra
Unit II (pages 27-48) builds propositional logic up to PDNF/PCNF, then six proof methods ending in complete induction. Lattices follow (bounded, distributive, complemented, isomorphic), and the unit ends with Boolean functions minimised on 3- and 4-variable K-maps, don't-care cells included.
Count: 32 solved examples (the most of any unit), 4 figures, 12 short answers, 9 long questions.
| Rule | Premises | Conclusion |
|---|---|---|
| Modus Ponens | p, p → q | q |
| Modus Tollens | ¬q, p → q | ¬p |
| Hypothetical Syllogism | p → q, q → r | p → r |
| Disjunctive Syllogism | p ∨ q, ¬p | q |
Quick look: four rules of inference (from page 32)
- Rule
- Modus Ponens
- Premises
- p, p → q
- Conclusion
- q
- Rule
- Modus Tollens
- Premises
- ¬q, p → q
- Conclusion
- ¬p
- Rule
- Hypothetical Syllogism
- Premises
- p → q, q → r
- Conclusion
- p → r
- Rule
- Disjunctive Syllogism
- Premises
- p ∨ q, ¬p
- Conclusion
- q
MCA-101 Unit 3: Number Theory and Group Theory
Unit III (pages 49-68) covers primes, gcd by the Euclidean algorithm, unique factorisation, Euler's phi function and Fermat's Little Theorem, plus check digits and toy RSA. Group theory runs from the symmetries of a triangle and a square to cosets, Lagrange's theorem, quotient groups, homomorphisms and permutation parity.
Count: 22 solved examples, 2 figures, 12 short answers, 9 long questions.
| Code | Weighted-sum rule | Worked check digit |
|---|---|---|
| ISBN-10 | Σ i·xi ≡ 0 (mod 11); "X" stands for 10 | 0-07-288008: sum 189, so x10 = 2 |
| UPC-A | 3 × (odd positions) + (even positions) ≡ 0 (mod 10) | 79357343104: 78 + 20 = 98, so x12 = 2 |
Quick look: check-digit rules (from page 55)
- Code
- ISBN-10
- Weighted-sum rule
- Σ i·xi ≡ 0 (mod 11); "X" stands for 10
- Worked check digit
- 0-07-288008: sum 189, so x10 = 2
- Code
- UPC-A
- Weighted-sum rule
- 3 × (odd positions) + (even positions) ≡ 0 (mod 10)
- Worked check digit
- 79357343104: 78 + 20 = 98, so x12 = 2
MCA-101 Unit 4: Graph Theory
Unit IV (pages 69-87) runs from the handshaking theorem, isomorphism and Dijkstra's shortest path to Euler graphs with Fleury's algorithm, Hamiltonian graphs, planarity, chromatic polynomials, Welch-Powell and a full Five Colour Theorem proof.
Count: 8 solved examples, 9 figures (the most of any unit), 12 short answers, 9 long questions.
| Graph | χ(G) |
|---|---|
| Complete graph Kn | n |
| Bipartite with an edge (trees, even cycles) | 2 |
| Odd cycle C2k+1 | 3 |
| Wheel Wn | 3 if n is even, 4 if n is odd |
Quick look: chromatic numbers (from page 81)
- Graph
- Complete graph Kn
- χ(G)
- n
- Graph
- Bipartite with an edge (trees, even cycles)
- χ(G)
- 2
- Graph
- Odd cycle C2k+1
- χ(G)
- 3
- Graph
- Wheel Wn
- χ(G)
- 3 if n is even, 4 if n is odd
Linear congruences and the Chinese Remainder Theorem in number theory: excerpt from page 53 of the MCA-101 notes
Excerpt from page 53 (Unit III), rewritten for the web
When does ax ≡ b (mod m) have a solution?
Let d = gcd(a, m). The congruence ax ≡ b (mod m) can be solved only when d divides b, and when it can, it has exactly d solutions that are different modulo m. Divide through by d to get (a/d)x ≡ b/d (mod m/d), solve it for x0, and the answers modulo m are x0, x0 + m/d, ..., x0 + (d − 1)m/d.
Three quick cases
First, 3x ≡ 4 (mod 7). Here gcd(3, 7) = 1, so there is one solution. The inverse of 3 modulo 7 is 5, because 3 × 5 = 15 ≡ 1. Multiply: x ≡ 5 × 4 = 20 ≡ 6 (mod 7). Check: 18 ≡ 4.
Second, 6x ≡ 9 (mod 15). Now d = gcd(6, 15) = 3, and 3 divides 9, so there are 3 solutions. Dividing by 3 gives 2x ≡ 3 (mod 5). The inverse of 2 modulo 5 is 3, so x ≡ 9 ≡ 4 (mod 5). Modulo 15 the answers are 4, 9 and 14; for 14, 6 × 14 = 84 = 5 × 15 + 9.
Third, the inverse of 17 modulo 43. Run the Euclidean algorithm (43 = 2 × 17 + 9, 17 = 1 × 9 + 8, 9 = 1 × 8 + 1) and substitute back to get 1 = 2 × 43 − 5 × 17. So −5 × 17 ≡ 1, and the inverse is −5 ≡ 38 (mod 43). Check: 17 × 38 = 646 = 15 × 43 + 1.
The Chinese Remainder Theorem
If the moduli m1, m2, ..., mn are pairwise relatively prime, the system x ≡ ak (mod mk) has one solution modulo M = m1m2...mn. It is x ≡ Σ akMkyk (mod M), where Mk = M/mk and yk is the inverse of Mk modulo mk.
Sun Tzu's puzzle
Solve x ≡ 2 (mod 3), x ≡ 3 (mod 5), x ≡ 2 (mod 7). The moduli are pairwise coprime and M = 105. M1 = 35 ≡ 2 (mod 3), so y1 = 2. M2 = 21 ≡ 1 (mod 5), so y2 = 1. M3 = 15 ≡ 1 (mod 7), so y3 = 1. Then x ≡ 2·35·2 + 3·21·1 + 2·15·1 = 140 + 63 + 30 = 233 ≡ 23 (mod 105). Every solution has the form 23 + 105k.
Do the MCA-101 notes cover the full GGSIPU syllabus?
Yes. Every official MCA-101 topic has its own section in the notes; no gaps. Extras such as Warshall's and Dijkstra's algorithms are added.
| Official unit | Official topics | Where in the notes | Status |
|---|---|---|---|
| Unit I | Set theory concepts; combinatorics; first-order linear recurrences | Parts A-C, pp. 6-18; D, pp. 18-20; E, pp. 21-22 | Covered |
| Unit II | Formal logic; methods of proofs; lattices; Boolean algebra and K-map | Part A, pp. 28-33; B, pp. 34-37; C, pp. 37-41; D, pp. 41-45 | Covered |
| Unit III | Number theory, with applications of congruences (ISBN, UPC, cryptography); group theory | Parts A-C, pp. 50-56; D-E, pp. 57-64 | Covered |
| Unit IV | Graph theory, from types of graphs to the Five Colour Theorem (with proof) | Parts A-E, pp. 70-84 | Covered |
MCA-101 official units mapped to the Unnati notes (2025-26 scheme)
- Official unit
- Unit I
- Official topics
- Set theory concepts; combinatorics; first-order linear recurrences
- Where in the notes
- Parts A-C, pp. 6-18; D, pp. 18-20; E, pp. 21-22
- Status
- Covered
- Official unit
- Unit II
- Official topics
- Formal logic; methods of proofs; lattices; Boolean algebra and K-map
- Where in the notes
- Part A, pp. 28-33; B, pp. 34-37; C, pp. 37-41; D, pp. 41-45
- Status
- Covered
- Official unit
- Unit III
- Official topics
- Number theory, with applications of congruences (ISBN, UPC, cryptography); group theory
- Where in the notes
- Parts A-C, pp. 50-56; D-E, pp. 57-64
- Status
- Covered
- Official unit
- Unit IV
- Official topics
- Graph theory, from types of graphs to the Five Colour Theorem (with proof)
- Where in the notes
- Parts A-E, pp. 70-84
- Status
- Covered
Official source: GGSIPU MCA Scheme of Examination and Detailed Syllabus, A.S. 2025-26 onwards (approved by BoS of USIC&T, 28 July 2025).
Every course in GGSIPU notes is mapped to its official PDF the same way.
How to write MCA-101 answers: counting numericals, formal proofs and step-marked twelve-mark solutions
Each MCA-101 unit question carries 12 marks with possible subparts, so marks follow visible steps.
- Name your sets or symbols first. In an inclusion-exclusion numerical, write "Let A = integers divisible by 2" and list every term before adding; the term list earns step marks even if the arithmetic slips. In a logic argument, give each statement a letter (p: it is sunny) and number every line with the rule used, such as Modus Tollens (2, 3).
- Check the closed form. Test a recurrence's closed form against a1 computed straight from the recurrence; it catches most sign errors.
- State the proof method. In a proof question, state the method in the first line ("by induction on n", "by contradiction") and end with a clear conclusion; for √3 or De Morgan's law, the notes model this layout step by step.
- Draw. A Hasse diagram, a K-map with circled groups or the pentagon of neighbours in the Five Colour proof earns marks of its own.
Worked example: verify before you write the answer box (page 23)
Solve an = 2an−1 + 2n, a0 = 1. Since f(n) = 2n uses the same base as the homogeneous part, try P·n·2n, which gives P = 1. The general solution is A·2n + n·2n, and a0 = 1 gives A = 1, so an = (n + 1)2n. Check: the recurrence gives a1 = 2·1 + 2 = 4, and the formula gives (1 + 1)·2 = 4. Write that check line in the answer.
Practise on GGSIPU MCA important questions after each unit.
MCA-101 exam corner: 48 short-answer solved questions and 36 long questions by unit
Each unit ends with 12 short-answer questions in the style of the compulsory Q1, all answered, and 9 long practice questions.
| Unit | Short answers (with answers) | Long questions (practice) | Solved examples |
|---|---|---|---|
| Unit I | 12 | 9 | 24 |
| Unit II | 12 | 9 | 32 |
| Unit III | 12 | 9 | 22 |
| Unit IV | 12 | 9 | 8 |
| Total | 48 | 36 | 86 |
MCA-101 exam corner by unit
- Unit
- Unit I
- Short answers (with answers)
- 12
- Long questions (practice)
- 9
- Solved examples
- 24
- Unit
- Unit II
- Short answers (with answers)
- 12
- Long questions (practice)
- 9
- Solved examples
- 32
- Unit
- Unit III
- Short answers (with answers)
- 12
- Long questions (practice)
- 9
- Solved examples
- 22
- Unit
- Unit IV
- Short answers (with answers)
- 12
- Long questions (practice)
- 9
- Solved examples
- 8
- Unit
- Total
- Short answers (with answers)
- 48
- Long questions (practice)
- 36
- Solved examples
- 86
One exam-style question per unit:
- Unit I: Find the number of non-negative integer solutions of x + y + z = 7. Pointer: C(7 + 3 − 1, 2) = 36.
- Unit II: Simplify x + x′y. Pointer: distribute to (x + x′)(x + y) = x + y.
- Unit III: Find φ(60). Pointer: 60 = 22·3·5, so φ = 60·(1/2)(2/3)(4/5) = 16.
- Unit IV: Why is K5 non-planar? Pointer: planar needs e ≤ 3v − 6 = 9; K5 has 10 edges.
The MCA-101 notes answer 48 short questions and list 36 long ones across 4 units, plus 86 worked examples.
More practice sits in the MCA-101 important questions.
Who writes and checks the MCA-101 Discrete Structures notes?
- Prateek Talwar (author, plans and edits the notes): Founder, Unnati Educations; Associate Company Secretary (ACS), ICSI, membership no. 58704, since 15 May 2019; B.Com, University of Delhi (School of Open Learning), 2012. Author bio
- Ritik Rawat (subject reviewer, checks definitions, proofs and worked numericals): Senior Full Stack Developer, Unnati Educations · B.Tech
For the 2026-27 edition, all four units were mapped against the MCA scheme approved by the USIC&T Board of Studies on 28 July 2025. These Discrete Structures notes in English were last updated on 14 October 2026.
Anyone looking for MCA-101 Discrete Structures IPU notes mostly wants K-map and group-theory numericals, so those carry the most worked steps. See our editorial policy.
The same team prepares GGSIPU important questions for every course it covers.
MCA-101 and the GGSIPU MCA Sem 1 papers it connects to
MCA-101 has no paired lab; its fourth credit comes from a weekly tutorial hour, and every paper in the semester is listed in the GGSIPU MCA syllabus.
- Unit I set operations, Cartesian products and relations → MCA-107 Database Management Systems, whose relational algebra uses union, intersection and minus on tables.
- Unit II logic and normal forms → tuple and domain relational calculus in MCA-107.
- Unit IV weighted graphs and Dijkstra's shortest path → the routing algorithms of MCA-103 Computer Networks.
- Unit IV cycles → resource allocation graphs for deadlock in MCA-105 Operating Systems with Linux.
Also in Semester 1: MCA-109 Object Oriented Programming and JAVA, labs MCA-161 to MCA-167, MCA-169 Minor Project-I and the NUES paper MCA-171 Professional Proficiency-I.
MCA-101 Discrete Structures notes FAQs
How do I get the full MCA-101 notes?
Send a WhatsApp message to 9899436384 using the "Get Full Notes" button on this page. The full MCA-101 notes are sold only as a printed book of 87 pages covering all 4 units; they are not available as a PDF. Delivery takes 5 to 7 days at most, depending on your location, and our team confirms it on the same chat.
What is the passing mark in MCA-101 Discrete Structures?
MCA-101 is marked out of 100, and the end-term paper itself carries 60 of those marks (12 + 48). The MCA scheme of examination states pass marks as 40 out of 100 marks for every paper, including MCA-101. Rules on minimum end-term marks and re-appear chances are in GGSIPU Ordinance 11, which governs the MCA programme.
How is the MCA-101 end-term paper set?
Question 1 is compulsory, covers the whole syllabus and has objective or short-answer parts worth 12 marks. Each of the four units then has two questions, of which you attempt one, and each carries 12 marks including subparts. That makes 12 + 48 = 60 marks for the end-term paper. Every question is mapped to one of the five course outcomes.
Which MCA-101 unit has the most solved examples?
Unit II has the most, with 32 solved examples across formal logic, proofs, lattices and Boolean algebra, including three worked K-map minimisations, one with don't-care cells. Unit I follows with 24, Unit III has 22 and Unit IV has 8. Unit IV has fewer examples but 9 figures and a full Five Colour Theorem proof.
Do the MCA-101 notes follow the 2025-26 GGSIPU MCA scheme?
Yes. The notes were checked against the MCA Scheme of Examination and Detailed Syllabus approved by the USIC&T Board of Studies on 28 July 2025, effective from academic session 2025-26. That scheme applies to students admitted to MCA at affiliated institutes from the 2025-26 batch onwards, and every official MCA-101 topic in all four units has its own section in the notes.
Do I need a maths background for MCA-101 Discrete Structures?
The official pre-requisite for MCA-101 is basic knowledge of mathematics, nothing more. The notes start each unit from definitions, explain every symbol in words and solve numericals line by line with a check step. If you are new to proofs, give Unit III group theory extra time, as its definitions build on each other quickly.
Get the full MCA-101 Discrete Structures Notes on WhatsApp
The complete MCA-101 notes are one printed book of 87 pages, ordered on WhatsApp; there is no PDF edition.
MCA-101 notes book by unit
- Unit
- Unit I
- Pages
- 22 (pp. 5-26)
- Solved examples
- 24
- Short answers
- 12
- Long questions
- 9
- Unit
- Unit II
- Pages
- 22 (pp. 27-48)
- Solved examples
- 32
- Short answers
- 12
- Long questions
- 9
- Unit
- Unit III
- Pages
- 20 (pp. 49-68)
- Solved examples
- 22
- Short answers
- 12
- Long questions
- 9
- Unit
- Unit IV
- Pages
- 19 (pp. 69-87)
- Solved examples
- 8
- Short answers
- 12
- Long questions
- 9
Printed in English with 20 figures. Delivery: within 5 to 7 days at most; the exact time may vary with your location.
Order the MCA-101 notes book on WhatsApp (4 units, 87 pages)
Unnati Educations is an independent education provider based in Vikaspuri, Delhi. We are not affiliated with, authorised by, or endorsed by Guru Gobind Singh Indraprastha University (GGSIPU). 'GGSIPU' and 'IPU' are used only to describe the syllabus our notes follow. For official information, visit ipu.ac.in.
Ready for the full notes?
Discuss coverage and delivery with our team.