CS-302 Discrete Structure - Jun 2023 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
   aProve that $P(A) \subseteq P(B)$ if and only if $A \subseteq B$.
   How to answer

   • Assume $A \subseteq B$ and show $X \in P(A) \implies X \in P(B)$
   • Assume $P(A) \subseteq P(B)$ and let $x \in A$, then $\{x\} \in P(A)$
   • Since $P(A) \subseteq P(B)$, $\{x\} \in P(B)$, hence $x \in B$
   • Conclude that both directions hold, establishing the equivalence
2. 7 Marks
   bSuppose that $R$ is the relation on the set of strings of English letters such that $aRb$ if and only if $l(a) = l(b)$, where $l(x)$ is the length of the string $x$. Is $R$ an equivalence relation?
   How to answer

   • State conditions for an equivalence relation: reflexive, symmetric, transitive
   • Check reflexivity: $l(a) = l(a) \implies aRa$
   • Check symmetry: $l(a) = l(b) \implies l(b) = l(a) \implies bRa$
   • Check transitivity: $l(a) = l(b)$ and $l(b) = l(c) \implies l(a) = l(c) \implies aRc$
   • Conclude that $R$ is an equivalence relation
3. 7 Marks
   aIllustrate the concept of an inverse function. Let $f : Z \to Z$ be such that $f(x) = x + 1$. Is $f$ invertible? if it is then what is its inverse?
   How to answer

   • Define inverse function and condition for invertibility (bijective)
   • Prove $f(x) = x + 1$ is injective (one-to-one): $x_1 + 1 = x_2 + 1 \implies x_1 = x_2$
   • Prove $f(x)$ is surjective (onto): for any $y \in Z$, $x = y - 1 \in Z$ such that $f(x) = y$
   • Conclude $f$ is bijective, hence invertible
   • State $f^{-1}(y) = y - 1$
4. 7 Marks
   bDefine group. Explain the properties of groups.
   How to answer

   • Definition of an algebraic structure $(G, *)$
   • Property 1: Closure property
   • Property 2: Associative property
   • Property 3: Existence of identity element
   • Property 4: Existence of inverse element
   • Mention abelian group (commutative property) as an extension
5. 14 Marks
   Let $S = N \times N$. Let $*$ be the operation on $S$ defined by $(a, b) * (a', b') = (aa', bb')$. i) Define $f : (S, *) \to (Q, \times)$ by $f(a, b) = a/b$. Show that $f$ is a homomorphism. ii) Find the congruence relation $\sim$ in $S$ determined by the homomorphism $f$, that is, where $x \sim y$ if $f(x) = f(y)$.
   How to answer

   • Part i: Compute $f((a, b) * (a', b')) = f(aa', bb') = (aa')/(bb')$.
   • Compute $f(a, b) \times f(a', b') = (a/b) \times (a'/b') = (aa')/(bb')$. Since they are equal, $f$ is a homomorphism.
   • Part ii: Let $x = (a, b)$ and $y = (c, d)$. Then $x \sim y \iff f(a, b) = f(c, d) \iff a/b = c/d \iff ad = bc$.
   • State the congruence relation as $(a, b) \sim (c, d) \iff ad = bc$ on $N \times N$.
6. 7 Marks
   aShow that the $((p \lor q) \land \neg p) \to q$ compound proposition is a tautology.
   How to answer

   • Construct truth table for variables $p$ and $q$ (4 rows)
   • Evaluate columns: $p \lor q$, $\neg p$, $(p \lor q) \land \neg p$
   • Evaluate conditional $((p \lor q) \land \neg p) \to q$
   • Observe all entries in the final column are True ($T$)
   • Alternatively, prove using logical equivalences: $((p \lor q) \land \neg p) \equiv (p \land \neg p) \lor (q \land \neg p) \equiv F \lor (q \land \neg p) \equiv q \land \neg p$, then $(q \land \neg p) \to q \equiv \neg(q \land \neg p) \lor q \equiv (\neg q \lor p) \lor q \equiv T$
