BE Computer Engineering (IOE, TU) Discrete Structure (IOE, CT 551) Question Paper 2079 Nepal

(a) Principle of Mathematical Induction and proof of the sum of squares

Principle of Mathematical Induction. Let $P(n)$ be a statement about a positive integer $n$. If

1. Basis step: $P(1)$ is true, and
2. Inductive step: for every $k \ge 1$, $P(k) \Rightarrow P(k+1)$,

then $P(n)$ is true for all positive integers $n$.

To prove: $\displaystyle P(n): \; 1^2 + 2^2 + \cdots + n^2 = \frac{n(n+1)(2n+1)}{6}.$

Basis step ($n=1$): LHS $= 1^2 = 1$. RHS $= \dfrac{1\cdot 2 \cdot 3}{6} = 1$. So $P(1)$ holds.

Inductive step: Assume $P(k)$ is true, i.e.

$$1^2 + 2^2 + \cdots + k^2 = \frac{k(k+1)(2k+1)}{6}.$$

Add $(k+1)^2$ to both sides:

$$1^2 + \cdots + k^2 + (k+1)^2 = \frac{k(k+1)(2k+1)}{6} + (k+1)^2.$$

Taking $(k+1)$ common:

$$= (k+1)\cdot\frac{k(2k+1) + 6(k+1)}{6} = (k+1)\cdot\frac{2k^2 + 7k + 6}{6} = (k+1)\cdot\frac{(k+2)(2k+3)}{6}.$$

This is exactly $\dfrac{(k+1)\big((k+1)+1\big)\big(2(k+1)+1\big)}{6}$, which is $P(k+1)$.

Since the basis and inductive steps hold, by the principle of mathematical induction $P(n)$ is true for all positive integers $n$. $\blacksquare$

(b) Solving the recurrence $a_n = 5a_{n-1} - 6a_{n-2}$

This is a linear homogeneous recurrence of degree 2. The characteristic equation is obtained by substituting $a_n = r^n$:

$$r^2 = 5r - 6 \;\Rightarrow\; r^2 - 5r + 6 = 0 \;\Rightarrow\; (r-2)(r-3) = 0.$$

The roots are $r_1 = 2$ and $r_2 = 3$ (distinct), so the general solution is

$$a_n = A\cdot 2^n + B\cdot 3^n.$$

Apply initial conditions:

• $a_0 = 1: \; A + B = 1.$
• $a_1 = 0: \; 2A + 3B = 0.$

From the first, $A = 1 - B$. Substituting: $2(1-B) + 3B = 0 \Rightarrow 2 + B = 0 \Rightarrow B = -2$, hence $A = 3$.

Final solution:

$$\boxed{a_n = 3\cdot 2^n - 2\cdot 3^n.}$$

Check: $a_0 = 3 - 2 = 1$, $a_1 = 6 - 6 = 0$, $a_2 = 12 - 18 = -6$, and $5a_1 - 6a_0 = 0 - 6 = -6$. ✓

(a) Tautology, contradiction, contingency and the truth table

• Tautology: a compound proposition that is true for every assignment of truth values to its variables (e.g. $p \vee \neg p$).
• Contradiction: a compound proposition that is false for every assignment (e.g. $p \wedge \neg p$).
• Contingency: a compound proposition that is true for some assignments and false for others (neither a tautology nor a contradiction).

Truth table for $(p \rightarrow q) \wedge (q \rightarrow r)$:

The final column contains both T and F, so the proposition is a contingency.

(b) Validity by rules of inference

Premises: (1) $p \rightarrow q$, (2) $\neg q \vee r$, (3) $\neg r$. Conclusion: $\neg p$.

Hence the conclusion $\neg p$ follows, so the argument is valid.

(c) Translation with quantifiers

Universe of discourse: all students in this class. Let $P(x)$: "$x$ has visited Pokhara", and $L(x)$: "$x$ has visited Lumbini".

$$\forall x \,\big( P(x) \vee L(x) \big).$$

This reads: for every student $x$ in the class, $x$ has visited Pokhara or Lumbini (inclusive or).

(a) Definitions

• Connected graph: a graph in which there is a path between every pair of distinct vertices.
• Hamiltonian circuit: a closed walk that visits every vertex exactly once and returns to the starting vertex.
• Euler circuit: a closed walk that traverses every edge exactly once and returns to the starting vertex.

Necessary and sufficient condition (Euler circuit): A connected graph (with at least one edge) contains an Euler circuit if and only if every vertex has even degree.

(b) Dijkstra's algorithm from $A$

