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

(a) State the principle of mathematical induction. Using induction, prove that for every positive integer $n$,

(6)

(b) Solve the recurrence relation $a_n = 5a_{n-1} - 6a_{n-2}$ for $n \ge 2$, with initial conditions $a_0 = 1$ and $a_1 = 0$. Show all steps including the formation and solution of the characteristic equation. (6)

(a) Define a tautology, a contradiction, and a contingency. Construct a truth table for the compound proposition $(p \rightarrow q) \wedge (q \rightarrow r)$ and determine its type. (5)

(b) Using rules of inference, show that the following argument is valid. State the rule used at each step.

Premises: $p \rightarrow q$, $\neg q \vee r$, $\neg r$. Conclusion: $\neg p$. (4)

(c) Translate the statement "Every student in this class has visited either Pokhara or Lumbini" into a logical expression using quantifiers and predicates, clearly defining the universe of discourse and each predicate. (3)

(a) Define a connected graph, a Hamiltonian circuit, and an Euler circuit. State the necessary and sufficient condition for a connected graph to contain an Euler circuit. (4)

(b) Apply Dijkstra's algorithm to find the shortest path from vertex $A$ to all other vertices of the following weighted graph. Edges and weights: $A$-$B$ = 4, $A$-$C$ = 2, $C$-$B$ = 1, $B$-$D$ = 5, $C$-$D$ = 8, $C$-$E$ = 10, $D$-$E$ = 2, $D$-$Z$ = 6, $E$-$Z$ = 3. Show the table of tentative distances at each iteration. (8)

(a) Let $R$ be a relation defined on the set of integers $\mathbb{Z}$ by $a\,R\,b$ if and only if $a - b$ is divisible by 5. Prove that $R$ is an equivalence relation and describe its equivalence classes. (6)

(b) State and prove the principle of inclusion-exclusion for two finite sets $A$ and $B$. In a survey of 120 students, 70 like tea, 60 like coffee, and 30 like both. How many students like neither tea nor coffee? (6)

(a) Define injective, surjective, and bijective functions with one example of each. (4)

(b) Let $f : \mathbb{R} \rightarrow \mathbb{R}$ be defined by $f(x) = 3x - 7$. Show that $f$ is a bijection and find its inverse function $f^{-1}$. (4)

(a) How many distinct strings can be formed by rearranging the letters of the word "ENGINEERING"? (4)

(b) In how many ways can a committee of 4 members be selected from a group of 7 men and 5 women if the committee must contain at least 2 women? (4)

(a) State the basic postulates of Boolean algebra. Prove the absorption law $x + xy = x$ using the postulates. (4)

(b) Simplify the Boolean function $F(x, y, z) = \sum m(0, 1, 2, 4, 5)$ using a Karnaugh map and draw the resulting logic circuit. (4)

(a) Define an adjacency matrix and an incidence matrix of a graph. Write the adjacency matrix for a simple undirected graph on vertices $\{1,2,3,4\}$ with edges $\{1,2\}, \{2,3\}, \{3,4\}, \{4,1\}, \{1,3\}$. (4)

(b) Determine whether the two given graphs are isomorphic, justifying your answer using graph invariants such as degree sequence and number of edges. (4)

(a) Define a binary search tree. Construct a binary search tree by inserting the following keys in order: 50, 30, 70, 20, 40, 60, 80. (4)

(b) Write the preorder, inorder, and postorder traversals of the binary search tree obtained in part (a). (4)

(a) Set up a recurrence relation for the number of binary strings of length $n$ that do not contain two consecutive 0's, and give the initial conditions. (4)

(b) Using a generating function, or otherwise, find the number of ways to distribute 10 identical chocolates among 3 distinct children so that each child receives at least one chocolate. (4)

(a) For the sets $A = \{1, 2, 3\}$ and $B = \{a, b\}$, list all elements of the Cartesian product $A \times B$ and determine the total number of relations from $A$ to $B$. (4)

(b) Define a partial order relation. Draw the Hasse diagram for the divisibility relation on the set $\{1, 2, 3, 6, 12\}$ and identify the maximal and minimal elements. (4)