Ask
Login
0
820views
Discrete Structures Question Paper - December 2013 - Information Technology (Semester 3) - Savitribai Phule Pune University (SPPU)
written 5.8 years ago by gravatar for teamques10 teamques10 ★ 64k
ADD COMMENT EDIT
1 Answer
0
5views
written 5.8 years ago by gravatar for teamques10 teamques10 ★ 64k

Discrete Structures - December 2013

SPPU Information Technology (Semester 3)

Total marks: --
Total time: -- INSTRUCTIONS
(1) Assume appropriate data and state your reasons
(2) Marks are given to the right of every question
(3) Draw neat diagrams wherever necessary

Solve any one question from Q1 and Q2

1 (a) By using mathematical induction, prove that 11×4+14×7+17×10+⋯+1(3n−2)(3n+1)=n3n+1<script type="math/tex; mode=display" id="MathJax-Element-1"> \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} </script> where n≥1. 6 marks

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 marks

2 (a) By using law of set, prove that (A∩¯B)∪(¯A∩B)∪(¯A∩¯B)=¯A∪¯B. (A\cap \overline B) \cup (\overline A \cap B) \cup (\overline A \cap \overline B) = \overline A \cup \overline B. 6 marks

2 (b) Find the homogeneous solution for the recurrence relation
an=(2an)-1-an-2 if a1=1.5, a2=3. 6 marks

Solve any one question from Q3 and Q4

3 (a) Define Hamming distance. Given the parity check matrix. H=[110100011010101001]<script type="math/tex; mode=display" id="MathJax-Element-3"> H=\begin{bmatrix} 1 &1 &0 &1 &0 &0 \0 &1 &1 &0 &1 &0 \1 &0 &1 &0 &0 &1 \end{bmatrix} </script>
Calculate the minimum distance of code generated by H. How many errors can it detect and correct? 6 marks

3 (b) Find the shortest path from a to z using Dijkstra's Algorithm.
 6 marks

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. 6 marks

4 (b) Define ring homomorphism and ring isomorphism. 6 marks

4 (c) Define graph colouring. 6 marks

4 (d) Find the Hamiltonian circuit using nearest neighbourhood method, starting from vertex a. Find its weight.
 6 marks

Solve any one question from Q5 and Q6

5 (a) For the following tree find the nodes traversed using preorder, inorder and postorder traversal.
 6 marks

5 (b) Find the minimum spanning tree for the graph G using Prim's algorithm and find its minimum weight.
 6 marks

6 (a) Find the minimum spanning tree for the graph shown in Fig 4 using Krushkal's algorithm. Find its minimum weight also. 6 marks

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. 6 marks

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? 6 marks

7 (b) In how many ways the letters in the word MISSISSIPPI can be arranged? 6 marks

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. 6 marks

8 (b) In how many ways can 3 prizes be distributed among 4 winners so that not one gets more than one prize. 6 marks

8 (c) In how many ways can ten examination papers be arranged so that best and worst are never together. 6 marks

ADD COMMENT EDIT
Please log in to add an answer.