Edges (undirected): $AB=4,\ AC=2,\ CB=1,\ BD=5,\ CD=8,\ CE=10,\ DE=2,\ DZ=6,\ EZ=3$.

Start: $d(A)=0$, all others $\infty$. At each step pick the unvisited vertex of least tentative distance, mark it permanent (✓), and relax its neighbours.

Relaxation notes: from C, $B: \min(4, 2+1)=3$, $D: 2+8=10$, $E: 2+10=12$. From B, $D: \min(10, 3+5)=8$. From D, $E:\min(12,8+2)=10$, $Z:8+6=14$. From E, $Z:\min(14,10+3)=13$.

Shortest distances from $A$:

$$A=0,\quad C=2,\quad B=3,\quad D=8,\quad E=10,\quad Z=13.$$

Shortest paths: $A\to C$ (2); $A\to C\to B$ (3); $A\to C\to B\to D$ (8); $A\to C\to B\to D\to E$ (10); $A\to C\to B\to D\to E\to Z$ (13).

(a) $R$ on $\mathbb{Z}$: $a\,R\,b \iff 5 \mid (a-b)$ is an equivalence relation

We verify the three properties.

• Reflexive: for any $a$, $a-a = 0 = 5\cdot 0$, which is divisible by 5, so $a\,R\,a$. ✓
• Symmetric: if $a\,R\,b$ then $a-b = 5k$ for some integer $k$. Then $b-a = -5k = 5(-k)$ is divisible by 5, so $b\,R\,a$. ✓
• Transitive: if $a\,R\,b$ and $b\,R\,c$, then $a-b = 5k$ and $b-c = 5m$. Adding, $a-c = 5(k+m)$ is divisible by 5, so $a\,R\,c$. ✓

Hence $R$ is reflexive, symmetric and transitive, so it is an equivalence relation.

Equivalence classes. Two integers are related iff they leave the same remainder on division by 5. So there are exactly five classes (the residue classes mod 5):

$$[0]=\{\dots,-5,0,5,10,\dots\},\ [1],\ [2],\ [3],\ [4],$$

where $[r] = \{ x \in \mathbb{Z} : x \equiv r \pmod 5 \}$. These five classes partition $\mathbb{Z}$.

(b) Inclusion–exclusion for two sets

Statement. For finite sets $A$ and $B$,

$$|A \cup B| = |A| + |B| - |A \cap B|.$$

Proof. When we add $|A|$ and $|B|$, every element of $A\cap B$ is counted twice — once in $A$ and once in $B$ — while elements in exactly one set are counted once. Subtracting $|A\cap B|$ removes the double count, leaving each element of $A\cup B$ counted exactly once. Hence $|A\cup B| = |A|+|B|-|A\cap B|$. $\blacksquare$

Numerical part. Let $T$ = tea drinkers, $C$ = coffee drinkers, total $= 120$. $|T|=70$, $|C|=60$, $|T\cap C|=30$.

$$|T \cup C| = 70 + 60 - 30 = 100.$$

Students who like neither $= 120 - 100 = \boxed{20}.$

(a) Injective, surjective, bijective functions

Let $f : X \to Y$.

• Injective (one-to-one): distinct inputs give distinct outputs, i.e. $f(a)=f(b) \Rightarrow a=b$. Example: $f:\mathbb{R}\to\mathbb{R},\ f(x)=2x$ (injective but, on $\mathbb{R}\to\mathbb{R}$, also surjective; on $\mathbb{N}\to\mathbb{N}$, $f(n)=2n$ is injective only).
• Surjective (onto): every element of the codomain is an image, i.e. for all $y\in Y$ there is $x\in X$ with $f(x)=y$. Example: $f:\mathbb{R}\to\mathbb{R},\ f(x)=x^3$ is surjective.
• Bijective: both injective and surjective (a one-to-one correspondence). Example: $f:\mathbb{R}\to\mathbb{R},\ f(x)=x+1$.

(b) $f(x) = 3x - 7$ is a bijection; find $f^{-1}$

Injective: Suppose $f(a)=f(b)$. Then $3a-7 = 3b-7 \Rightarrow 3a = 3b \Rightarrow a=b$. So $f$ is one-to-one.

Surjective: Let $y\in\mathbb{R}$. Solve $y = 3x-7 \Rightarrow x = \dfrac{y+7}{3} \in \mathbb{R}$, and $f\!\left(\dfrac{y+7}{3}\right)=y$. So every $y$ is attained; $f$ is onto.

Being injective and surjective, $f$ is a bijection.

Inverse: set $y = 3x-7$ and solve for $x$: $x = \dfrac{y+7}{3}$. Renaming,

$$\boxed{f^{-1}(x) = \frac{x+7}{3}.}$$

