Dean's Office Official Model Question Paper

Answer:

• Tautology: A compound proposition that is always true for all possible truth value assignments of its component propositional variables (e.g., $p \lor \neg p$).
• Contrapositive: $\neg q \to \neg p$ (which is logically equivalent to $p \to q$).

Answer: Pigeonhole Principle: If $k + 1$ or more objects are placed into $k$ boxes, then at least one box must contain two or more objects. Example: Among any group of 367 people, at least two individuals must share the same birthday.

Answer: A relation $R$ on a set $A$ is an equivalence relation if and only if it satisfies three properties:

1. Reflexive: $(a, a) \in R$ for all $a \in A$.
2. Symmetric: If $(a, b) \in R$, then $(b, a) \in R$.
3. Transitive: If $(a, b) \in R$ and $(b, c) \in R$, then $(a, c) \in R$.

Answer: Euler Circuit: A closed walk in a graph that visits every single edge exactly once and returns to the starting vertex. A connected undirected graph has an Euler circuit if and only if every vertex has an even degree.

Answer: Tree: A connected undirected graph with no simple circuits. Relationship: For any tree with $V$ vertices and $E$ edges:

$$E = V - 1$$

Proof by Mathematical Induction

Let $P(n)$ be the proposition:

$$1^2 + 2^2 + 3^2 + \dots + n^2 = \frac{n(n + 1)(2n + 1)}{6}$$

---

Step 1: Base Case ($n = 1$)

• Left Hand Side (LHS) = $1^2 = 1$.
• Right Hand Side (RHS) = $\frac{1(1 + 1)(2(1) + 1)}{6} = \frac{1(2)(3)}{6} = \frac{6}{6} = 1$. Since $\text{LHS} = \text{RHS} = 1$, the base case $P(1)$ is true.

---

Step 2: Inductive Hypothesis

Assume that $P(k)$ is true for some positive integer $k \ge 1$:

$$1^2 + 2^2 + 3^2 + \dots + k^2 = \frac{k(k + 1)(2k + 1)}{6}$$

---

Step 3: Inductive Step ($n = k + 1$)

We must prove that $P(k + 1)$ is true, i.e.:

$$1^2 + 2^2 + \dots + k^2 + (k + 1)^2 = \frac{(k + 1)((k + 1) + 1)(2(k + 1) + 1)}{6} = \frac{(k + 1)(k + 2)(2k + 3)}{6}$$

Starting with the LHS of $P(k + 1)$:

$$\text{LHS} = [1^2 + 2^2 + \dots + k^2] + (k + 1)^2$$

Substitute the inductive hypothesis:

$$\text{LHS} = \frac{k(k + 1)(2k + 1)}{6} + (k + 1)^2$$

Factor out common term $(k + 1)$:

$$\text{LHS} = (k + 1) \left[ \frac{k(2k + 1)}{6} + (k + 1) \right] = (k + 1) \left[ \frac{2k^2 + k + 6k + 6}{6} \right]$$

$$= (k + 1) \left[ \frac{2k^2 + 7k + 6}{6} \right]$$

Factoring the numerator quadratic $2k^2 + 7k + 6 = 2k^2 + 4k + 3k + 6 = 2k(k + 2) + 3(k + 2) = (k + 2)(2k + 3)$:

$$\text{LHS} = \frac{(k + 1)(k + 2)(2k + 3)}{6} = \text{RHS}$$

Therefore, $P(k + 1)$ is true whenever $P(k)$ is true. By the Principle of Mathematical Induction, $P(n)$ is true for all integers $n \ge 1$.

Solution: Homogeneous Recurrence Relation

Given:

$$a_n - 5a_{n-1} + 6a_{n-2} = 0$$

Step 1: Characteristic Equation

Let $a_n = r^n$:

$$r^2 - 5r + 6 = 0$$

$$(r - 2)(r - 3) = 0$$

The characteristic roots are distinct: $r_1 = 2$ and $r_2 = 3$.

---

Step 2: General Solution

Since roots are real and distinct, the general solution is:

$$a_n = \alpha_1 (2)^n + \alpha_2 (3)^n$$

---

Step 3: Determine Constants $\alpha_1$ and $\alpha_2$ from Initial Conditions

• For $n = 0$:
  $$a_0 = \alpha_1 (2)^0 + \alpha_2 (3)^0 = \alpha_1 + \alpha_2 = 1 \implies \alpha_2 = 1 - \alpha_1 \quad \text{--- (1)}$$
• For $n = 1$:
  $$a_1 = 2\alpha_1 + 3\alpha_2 = 4 \quad \text{--- (2)}$$

Substitute (1) into (2):

$$2\alpha_1 + 3(1 - \alpha_1) = 4$$

$$2\alpha_1 + 3 - 3\alpha_1 = 4 \implies -\alpha_1 = 1 \implies \alpha_1 = -1$$

$$\alpha_2 = 1 - (-1) = 2$$

---

Step 4: Final Solution

$$a_n = -(2)^n + 2(3)^n$$

Verification:

• $n = 0: -(1) + 2(1) = 1$ (Matches $a_0$).
• $n = 1: -(2) + 2(3) = 4$ (Matches $a_1$).
• $n = 2: a_2 = 5(4) - 6(1) = 14$; Formula: $-(4) + 2(9) = -4 + 18 = 14$ (Confirmed).

Dijkstra’s Shortest Path Algorithm

1. Algorithm Overview

• A greedy algorithm that finds the shortest path from a single source vertex to all other vertices in a weighted graph with non-negative edge weights.
• Maintains a set of visited vertices $S$ and updates tentative distance estimates $d(v)$ for all unvisited neighbors:
  $$d(v) = \min(d(v), d(u) + w(u, v))$$

---

2. Step-by-Step Trace from Source $A$:

• Initialization: $d(A) = 0$; $d(B) = \infty, d(C) = \infty, d(D) = \infty, d(E) = \infty$. Visited set $S = \emptyset$.

• Iteration 1: Select unvisited vertex with minimum distance: Vertex $A$ ($d=0$). Add $A$ to $S$: $S = \{A\}$. Update neighbors of $A$:

  • $d(B) = \min(\infty, 0 + 4) = 4$ (via $A$)
  • $d(C) = \min(\infty, 0 + 2) = 2$ (via $A$)

• Iteration 2: Minimum unvisited vertex: Vertex $C$ ($d=2$). Add $C$ to $S$: $S = \{A, C\}$. Update neighbors of $C$:

  • Neighbor $B$: $d(B) = \min(4, 2 + 1) = 3$ (updated via $C$!)
  • Neighbor $D$: $d(D) = \min(\infty, 2 + 8) = 10$ (via $C$)
  • Neighbor $E$: $d(E) = \min(\infty, 2 + 10) = 12$ (via $C$)

• Iteration 3: Minimum unvisited vertex: Vertex $B$ ($d=3$). Add $B$ to $S$: $S = \{A, C, B\}$. Update neighbors of $B$:

  • Neighbor $D$: $d(D) = \min(10, 3 + 5) = 8$ (updated via $B$!)

• Iteration 4: Minimum unvisited vertex: Vertex $D$ ($d=8$). Add $D$ to $S$: $S = \{A, C, B, D\}$. Update neighbors of $D$:

  • Neighbor $E$: $d(E) = \min(12, 8 + 2) = 10$ (updated via $D$!)

• Iteration 5: Select remaining vertex: Vertex $E$ ($d=10$). $S = \{A, B, C, D, E\}$. All vertices visited.

---

3. Shortest Paths and Distances from $A$:

• To $B$: Path $A \to C \to B$, Distance = 3
• To $C$: Path $A \to C$, Distance = 2
• To $D$: Path $A \to C \to B \to D$, Distance = 8
• To $E$: Path $A \to C \to B \to D \to E$, Distance = 10

Boolean Algebra and De Morgan’s Laws

1. Definition of Boolean Algebra

A Boolean algebra is an algebraic structure $(B, +, \cdot, ', 0, 1)$ consisting of a set $B$ with two binary operations $+$ (OR), $\cdot$ (AND), a unary operation $'$ (NOT), and two special elements 0 and 1, satisfying:

1. Closure under $+$ and $\cdot$
2. Commutative laws: $x + y = y + x$ and $x \cdot y = y \cdot x$
3. Associative laws: $(x + y) + z = x + (y + z)$ and $(x \cdot y) \cdot z = x \cdot (y \cdot z)$
4. Distributive laws: $x \cdot (y + z) = (x \cdot y) + (x \cdot z)$ and $x + (y \cdot z) = (x + y) \cdot (x + z)$
5. Identity laws: $x + 0 = x$ and $x \cdot 1 = x$
6. Complement laws: $x + x' = 1$ and $x \cdot x' = 0$

---

2. De Morgan’s Laws

1. First Law: $(x + y)' = x' \cdot y'$ (The complement of a sum equals the product of the complements).
2. Second Law: $(x \cdot y)' = x' + y'$ (The complement of a product equals the sum of the complements).

---

3. Truth Table Verification

Columns 6 and 7 are identical, proving $(x + y)' = x' \cdot y'$. Columns 9 and 10 are identical, proving $(x \cdot y)' = x' + y'$.

Comprehensive Case Analysis Solution

a) Kruskal’s Algorithm for Minimum Spanning Tree (MST)

A graph with $V = 6$ vertices requires an MST with exactly $V - 1 = 5$ edges.

