CS-302 Discrete Structure - Dec 2024 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 various types of functions. How many symmetric and reflexive relations are possible from a set A containing 'n' elements?
   How to answer

   • Define one-to-one (injective), onto (surjective), and bijective functions with mathematical conditions
   • Define reflexive relation and symmetric relation on a set
   • Derive or state the formula for number of reflexive and symmetric relations on a set of size n: $2^{n(n-1)/2}$
2. 7 Marks
   bLet $Z$ be the group of integers with binary operation $*$ defined by $a * b = a + b - 2$, for all $a, b \in Z$. Find the identity element of the group $\langle Z, * \rangle$.
   How to answer

   • State the definition of identity element: $a * e = a = e * a$
   • Apply the given definition: $a + e - 2 = a$
   • Solve for $e$: $e - 2 = 0 \implies e = 2$
   • Verify: $2 * a = 2 + a - 2 = a$, hence identity is 2
3. 7 Marks
   aShow that every Cyclic group is Abelian. Prove that a lattice with 5 elements is not a Boolean algebra.
   How to answer

   • Let $G = \langle a \rangle$ be a cyclic group. For any $x, y \in G$, $x = a^m$ and $y = a^n$
   • Show $x y = a^m a^n = a^{m+n} = a^{n+m} = a^n a^m = y x$, thus $G$ is Abelian
   • State the property that any finite Boolean algebra has cardinality $2^n$ for some non-negative integer $n$
   • Conclude that since 5 is not a power of 2 ($2^n \neq 5$), no 5-element lattice can be a Boolean algebra
4. 7 Marks
   bDefine Pigeon hole Principle. Write the contra positive of the implication: "if it is Sunday then it is a holiday."
   How to answer

   • State the Pigeonhole Principle: If $k + 1$ or more objects are placed into $k$ boxes, at least one box contains two or more objects
   • State definition of contrapositive of $p \to q$ as $\neg q \to \neg p$
   • Identify $p$: 'it is Sunday' and $q$: 'it is a holiday'
   • Write contrapositive: 'If it is not a holiday, then it is not Sunday.'
5. 7 Marks
   aShow that there does not exist a graph with 5 vertices with degrees 1, 3, 4, 2, 3 respectively.
   How to answer

   • State the Handshaking Lemma: $\sum \deg(v) = 2e$, which must be an even number
   • Compute the sum of degrees: $1 + 3 + 4 + 2 + 3 = 13$
   • Observe that 13 is an odd number (or note there are 3 vertices of odd degree, which is impossible)
   • Conclude that no such graph can exist
6. 7 Marks
   bObtain the generating function for the sequence 4, 4, 4, 4, 4, 4, 4. Explain complete digraph.
   How to answer

   • Write formula for generating function: $G(x) = \sum_{k=0}^{6} 4 x^k = 4(1 + x + x^2 + x^3 + x^4 + x^5 + x^6)$
   • Express as closed form: $G(x) = 4 \frac{1 - x^7}{1 - x}$
   • Define complete digraph: a directed graph in which there is a directed edge between every pair of distinct vertices in both directions (or exactly one in each direction)
   • State properties (number of edges $n(n-1)$) and provide a small illustrative diagram
7. 7 Marks
   aDefine planar graph. Prove that for any connected planar graph, $v - e + r = 2$ Where $v, e, r$ is the number of vertices, edges, and regions of the graph respectively.
   How to answer

   • Define planar graph: a graph that can be drawn in a plane such that no two edges intersect except at vertices
   • State Euler's formula: $v - e + r = 2$
   • Prove by induction on the number of edges $e$ (base case: tree where $e = v - 1$ and $r = 1$)
   • Show induction step by adding/removing an edge that forms a cycle, increasing both $e$ and $r$ by 1
8. 7 Marks
   bFind the numbers between 1 to 500 that are not divisible by any of the integers 2 or 3 or 5 or 7.
   How to answer

   • State Principle of Inclusion-Exclusion for 4 sets $A_2, A_3, A_5, A_7$
   • Calculate sizes of single sets: $\lfloor 500/2 \rfloor = 250$, $\lfloor 500/3 \rfloor = 166$, $\lfloor 500/5 \rfloor = 100$, $\lfloor 500/7 \rfloor = 71$
   • Calculate pairwise intersections: $\lfloor 500/6 \rfloor = 83$, $\lfloor 500/10 \rfloor = 50$, $\lfloor 500/14 \rfloor = 35$, $\lfloor 500/15 \rfloor = 33$, $\lfloor 500/21 \rfloor = 23$, $\lfloor 500/35 \rfloor = 14$
   • Calculate triple intersections: $\lfloor 500/30 \rfloor = 16$, $\lfloor 500/42 \rfloor = 11$, $\lfloor 500/70 \rfloor = 7$, $\lfloor 500/105 \rfloor = 4$
   • Calculate quadruple intersection: $\lfloor 500/210 \rfloor = 2$
   • Compute union size and subtract from total (note whether 'between 1 to 500' means 498 or inclusive 500)
