SPPU Information Technology (Semester 3)
Discrete Structures
May 2017
Total marks: --
Total time: --
(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 M
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?
3 M
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?
3 M

2(a) Prove by induction that the sum of the cubes of three consecutive integers is divisible by 9.
6 M
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.
4 M
2(c) Three unbiased coins are tossed. What is the probability of getting at most two heads?
2 M

Solve any one question from Q.3(a,b) &Q.4(a,b)
3(a) Solve the following recurrence relation:\[\begin{align*}&a_{r}-7a_{r}-1+10a_r-2=2^{r}\\ &a_{1}=3,a_{2}=21. \end{align*}\]
6 M
3(b) Find the shortest path from vertex a to z in the following graph:
6 M

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 M
4(b) Define Isomorphic Graphs. Show that the following graphs G1 and G2 are isomorphic.
6 M

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.
7 M
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 M

6(a) Find the maximum flow for the following transport network.
7 M
6(b) Find the fundamental system cut set of graph G shown belo with respect to the spanning tree T.
6 M

Solve any one question from Q.7(a,b) &Q.8(a,b)
7(a) Let Q1 be the set of all rational numbers other than 1. Show that with operation * defined on the set Q1 by (a * b = a + b - ab ) is an Abelian group.
7 M
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 M

8(a) Let Zn be the set of integers {0, 1, 2, ........., n-1}. Let ⨁ be n binary operation on Zn 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.
7 M
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 M

More question papers from Discrete Structures