Discrete Structures Question Paper - May 2017 - Information Technology (Semester 3)

4views

written 5.8 years ago by

Discrete Structures - May 2017

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 Q.1(a,b,c) &Q.2(a,b,c)

1(a) Out of a total of 130 students, 60 are wearing hats, 51 are wearing scarves, and 30 wearing both hats and scarves. Out of 54 students who are wearing sweaters, 26 are wearing hats, 21 are wearing scarves, snd 12 are wearing both hats and scarves. Everyone wearing neither a hat nor a scarf is wearing gloves:
a) How many students are wearing gloves?
b) How many students not wearing a sweater are wearing hats but not scares?
c) How many students not wearing a sweater are wearing neither hat nor a scarf? 6 marks

1(b) Tickets numbered 1 to 20 are mixed up and then a ticket is drawn at random. What is the probability that the ticket drawn has a number which is the multiple of 3 or 5? 6 marks

1(c) In a box, there are 8 red, 7 blue and 6 green balls. One ball is picked up randomly. What is the probability that it is neither red nor green? 6 marks

2(a) Prove by induction that the sum of the cubes of three consecutive integers is divisible by 9. 6 marks

2(b) Two cards are drawn together from a pack of 52 cards. Determine the probability that one is a spade and one is a heart. 6 marks

2(c) Three unbiased coins are tossed. What is the probability of getting at most two heads? 6 marks

Solve any one question from Q.3(a,b) &Q.4(a,b)

3(a) Solve the following recurrence relation:

<mtable columnalign="right left right left right left right left right left right left" rowspacing="3pt" columnspacing="0em 2em 0em 2em 0em 2em 0em 2em 0em 2em 0em" displaystyle="true"><mtr><mtd ></mtd><mtd><msub><mi>a</mi><mrow class="MJX-TeXAtom-ORD"><mi>r</mi></mrow></msub><mo>-</mo><mn>7</mn><msub><mi>a</mi><mrow class="MJX-TeXAtom-ORD"><mi>r</mi></mrow></msub><mo>-</mo><mn>1</mn><mo>+</mo><mn>10</mn><msub><mi>a</mi><mi>r</mi></msub><mo>-</mo><mn>2</mn><mo>=</mo><msup><mn>2</mn><mrow class="MJX-TeXAtom-ORD"><mi>r</mi></mrow></msup></mtd></mtr><mtr><mtd ></mtd><mtd><msub><mi>a</mi><mrow class="MJX-TeXAtom-ORD"><mn>1</mn></mrow></msub><mo>=</mo><mn>3</mn><mo>,</mo><msub><mi>a</mi><mrow class="MJX-TeXAtom-ORD"><mn>2</mn></mrow></msub><mo>=</mo><mn>21.</mn></mtd></mtr></mtable></math>" role="presentation" style="font-size: 125%; text-align: center; position: relative;"> \begin{matrix} a_{r} - 7 a_{r} - 1 + 10 a_{r} - 2 = 2^{r} a_{1} = 3, a_{2} = 21. \end{matrix}

3(b) Find the shortest path from vertex a to z in the following graph:
!mage 6 marks

4(a) Functions f, g and h are defined on the set X= {1, 2, 3 } as:
f = {(1, 3), (2, 1), (3, 2)};
g = {(1, 2), (2, 3), (3, 1) };
h {(1, 2), (2, 1), (3, 3)}
i) Find fog and gof . Are the equals?
ii) Find fogoh and fohog. 6 marks

4(b) Define Isomorphic Graphs. Show that the following graphs G1 and G2 are isomorphic.
!mage 6 marks

Solve any one question from Q.5(a,b) &Q.6(a,b)

5(a) Find the minimum spanning tree and weight of it for the given graph using Kruskal's algorithm.
!mage 6 marks

5(b) Define optimal tree. For the following set of weights, construct optimal binary prefix code. For each weight in the set, give corresponding prefix code:
1, 4, 8, 9, 15, 25, 31, 37. 6 marks

6(a) Find the maximum flow for the following transport network.
!mage 6 marks

6(b) Find the fundamental system cut set of graph G shown belo with respect to the spanning tree T.
!mage 6 marks

Solve any one question from Q.7(a,b) &Q.8(a,b)

7(a) Let Q₁ be the set of all rational numbers other than 1. Show that with operation * defined on the set Q₁ by (a * b = a + b - ab ) is an Abelian group. 6 marks

7(b) Let I be the set of all integers. For each of the following determine whether * is an associative operation of not:
i) a * b = max (a, b)
2) a * b = min ( x + 2, b)
3) a * b = a- 2b
4) a * b = max (2a - b, 2b - a). 6 marks

8(a) Let Z_n be the set of integers {0, 1, 2, ........., n-1}. Let ⨁ be n binary operation on Z_n such that: ( \begin{align*}a\bigoplus b=\left{\begin{matrix} a+bifa+b/ Let ⨀ be a binary operation on Zn such that: a⨀b = the remainder of ab divided by n. 6 marks

8(b) Consider the (2, 7) encoding function e.
e (00) = 000000 e(01) = 1010101
e(10) = 0111110 e(11) = 0110110
a) Find the minimum distance of e.
b) How many errors will e detect? 6 marks

ADD COMMENT EDIT