7. 7 Marks
   bUse existential and universal quantifiers to express the statement. "No one has more than three grandmothers" using the propositional function $G(x, y)$, which represents "$x$ is the grandmother of $y$."
   How to answer

   • Identify the variables: let $y$ be any person and $x_1, x_2, x_3, x_4$ be potential grandmothers
   • Formulate condition for 4 distinct grandmothers
   • Negate the existence of four distinct grandmothers for any individual $y$
   • Write full logical expression using $\forall$ and $\exists$
8. 7 Marks
   aDiscuss the 6 tuple notation of finite state machine $M$ with an example.
   How to answer

   • Define 6-tuple $M = (Q, \Sigma, \Delta, \delta, \lambda, q_0)$
   • Explain each component: states $Q$, input alphabet $\Sigma$, output alphabet $\Delta$, transition function $\delta$, output function $\lambda$, initial state $q_0$
   • Provide a concrete example of Mealy or Moore machine with state diagram and transition table
9. 7 Marks
   bConsider the complete weighted graph $G$ in the following figure with 5 vertices. Find a Hamiltonian circuit of minimal weight.

   

   How to answer

   • List all possible Hamiltonian circuits (or use TSP algorithms / branch & bound / brute force for 5 vertices)
   • Calculate weights of different candidate cycles
   • Determine the circuit with the minimum sum of edge weights
   • State the optimal vertex sequence and its total weight
10. 7 Marks
    aDiscuss the various applications of graph colouring.
    How to answer

    • Briefly define vertex colouring and chromatic number
    • Application 1: Timetabling and scheduling problems
    • Application 2: Register allocation in compiler optimization
    • Application 3: Map colouring (Four Colour Theorem)
    • Application 4: Frequency assignment in mobile/radio networks
11. 7 Marks
    bState Euler's formula for a planar graph. Give an example of a planar graph with 5 vertices and 5 regions and verify Euler's formula for your example.
    How to answer

    • State Euler's formula: $v - e + r = 2$ for a connected planar graph
    • Given $v = 5$ and $r = 5$, find required edges: $e = v + r - 2 = 5 + 5 - 2 = 8$
    • Draw an example planar graph with $v = 5$ vertices, $e = 8$ edges, and $r = 5$ regions (including outer region)
    • Verify $v - e + r = 5 - 8 + 5 = 2$
12. 7 Marks
    aConsider the set $A = \{4, 5, 6, 7\}$. Let $R$ be the relation $\le$ on $A$. Draw the directed graph and the Hasse diagram of $R$.
    How to answer

    • List pairs of $R$: $(4,4), (4,5), (4,6), (4,7), (5,5), (5,6), (5,7), (6,6), (6,7), (7,7)$
    • Draw directed graph: 4 nodes with self-loops and directed edges for all ordered pairs
    • Draw Hasse diagram: vertical chain with edges $4 - 5 - 6 - 7$ (omitting self loops and transitive edges)
13. 7 Marks
    bConsider the lattice $M$ in the following figure. i) Find the non-zero join irreducible elements and atoms of $M$. ii) Is $M$ distributive and complemented?

    

    How to answer

    • Part i: Identify elements in the lattice: 0 at bottom, atoms/coverings of 0 are $a$ and $b$.
    • Determine non-zero join-irreducible elements (elements that cannot be written as $x \lor y$ with $x, y < z$).
    • Part ii: Test distributive law on sublattices (check for pentagon $N_5$ or diamond $M_3$ sublattices).
    • Check whether each element has a complement (an element $x'$ such that $x \land x' = 0$ and $x \lor x' = 1$).
14. 14 Marks
    Discuss in brief any two of the following: i) Partial ordering relation ii) Cosets iii) Disjunctive normal form iv) Pigeonhole principle
    How to answer

    • For (i): Define reflexive, antisymmetric, transitive relation with an example (e.g., subset relation).
    • For (ii): Define left and right cosets $aH$ and $Ha$ in a group $G$ with subgroup $H$ and properties.
    • For (iii): Define DNF as a sum of minterms / disjunction of conjunctions with an example.
    • For (iv): State standard and generalized pigeonhole principles with an illustrative application.