9. 7 Marks
   aA collection of 10 electric bulbs contain 3 defective ones (i) In how many ways can a sample of four bulbs be selected? (ii) In how many ways can a sample of 4 bulbs be selected which contain 2 good bulbs and 2 defective ones? (iii) In how many ways can a sample of 4 bulbs be selected so that either the sample contains 3 good ones and 1 defectives ones or 1 good and 3 defectives ones?
   How to answer

   • (i) Total ways: $\binom{10}{4} = \frac{10 \times 9 \times 8 \times 7}{24} = 210$
   • (ii) 2 good and 2 defective: $\binom{7}{2} \times \binom{3}{2} = 21 \times 3 = 63$
   • (iii) (3 good & 1 defective) OR (1 good & 3 defective): $\binom{7}{3}\binom{3}{1} + \binom{7}{1}\binom{3}{3} = (35 \times 3) + (7 \times 1) = 105 + 7 = 112$
10. 7 Marks
    bDiscuss about Complete digraph and Euler Graph with the help of suitable examples.
    How to answer

    • Define Complete digraph: directed graph where every pair of vertices is connected by bidirectional directed edges
    • Provide a diagram and degree properties of a complete digraph (e.g., $K_3$ or $K_4$ digraph)
    • Define Euler Graph: a graph containing an Eulerian circuit traversing every edge exactly once
    • State Euler's theorem: all vertices must have even degrees (connected)
    • Give an example diagram of an Euler graph
11. 7 Marks
    aSolve the following recurrence equation using generating function. $$G(K) - 7 G(K-1) + 10 G(K-2) = 8K + 6.$$
    How to answer

    • Multiply the recurrence relation by $x^K$ and sum over $K \ge 2$
    • Express sums in terms of the generating function $A(x) = \sum_{K=0}^{\infty} G(K) x^K$
    • Substitute boundary conditions (or express solution in terms of constants $G(0), G(1)$)
    • Decompose into partial fractions
    • Expand using standard series to obtain the general form of $G(K)$
12. 7 Marks
    bProve the validity of the following argument "if the races are fixed so the casinos are crooked, then the tourist trade will decline. If the tourist trade decreases, then the police will be happy. The police force is never happy. Therefore, the races are not fixed."
    How to answer

    • Assign propositional variables: $p$: races are fixed, $q$: casinos are crooked, $r$: tourist trade declines, $s$: police will be happy
    • Formalize premises: $P_1: (p \land q) \to r$ (or $(p \to q) \to r$), $P_2: r \to s$, $P_3: \neg s$
    • Apply Modus Tollens on $P_2$ and $P_3$ to infer $\neg r$
    • Apply Modus Tollens on $P_1$ and $\neg r$ to infer $\neg (p \land q)$ or $\neg p$
    • Conclude validity of the argument based on stated inference rules
13. 7 Marks
    aLet $(L, \vee, \wedge, \le)$ be a distributive lattice and $a, b, c \in L$. If $a \wedge b = a \wedge c$ and $a \vee b = a \vee c$ then show that $b = c$.
    How to answer

    • Start with absorption law: $b = b \wedge (a \vee b)$ (or $b = b \vee (b \wedge a)$)
    • Substitute $a \vee b = a \vee c$: $b = b \wedge (a \vee c)$
    • Apply distributive law: $b = (b \wedge a) \vee (b \wedge c) = (a \wedge c) \vee (b \wedge c) = (a \vee b) \wedge c$
    • Substitute $a \vee b = a \vee c$: $b = (a \vee c) \wedge c = c$ by absorption law
    • Conclude that $b = c$
14. 7 Marks
    bExplain various Rules of Inference for Propositional Logic.
    How to answer

    • Define rule of inference as a valid argument form
    • List and formulate Modus Ponens: $p, p \to q \vdash q$
    • List and formulate Modus Tollens: $\neg q, p \to q \vdash \neg p$
    • List Hypothetical Syllogism: $p \to q, q \to r \vdash p \to r$
    • List Disjunctive Syllogism: $p \vee q, \neg p \vdash q$
    • List Addition, Simplification, Conjunction, and Resolution with schema
15. 7 Marks
    aWhat is Ring? Define elementary properties of Ring with example.
    How to answer

    • Define a Ring $\langle R, +, \cdot \rangle$ as an algebraic structure where $(R, +)$ is an Abelian group, $(R, \cdot)$ is a semigroup, and $\cdot$ distributes over $+$
    • List axioms explicitly (associativity, identity, inverse, commutativity under $+$, associativity under $\cdot$, distributivity)
    • State elementary properties: $a \cdot 0 = 0 \cdot a = 0$, $a(-b) = -(ab) = (-a)b$, $(-a)(-b) = ab$, $a(b-c) = ab - ac$
    • Give examples: $(\mathbb{Z}, +, \cdot)$, $(\mathbb{R}, +, \cdot)$
16. 7 Marks
    bProve or disprove that intersection of two normal subgroups of a group G is again a normal subgroup of G.
    How to answer

    • Let $H$ and $K$ be normal subgroups of $G$
    • Show $H \cap K$ is a subgroup of $G$ (non-empty as $e \in H \cap K$; closed under operation and inverses)
    • Let $x \in H \cap K$ and $g \in G$. Then $x \in H$ and $x \in K$
    • Since $H \triangleleft G$, $g x g^{-1} \in H$; since $K \triangleleft G$, $g x g^{-1} \in K$
    • Thus $g x g^{-1} \in H \cap K$, proving $H \cap K$ is normal in $G$