CS-302 Discrete Structures - Dec 2025 Question Paper

Under each question, How to answer lists the points an answer should cover, outlined by CampusPrep from the syllabus. Check the details against your textbook.

1. 7 Marks
   aDefine countable and uncountable sets. Prove that the set of rational numbers is countable.
   How to answer

   • Define countable set as in bijection with N or subset of N; uncountable as not countable
   • Enumerate positive rationals by p/q array / Cantor diagonal enumeration
   • Extend to all rationals including negatives and zero to show countability
   • Conclude Q is countable infinite
2. 7 Marks
   bUsing Venn diagram, prove: $$A\cap(B\cup C)=(A\cap B)\cup(A\cap C)$$
   How to answer

   • State distributive law $A\cap(B\cup C)=(A\cap B)\cup(A\cap C)$
   • Draw Venn diagram for LHS with shading of $B\cup C$ then intersection with A
   • Draw Venn diagram for RHS with shadings of intersections and union
   • Conclude equality from identical shaded regions
3. 7 Marks
   aDefine relation. Explain equivalence relation and partial ordering relation with suitable examples.
   How to answer

   • Define relation as subset of Cartesian product AxB
   • Define equivalence relation: reflexive, symmetric, transitive with example
   • Define partial ordering relation: reflexive, antisymmetric, transitive with example
   • Give suitable examples e.g. congruence modulo n and divisibility / subset relation
4. 7 Marks
   bLet $$A=\{1, 2, 3\}$$ $$R=\{(1,1), (2,2), (3,3), (1,2), (2,1)\}$$ Check whether R is an equivalence relation and find equivalence classes.
   How to answer

   • Check reflexive: (1,1),(2,2),(3,3) present
   • Check symmetric: (1,2) and (2,1) both present
   • Check transitive for pairs involving 1,2 and conclude equivalence
   • List equivalence classes: [1]=[2]={1,2}, [3]={3}
5. 7 Marks
   aDefine one-one, onto and bijective functions. Prove that inverse of a function exists if and only if the function is bijective.
   How to answer

   • Define one-one (injective), onto (surjective) and bijective with examples
   • Assume f bijective and construct inverse using pre-image uniqueness
   • Conversely assume inverse exists and prove f must be one-one and onto
   • Conclude inverse exists iff bijective
6. 7 Marks
   bState and prove Pigeonhole Principle.
   How to answer

   • State pigeonhole principle: n+1 objects in n boxes implies one box with >=2 objects
   • Give formal statement with m,n version if needed
   • Prove by contradiction / contrapositive using counting
   • Give illustrative example
7. 7 Marks
   aConstruct truth table for the proposition. $$(p\to q)\leftrightarrow(\neg p\lor q)$$ and show that it is a tautology.
   How to answer

   • List all 4 truth assignments for p,q
   • Evaluate $p\to q$ and $\neg p \lor q$ columns
   • Evaluate biconditional $(p\to q)\leftrightarrow(\neg p \lor q)$
   • Show final column all true hence tautology
8. 7 Marks
   bConvert the following statement into predicate logic and write its negation: "Every student studies Discrete Mathematics."
   How to answer

   • Define predicates e.g. S(x): x is student, D(x): x studies Discrete Mathematics
   • Write universal quantification $\forall x (S(x)\to D(x))$ or $\forall x D(x)$ over domain of students
   • Negate using $\neg\forall = \exists$ to get existential statement
   • Give English negation: There exists a student who does not study Discrete Mathematics
9. 7 Marks
   aProve by mathematical induction that: $$1 + 2 + 3 + \dots + n = \frac{n(n + 1)}{2}.$$
   How to answer

   • State base case n=1 verification
   • Assume induction hypothesis for n=k
   • Prove for n=k+1 by adding k+1 to both sides
   • Conclude by principle of mathematical induction
10. 7 Marks
    bProve by contradiction that $\sqrt{2}$ is irrational.
    How to answer

    • Assume contrary that $\sqrt{2}$ is rational p/q in lowest terms
    • Square to get $2q^2=p^2$ implying p even
    • Substitute p=2k to show q also even
    • Contradiction with coprime assumption hence irrational
11. 7 Marks
    aDefine group and Abelian group. Prove that identity element of a group is unique.
    How to answer

    • Define group with closure, associativity, identity, inverse axioms
    • Define Abelian group with commutativity
    • Assume two identities e and e' and use e*e'
    • Conclude e=e' proving uniqueness
12. 7 Marks
    bFind all subgroups of the group $Z_8$.
    How to answer

    • Recall $Z_8$ under addition modulo 8
    • Use Lagrange theorem: order of subgroup divides 8
    • List subgroups generated by divisors: {0}, {0,4}, {0,2,4,6}, $Z_8$ itself
    • Verify closure under addition mod 8
13. 7 Marks
    aDefine Finite State Machine. Explain FSM as a language recognizer.
    How to answer

    • Define FSM as 5-tuple (Q, Σ, δ, q0, F)
    • Explain components: states, input alphabet, transition function
    • Explain recognizer mode with acceptance by final state
    • Give simple example of language recognition
14. 7 Marks
    bDesign a finite state machine that accepts all binary strings ending with 01.
    How to answer

    • Define states for suffixes: no suffix, suffix 0, suffix 01 (accept)
    • Draw transition diagram for inputs 0,1 from each state
    • Mark start state and final accepting state
    • Test with examples ending and not ending in 01
15. 7 Marks
    aDefine Euler path and Euler circuit. State necessary and sufficient conditions for their existence.
    How to answer

    • Define Euler path (trail using every edge exactly once) and Euler circuit (closed Euler trail)
    • State condition: connected graph, 0 odd vertices for circuit, 0 or 2 for path
    • Explain necessity via degree counting on entry/exit
    • Mention sufficiency theorem for connected graphs
16. 7 Marks
    bExplain Dijkstra's Algorithm and find the shortest path from a given source vertex in a weighted graph.
    How to answer

    • Explain initialization of distances and visited set
    • Describe iterative selection of minimum distance vertex and relaxation
    • Give pseudocode and complexity O(n^2) / with heap
    • Illustrate finding shortest path from source in weighted graph with example steps