1. Sort all candidate edges in non-decreasing order of cost:

   • $(v_2, v_4) = 15$
   • $(v_5, v_6) = 18$
   • $(v_1, v_2) = 20$
   • $(v_4, v_5) = 22$
   • $(v_1, v_4) = 28$
   • $(v_2, v_5) = 30$
   • $(v_1, v_3) = 35$
   • $(v_3, v_4) = 40$

2. Step-by-Step Edge Selection:

   • Edge 1: Pick $(v_2, v_4)$ with weight 15. Connects $\{v_2, v_4\}$. No cycle. (Accepted)
   • Edge 2: Pick $(v_5, v_6)$ with weight 18. Connects $\{v_5, v_6\}$. No cycle. (Accepted)
   • Edge 3: Pick $(v_1, v_2)$ with weight 20. Connects $\{v_1, v_2, v_4\}$. No cycle. (Accepted)
   • Edge 4: Pick $(v_4, v_5)$ with weight 22. Connects $\{v_1, v_2, v_4, v_5, v_6\}$. No cycle. (Accepted)
   • Next edge in list: $(v_1, v_4) = 28$. Vertices $v_1$ and $v_4$ are already in the same component $\{v_1, v_2, v_4\}$. Adding creates cycle $(v_1-v_2-v_4-v_1)$. (Rejected)
   • Next edge: $(v_2, v_5) = 30$. Both in same component. Forms cycle. (Rejected)
   • Edge 5: Pick $(v_1, v_3)$ with weight 35. Connects $v_3$ to component. No cycle. (Accepted)

All 6 vertices are connected with 5 edges.

3. Total Minimum Laying Cost:
   $$\text{Cost} = 15 + 18 + 20 + 22 + 35 = \text{Rs. } 110 \text{ Million}$$

---

b) Prim’s Algorithm Starting at Kathmandu ($v_1$)

• Initial tree $T = \{v_1\}$.
• Step 1: Incident edges from $\{v_1\}$: $(v_1, v_2) = 20$, $(v_1, v_4) = 28$, $(v_1, v_3) = 35$. Minimum edge: $(v_1, v_2)$ with weight 20. $T = \{v_1, v_2\}$.
• Step 2: Incident edges from $\{v_1, v_2\}$ to unvisited: $(v_2, v_4) = 15$, $(v_1, v_4) = 28$, $(v_2, v_5) = 30$, $(v_1, v_3) = 35$. Minimum edge: $(v_2, v_4)$ with weight 15. $T = \{v_1, v_2, v_4\}$.
• Step 3: Incident edges from $\{v_1, v_2, v_4\}$ to unvisited: $(v_4, v_5) = 22$, $(v_2, v_5) = 30$, $(v_1, v_3) = 35$, $(v_4, v_3) = 40$. Minimum edge: $(v_4, v_5)$ with weight 22. $T = \{v_1, v_2, v_4, v_5\}$.
• Step 4: Incident edges from $\{v_1, v_2, v_4, v_5\}$ to unvisited: $(v_5, v_6) = 18$, $(v_1, v_3) = 35$, $(v_4, v_3) = 40$. Minimum edge: $(v_5, v_6)$ with weight 18. $T = \{v_1, v_2, v_4, v_5, v_6\}$.
• Step 5: Incident edges to remaining unvisited vertex $\{v_3\}$: $(v_1, v_3) = 35$, $(v_4, v_3) = 40$. Minimum edge: $(v_1, v_3)$ with weight 35. $T = \{v_1, v_2, v_4, v_5, v_6, v_3\}$.

Verification: Edges selected by Prim: $\{(v_1, v_2), (v_2, v_4), (v_4, v_5), (v_5, v_6), (v_1, v_3)\}$. Total cost $= 20 + 15 + 22 + 18 + 35 = \text{Rs. } 110 \text{ Million}$ (Matches Kruskal’s exact tree!).

---

c) Relational Algebra Formulation

Given schemas:

• $R(\underline{\text{CustID}}, \text{Name}, \text{PlanID})$
• $S(\underline{\text{PlanID}}, \text{PlanName}, \text{MonthlyFee})$

The relational algebra expression:

$$\pi_{\text{Name}, \text{PlanName}} \Big( R \bowtie \sigma_{\text{MonthlyFee} > 1,000}(S) \Big)$$

Operational Steps:

1. Selection ($\sigma_{\text{MonthlyFee} > 1,000}(S)$): Filters rows in relation $S$ where the monthly fee exceeds Rs. 1,000.
2. Natural Join ($\bowtie$): Joins filtered plans with customer records $R$ on the common attribute $\text{PlanID}$.
3. Projection ($\pi_{\text{Name}, \text{PlanName}}$): Extracts only the customer Name and PlanName attributes in the final result relation.