STUPIDSID
Solve any one question from Q1 and Q2
1 (a)
Use mathematical induction to show that n2-4n2 is divisible by 3 for all n≥2.
4 M
1 (b)
Negate each of the statement:
∀x, |x|=x.
ii) ∃x, x2 = x.
iii) If there is a riot, then someone is killed.
iv) It is day light and all the people are arisen.
∀x, |x|=x.
ii) ∃x, x2 = x.
iii) If there is a riot, then someone is killed.
iv) It is day light and all the people are arisen.
4 M
1 (c)
Let R=|(a, b), (b, a), (b, d), (c, b), (c, d), (d, c)| use Warshall's algorithm to find the matrix of transitive closure where A=[a, b, c, d].
5 M
2 (a)
Let A, B, C be sets. Under what conditions the following statements are true?
i) (A-B) ∪ (A-C)=A
ii) (A-B) ∪ (A-C)=ϕ.
i) (A-B) ∪ (A-C)=A
ii) (A-B) ∪ (A-C)=ϕ.
2 M
2 (b)
it was found that in the first year computer science class of 80 students, 50 knew COBOL, 55 'C' and 46 PASCAL. It was also known that 37 knew 'C' and COBOL, 28 'C' and PASCAL and 25 PASCAL and COBOL. 7 students however knew none of the language:
i) How many knew all the three languages?
ii) How many knew exactly two languages?
iii) How many knew exactly one language?
i) How many knew all the three languages?
ii) How many knew exactly two languages?
iii) How many knew exactly one language?
6 M
2 (c)
Let A={1, 2, 3, 4, 5, 6, 7, 8, 9, 12, 18, 24} be ordered by the relation x divides y. Show that the relation is partial ordering and draw the Hasse diagram.
5 M
Solve any one question from Q3 and Q4
3 (a)
What is Hamming Distance? Give 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} \] Find minimum distance of code generated by H. How many errors can it detect and correct.
6 M
3 (b)
Use Dijkstra's algorithm to find the shortest path between a and z for Fig. A.
6 M
4 (a)
Define the following terms with suitable example:
i) Homomorphism of Group
ii) Automorphism of Group.
i) Homomorphism of Group
ii) Automorphism of Group.
2 M
4 (b)
Show that (G/N, *) is group.
4 M
4 (c)
Use nearest neighbour method to find the Hamiltonian circuit starting from a in the following graph Fig. B. Find its weight.
6 M
Solve any one question from Q5 and Q6
5 (a)
Define the following terms with reference to tree with example:
i) Eccentricity of a vertex
ii) Cut points
iii) Level and Height of a tree.
i) Eccentricity of a vertex
ii) Cut points
iii) Level and Height of a tree.
6 M
5 (b)
A secondary storage media contains information in files with different formats. The frequency of different types of files is as follows:
Exe(20), bin(75), bat(20), jpeg(85), dat(51), doc(32), sys(26), c(19), cpp(25), bmp(30), avi(24), prj(29), Ist(35), zip(37).
Construct the Huffman code for this.
Exe(20), bin(75), bat(20), jpeg(85), dat(51), doc(32), sys(26), c(19), cpp(25), bmp(30), avi(24), prj(29), Ist(35), zip(37).
Construct the Huffman code for this.
7 M
6 (a)
Obtain the minimum spanning tree using Krushal algorithm for the following graph. Obtain the total cost of minimum spanning tree.
7 M
6 (b)
Find the fundamental system of cut-set for the graph G shown below with respect to the spanning tree T.
(a)
(b)
6 M
Solve any one question from Q7 and Q8
7 (a)
Suppose license plate contains 3 English letters followed by 4 digits:
i) How many different license plates can be manufactured if repetition of letters and digits are allowed?
ii) How many plates are possible if only the letters are repeated?
iii) How many plates are possible if only the digits are repeated?
i) How many different license plates can be manufactured if repetition of letters and digits are allowed?
ii) How many plates are possible if only the letters are repeated?
iii) How many plates are possible if only the digits are repeated?
4 M
7 (b)
Out of 4 officers and 10 clerks, a committee of 2 officers and 3 clerks is to be formed. In how many ways committee can be done if:
i) Any officer and any clerk can be included
ii) A particular clerk must be in committee
iii) A particular officer cannot be in committee.
i) Any officer and any clerk can be included
ii) A particular clerk must be in committee
iii) A particular officer cannot be in committee.
6 M
8 (a)
A student is to answer 10 out of 13 question in an exam:
i) How many choice has he, if he must answer the first or second questions but not both?
ii) How many choices has he, if he must answer exactly three out of first five questions.
i) How many choice has he, if he must answer the first or second questions but not both?
ii) How many choices has he, if he must answer exactly three out of first five questions.
6 M
8 (b)
Three students A, B and C are swimming in the race. A and B have, same probability of winning and each is twice as likely to win as C. Find the probability that:
i) B wins
ii) C wins
iii) B or C wins.
i) B wins
ii) C wins
iii) B or C wins.
6 M
More question papers from Discrete Mathematics