STUPIDSID
Solve any one question from Q1 and Q2
1 (a)
By using mathematical induction, prove that \[ \dfrac {1}{1\times 4}+ \dfrac {1}{4 \times 7}+\dfrac {1}{7 \times 10} + \cdots + \dfrac {1}{(3n-2)(3n+1)}=\dfrac {n}{3n+1} \] where n≥1.
6 M
1 (b)
Let A = {a, b, c, d}, Let R be a relation on set A described as R = {(a,d), (b,a), (b, d), (c, b), (c, d), (d, c)}
Find transitive closure of R using Warshall's algorithm.
6 M
2 (a)
By using law of set, prove that \( (A\cap \overline B) \cup (\overline A \cap B) \cup (\overline A \cap \overline B) = \overline A \cup \overline B. \)
6 M
2 (b)
Find the homogeneous solution for the recurrence relation
an=(2an)-1-an-2 if a1=1.5, a2=3.
an=(2an)-1-an-2 if a1=1.5, a2=3.
6 M
Solve any one question from Q3 and Q4
3 (a)
Define Hamming distance. Given the parity check matrix. \[ H=\begin{bmatrix}
1 &1 &0 &1 &0 &0 \\0
&1 &1 &0 &1 &0 \\1
&0 &1 &0 &0 &1
\end{bmatrix} \]
Calculate the minimum distance of code generated by H. How many errors can it detect and correct?
Calculate the minimum distance of code generated by H. How many errors can it detect and correct?
6 M
3 (b)
Find the shortest path from a to z using Dijkstra's Algorithm.
6 M
4 (a)
What is monoid? Show that the algebraic system (A, +) is a monoid, where A is set of integers and + is a binary operation giving addition of two integers.
3 M
4 (b)
Define ring homomorphism and ring isomorphism.
3 M
4 (c)
Define graph colouring.
2 M
4 (d)
Find the Hamiltonian circuit using nearest neighbourhood method, starting from vertex a. Find its weight.
4 M
Solve any one question from Q5 and Q6
5 (a)
For the following tree find the nodes traversed using preorder, inorder and postorder traversal.
7 M
5 (b)
Find the minimum spanning tree for the graph G using Prim's algorithm and find its minimum weight.
6 M
6 (a)
Find the minimum spanning tree for the graph shown in Fig 4 using Krushkal's algorithm. Find its minimum weight also.
6 M
6 (b)
Find the optimal prefix code tree for the following data 1, 2, 4, 6, 8, 9, 10, 12 obtain the optimal prefix code for each weight.
7 M
Solve any one question from Q7 and Q8
7 (a)
Suppose repetitions are not allowed, how many 4 digit numbers can be formed from six digits 1, 2, 3, 5, 7, 8?
Also find
i) How many of these numbers are less than 4000?
ii) How many of these numbers are even?
iii) How many of these numbers are odd?
iv) How many of these numbers contain both 3 and 5?
Also find
i) How many of these numbers are less than 4000?
ii) How many of these numbers are even?
iii) How many of these numbers are odd?
iv) How many of these numbers contain both 3 and 5?
8 M
7 (b)
In how many ways the letters in the word MISSISSIPPI can be arranged?
5 M
8 (a)
Determine the probability P of each event
i) An even number appears in the toss of fair die?
ii) One or more heads appear in the toss of three fair coins?
iii) Red marble appears in random drawing of one marble from a box containing 4 white, 3 red and 5 blue marbles.
i) An even number appears in the toss of fair die?
ii) One or more heads appear in the toss of three fair coins?
iii) Red marble appears in random drawing of one marble from a box containing 4 white, 3 red and 5 blue marbles.
6 M
8 (b)
In how many ways can 3 prizes be distributed among 4 winners so that not one gets more than one prize.
3 M
8 (c)
In how many ways can ten examination papers be arranged so that best and worst are never together.
4 M
More question papers from Discrete Structures