Check: $f^{-1}(f(x)) = \frac{(3x-7)+7}{3} = x.$ ✓

(a) Rearrangements of "ENGINEERING"

The word has 11 letters. Letter counts:

• E: 3, N: 3, G: 2, I: 2, R: 1.

(Check: $3+3+2+2+1 = 11$.) The number of distinct arrangements is the multinomial

$$\frac{11!}{3!\,3!\,2!\,2!\,1!} = \frac{39916800}{6\cdot 6\cdot 2\cdot 2\cdot 1} = \frac{39916800}{144} = \boxed{277200}.$$

(b) Committee of 4 with at least 2 women (7 men, 5 women)

"At least 2 women" means 2, 3, or 4 women (the rest men).

• 2 women, 2 men: $\binom{5}{2}\binom{7}{2} = 10 \cdot 21 = 210.$
• 3 women, 1 man: $\binom{5}{3}\binom{7}{1} = 10 \cdot 7 = 70.$
• 4 women, 0 men: $\binom{5}{4}\binom{7}{0} = 5 \cdot 1 = 5.$

Total $= 210 + 70 + 5 = \boxed{285}$ ways.

(a) Postulates of Boolean algebra and the absorption law

A Boolean algebra $(B, +, \cdot, ', 0, 1)$ satisfies, for all $x,y,z\in B$:

1. Closure under $+$ and $\cdot$.
2. Identity: $x + 0 = x$, $\;x \cdot 1 = x$.
3. Commutativity: $x+y = y+x$, $\;x\cdot y = y\cdot x$.
4. Distributivity: $x\cdot(y+z) = x\cdot y + x\cdot z$ and $x+(y\cdot z) = (x+y)\cdot(x+z)$.
5. Complement: $x + x' = 1$, $\;x\cdot x' = 0$.

Proof of absorption $x + xy = x$:

$$x + xy = x\cdot 1 + x\cdot y \quad (\text{identity, } x = x\cdot 1)$$ $$= x\cdot(1 + y) \quad (\text{distributive law})$$ $$= x\cdot 1 \quad (1 + y = 1)$$ $$= x. \qquad \blacksquare$$

(b) K-map simplification of $F(x,y,z) = \sum m(0,1,2,4,5)$

Minterms in $xyz$ order: $0{=}000,\ 1{=}001,\ 2{=}010,\ 4{=}100,\ 5{=}101$.

K-map (rows = $x$, columns = $yz$ in Gray order $00,01,11,10$):

Grouping:

• The whole $yz=00$ and $yz=01$ columns (m0,m1,m4,m5) form a quad $\Rightarrow y'$ (since $y=0$ throughout).
• m0 and m2 (cells $x{=}0$, $yz=00,10$) form a pair $\Rightarrow x'z'$.

Simplified expression:

$$\boxed{F = y' + x'z'.}$$

Logic circuit (described): invert $y$ with a NOT gate to get $y'$; invert $x$ and $z$ to get $x',z'$ and feed them into a 2-input AND gate producing $x'z'$; feed $y'$ and $x'z'$ into a 2-input OR gate. The OR gate output is $F$.

(a) Adjacency and incidence matrices

• Adjacency matrix: an $n\times n$ matrix $A$ (for $n$ vertices) where $A_{ij}$ = number of edges between vertices $i$ and $j$ (1 if adjacent, 0 otherwise, for a simple graph). It is symmetric for undirected graphs.
• Incidence matrix: an $n\times m$ matrix $M$ (vertices $\times$ edges) where $M_{ie}=1$ if vertex $i$ is an endpoint of edge $e$, else $0$ (each column has exactly two 1's for an undirected graph).

Graph: vertices $\{1,2,3,4\}$, edges $\{1,2\},\{2,3\},\{3,4\},\{4,1\},\{1,3\}$.

Adjacency matrix (rows/columns ordered $1,2,3,4$):

$$A = \begin{pmatrix} 0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \end{pmatrix}$$

(Vertex 1 is adjacent to 2,3,4; vertex 2 to 1,3; vertex 3 to 1,2,4; vertex 4 to 1,3. Degrees: 3,2,3,2.)

(b) Testing graph isomorphism using invariants

Two graphs $G_1$ and $G_2$ are isomorphic if there is a bijection between their vertex sets that preserves adjacency. Necessary conditions (graph invariants) — they must agree for the graphs to possibly be isomorphic:

1. Same number of vertices.
2. Same number of edges.
3. Same degree sequence (multiset of vertex degrees).
4. Same number/length of cycles, same connectivity, etc.

Method: Compute the degree sequence of each graph. If the degree sequences (or any other invariant) differ, the graphs are not isomorphic. If all checked invariants match, attempt to construct an explicit adjacency-preserving bijection; if one exists, the graphs are isomorphic.

Worked illustration: if $G_1$ has degree sequence $(3,3,2,2)$ and $G_2$ has $(3,2,2,1)$, they have the same number of vertices but different degree sequences, so they are not isomorphic. If instead both have degree sequence $(3,3,2,2)$ and equal edge counts, we map the two degree-3 vertices of $G_1$ to the two degree-3 vertices of $G_2$ and verify adjacencies; a consistent mapping confirms isomorphism.

(a) Binary search tree (BST)

A binary search tree is a binary tree in which, for every node, all keys in its left subtree are less than the node's key and all keys in its right subtree are greater than the node's key.

Insert 50, 30, 70, 20, 40, 60, 80:

• 50 → root.
• 30 < 50 → left of 50.
• 70 > 50 → right of 50.
• 20 < 50, < 30 → left of 30.
• 40 < 50, > 30 → right of 30.
• 60 > 50, < 70 → left of 70.
• 80 > 50, > 70 → right of 70.

Resulting tree:

            50
          /    \
        30      70
       /  \    /  \
      20  40  60  80

This is a complete, balanced BST of height 2.

(b) Traversals

• Preorder (Root, Left, Right): $50,\ 30,\ 20,\ 40,\ 70,\ 60,\ 80.$
• Inorder (Left, Root, Right): $20,\ 30,\ 40,\ 50,\ 60,\ 70,\ 80.$ (sorted, as expected for a BST)
• Postorder (Left, Right, Root): $20,\ 40,\ 30,\ 60,\ 80,\ 70,\ 50.$

(a) Recurrence for binary strings of length $n$ with no two consecutive 0's

Let $a_n$ be the number of binary strings of length $n$ containing no two consecutive 0's. Classify by the last bit:

• If the last bit is 1, the first $n-1$ bits form any valid string of length $n-1$: $a_{n-1}$ ways.
• If the last bit is 0, the previous bit must be 1 (to avoid "00"), and the first $n-2$ bits form any valid string of length $n-2$: $a_{n-2}$ ways.

Hence

$$\boxed{a_n = a_{n-1} + a_{n-2}}, \quad n \ge 3,$$

with initial conditions $a_1 = 2$ (strings: "0","1") and $a_2 = 3$ (strings: "01","10","11"; "00" excluded). This is the Fibonacci recurrence.

(b) Distribute 10 identical chocolates among 3 distinct children, each at least one

We need positive-integer solutions of $x_1 + x_2 + x_3 = 10$ with each $x_i \ge 1$. The number of such solutions is

$$\binom{10-1}{3-1} = \binom{9}{2} = 36.$$

Generating-function view: each child contributes $x + x^2 + \cdots = \dfrac{x}{1-x}$, so the generating function is

$$\left(\frac{x}{1-x}\right)^3 = \frac{x^3}{(1-x)^3}.$$

The number of ways is the coefficient of $x^{10}$, i.e. the coefficient of $x^{7}$ in $(1-x)^{-3}$, which is $\binom{7+2}{2} = \binom{9}{2} = \boxed{36}.$

(a) Cartesian product and number of relations

$A = \{1,2,3\}$, $B = \{a,b\}$. The Cartesian product $A\times B$ has $3\times 2 = 6$ ordered pairs:

$$A\times B = \{(1,a),(1,b),(2,a),(2,b),(3,a),(3,b)\}.$$

A relation from $A$ to $B$ is any subset of $A\times B$. Since $|A\times B| = 6$, the number of relations is

$$2^{|A\times B|} = 2^{6} = \boxed{64}.$$

(b) Partial order and Hasse diagram for divisibility on $\{1,2,3,6,12\}$

Partial order relation: a relation $R$ on a set that is reflexive, antisymmetric, and transitive. A set with such a relation is a partially ordered set (poset). Divisibility ($a \le b \iff a \mid b$) is a partial order.

Cover relations (draw $a$ below $b$ when $a \mid b$ and there is no intermediate divisor):

• $1 \mid 2$, $1 \mid 3$
• $2 \mid 6$, $3 \mid 6$
• $6 \mid 12$

Hasse diagram (described):

        12
        |
        6
       / \
      2   3
       \ /
        1

Element 1 is at the bottom; 2 and 3 are above 1; 6 is above both 2 and 3; 12 is at the top above 6.

• Minimal element: $1$ (nothing below it). It is also the least element.
• Maximal element: $12$ (nothing above it). It is also the greatest element.