MU Computer Engineering (Semester 3)
Discrete Structures
December 2011
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

1(a) A survey on a sample of 25 new cars being sold of a local auto dealer was conducted to see which of three popular options, air conditioning A , radio R and popular window W, were already installed. The survey found,
15 had Air conditioning,
12 had radio,
11 had power window,
5 had air conditioning and power window,
9 had air conditioning and radio,
4 had radio and power window,
3 had all three option,
2 had no option
Find the number of cars having:
(i) Only one of these option
(ii) Radio and power window but not the air conditioning
(iii) None of these option.
6 M
1(b) Explain the following terms with suitable example:
(i) Disjoint set
(ii) Symmetric difference
(iii) Partition set
(iv) Cartesian product
4 M
1(c) Given A={1,2,3,4} and B={x,y,z}. Let R be the following relation from A to B
R={(1,y), (1,z), (3,y), (4,x), (4,z)}
(i) Determine the matrix of relation
(ii) Draw the arrow diagram of R
(iii) Find the inverse relation R-1 of R
(iv) Determine the domain and the range of R
6 M
1(d) Prove by the mathematical induction that 6(n+2) + 7(2n+1) is divisible by 43 for each +ve integer n
4 M

2(a) Write English sentence for following where P(x): X is even, Q(x): X is prime, R(x,y): X+Y is even:
(i) ? x ? y R(x, y)
(ii)? x ? y R(x, y)
(iii) ~(? x P(x))
(iv) ~(? x Q(x))
(v) ? x ? y R(x, y)
(vi) ? x ? y R(x,y)
(vii) ? x (~Q(x))
7 M
2(b) Show that if 30 dictionaries in a library containing total of 61,327 pages, then one of the dictionary must have at least 2045 pages.
6 M
2(c) Let G={0,1,2,3,4,5}
(i) Prepare composition table with respect to '+6'
(ii) Prove that G is an abelain group with respect to '+6'
(iii) Find the inverse of 2,3,5
(iv) Is it cyclic?
(v) Find the order of 2,3 and the subgroup generated by these elements.
7 M

3(a) Determine whether the following graphs are isomorphic:

6 M
3(b) (x1 ? x2) ? (x1 ? x3) ? (x2 ? x3) be the Boolean expression. Write E(x1,x2,x3) in disjunctive and conjunctive normal forms.
7 M
3(c) f:R ? R is defined as f(x)=x3
g:R ? R is defined as g(x)=4x2+1
h:R ? R is defined as H(x)=7x-1
Find the rule of defining (hog)of, go(hof)
7 M

4(a) Explain the Eulerian and Hamiltonian path and circuit with suitable example
6 M
4(b) What is the hamming distance? Consider (3,8) encoding function e: B3 ? B8 defined by
and let d be the (8,3) maximum likelihood decode function associated with e. How many errors can (e,d) correct?
7 M
4(c) Determine whether D625 is a Boolean algebra. Justify your answer
7 M

5(a) A function f:R-{7/3} ? R-{4/3} is defined as: f(x)=(4x-5)/(3x-7). Prove that 'f' is bijective and find the rule for f-1
7 M
5(b) Let A={1,2,3,4,6} and R be the relation on A defined by "x divides y" written x/y.(Note x/y if there exists an integer z such that xz=y)
(i)Write R as a set of ordered pairs.
(ii)Draw its directed graph.
(iii)Find the inverse relation of R.
6 M
5(c) Let A={11,12,13,14} and let R={(11,12), (12,13), (13,14), (12,11)}. Find the transitive closure of R using Warshall's algorithm.
7 M

6(a) Let R be the following equivalence relation on the set A={1,2,3,4,5,6}
R={(1,1), (1,5), (2,2), (2,3), (2,6), (3,2), (3,3), (3,6), (4,4), (5,1), (5,5), (6,2), (6,3), (6,6) }
Find the partition of A induced by R, i.e, find the equivalence classes of R.
6 M
6(b) Define a lattice. Let X={1,3,5,15,30,60,90,180} with the relation of divisibility. Draw the harse diagram for it. Whether it is a lattice? Justify your answer. Find the complement of all the elements.
7 M
6(c) Determine the sequence whose recurrence relation is an=4an-1+5an-2With a1=2 and a2=6
7 M

7(a) Explain various operations on binary trees.
6 M
7(b) Show that (P?Q) ? ~(~P?{~Q?~R}) ? (~P?~Q) ? (~P?~R) is tautology (use law of logic). Define universal and existential quantifier with suitable example.
7 M
7(c) Define a ring and field. Let R={0,2,4,6,8}. Show that R is a commutative ring under addition and multiplication modulo 10. Verify whether it is a field or not.
7 M

More question papers from Discrete Structures