Monday, May 26, 2014

Discrete Structures (DS) Semester 3 (Revised Course) (3 Hours) May 2012

Discrete Structures

Discrete Structures (DS)
Semester 3 (Revised Course)
(3 Hours) May 2012

 

GN-8699
[Total Marks : 60]
 

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.
 
[ 1 0 0 1 ]
1 1 0 0
0 0 1 0
0 0 0 1
 
       
4. (a) In a survey of 60 people, it was found that
 
  25 read Business indis
26 reads india Today.
26 read Times of india.
11 read both Business india and India Today.
09 read both Business India and Times of India.
08 read both India today and Times of india.
08 read none of the three.
     i) How many read all three?
     ii) How many read exactly one?
 
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
 
e(000) = 00000000 e(100) = 10100100
e(001) = 10111000 e(101) = 10001001
e(010) = 00101101 e(110) = 00011100
e(011) = 10010101 e(111) = 00110001

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

No comments:

Post a Comment