Discrete Structures (DS) |
|||||||||||||||||||||
GN-8699 |
|||||||||||||||||||||
N.B: | (1) | Question no.1 is compulsory. | |||||||||||||||||||
(2) | Attempt any four questions out of remaining six questions. | ||||||||||||||||||||
(3) | Assumptions made should be clearly stated. | ||||||||||||||||||||
(4) | Assume any suitable data wherever required but justify the same. | ||||||||||||||||||||
(5) | Figures to the right indicate marks. | ||||||||||||||||||||
(6) | illustrate answer with sketches wherever required. | ||||||||||||||||||||
1. | (a) | Prove that if A ⊆ C and B ⊆ C then A U B ⊆ C. | 05 | ||||||||||||||||||
(b) | Prove that the maximum number of node on level n of a binary tree is 2n where n ≥0. | 05 | |||||||||||||||||||
(c) | Prove that if any 14 integer from 1 to 25 are chosen, then one of them is multiple of another. | 05 | |||||||||||||||||||
(d) | Prove that in any ring (R+.) the additive inverse of each ring element is unique. | 05 | |||||||||||||||||||
2. | (a) | Let Q be the set of positive rational numbers which can be expressed in the form 2a3b. Where a and b are integers, prove that algebraic structure (Q.) is a group. Where. is multiplication operation. | 07 | ||||||||||||||||||
(b) | Determine whether the poset with the following Hasse
diagrams are lattices or not. |
07 | |||||||||||||||||||
(c) | Let R the relation on set of real numbers such that aRb if and only if a-b is an integer. Prove that R is an equivalence relation. | 06 | |||||||||||||||||||
3. | (a) | Find the solution of recurrence relation an=5an-1 - 6an-2 + 7n |
07 | ||||||||||||||||||
(b) | Show that ((PVQ)∧ ⌉(⌉P ∧(⌉QV ⌉ R)) V (⌉P ∧⌉ Q) V (⌉ P ∧⌉ R)) is tautology. | 07 | |||||||||||||||||||
(c) | Let A = {1, 2, 3, 4} for the relation R whose matrix is
given below. Find the matrix of transitive closure using warshall
algorithm.
|
||||||||||||||||||||
4. | (a) | In a survey of 60 people, it was found that
|
08 | ||||||||||||||||||
(b) | Use induction to prove that 7n -1 is divisible by 6 for n = 1, 2, 3,...... |
06 | |||||||||||||||||||
(c) | Let G be the group and let a and b are elements of G then verify that (ab)-1 = b-1a-1 | 06 | |||||||||||||||||||
5. | (a) | Consider (3,8) encoding function e:B3 -.B8 defined by
and let d be the (8,3) maximum likelihood decoding function associated with e. How many errors can (e,d) correct? |
08 | ||||||||||||||||||
(b) | Prove that if (F, + ,.) is a 'field then it is a integral domain. | 06 | |||||||||||||||||||
(c) | A connected planar graph has a 9 vertices having degrees
2, 2, 2, 3, 3, 3, 4, 4, 5. how many edges are there? |
06 | |||||||||||||||||||
6. | (a) | Let G be the group of integers under the operations addition and H be group of all even integers under the operation of addition, show that the function f:G →H is an isomorphism. | 08 | ||||||||||||||||||
(b) | Define Eulerian, Hamilton path and circuit with example. What is the necessary and sufficient condition for eular path and circuit? | 06 | |||||||||||||||||||
(c) | Suppose R and S is the relation from A to B,
then prove that (R∩S)-1 = R-1 ∩ S-1 and (RUS)-1 = R-1 U S -1 |
||||||||||||||||||||
7. | (a) | Consider the chains of chains of divisors of
4 and 9 i.e.L1 = {1, 2, 4} and L2 = {1, 3, 9} and partial ordering relation of division on L1 and L2.Draw the lattice L1 x L2. |
|||||||||||||||||||
(b) | Prove that the set {1, 2, 3, 4, 5, 6} is group under multiplication modulo 7. | 05 | |||||||||||||||||||
(c) | How many paths of length 4 are there from a
to d in simple graph as shown below. |
07 | |||||||||||||||||||
(d) | Find the complement of each element in D20 and D30. | 05 |
Monday, May 26, 2014
Discrete Structures (DS) Semester 3 (Revised Course) (3 Hours) May 2012
Posted by
B.E. Computers, IT Notes/Solved Question papers Mumbai - Free call 022-66752917
at
4:56 AM
Labels:
be engineering,
BE IT 3 semester,
BE IT Information Technology,
BE IT mumbai university,
BE IT Solved papers,
Discrete Structures,
May 2012,
Mumbai university Papers,
Mumbai university Questions papers
Location:
Mulund West, Mumbai, Maharashtra, India
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment