MTH202 Discreat Mathematics Solved Final Term Past Paper

FINALTERM  EXAMINATION

Fall 2008

MTH202- Discrete Mathematics (Session - 3)

Time: 120 min

Marks: 70

http://www.allvupastpapers.blogspot.com/

Question No: 1    ( Marks: 1 )    - Please choose one

 When 5^k is even, then 5^k+5^k+5^k is odd.

       ► True

       ► False

   

Question No: 2    ( Marks: 1 )    - Please choose one

 An arrangement of objects without the consideration of order is called

       ► Combination

       ► Selection

       ► None of these

       ► Permutation

   

Question No: 3    ( Marks: 1 )    - Please choose one

 In the following graph

            

                              http://www.allvupastpapers.blogspot.com/

How many simple paths are there from   to 

       ► 2

       ► 3

       ► 4

   

Question No: 4    ( Marks: 1 )    - Please choose one

 Changing   rows of matrix into columns is called

       ► Symmetric Matrix

       ► Transpose of Matrix

       ► Adjoint of Matrix

   

Question No: 5    ( Marks: 1 )    - Please choose one

                      The list of the degrees of the vertices of graph in non increasing order is called

http://www.allvupastpapers.blogspot.com/

       ► Isomorphic Invariant

       ► Degree Sequence

       ► Order of Graph

   

Question No: 6    ( Marks: 1 )    - Please choose one

 A vertex of degree greater than 1 in a tree is called a

       ► Branch vertex

       ► Terminal vertex

       ► Ancestor

   

Question No: 7    ( Marks: 1 )    - Please choose one

 The word "algorithm" refers to a step-by-step method for performing some action

       ► True

       ► False

       ► None of these

http://www.allvupastpapers.blogspot.com/

   

Question No: 8    ( Marks: 1 )    - Please choose one

 The sum of two irrational number must be an irrational number

       ► True   

       ► False

   

Question No: 9    ( Marks: 1 )    - Please choose one

 An integer n is prime if, and only if, n > 1 and for all positive integers r and s, if

    n = r·s, then

       ► r = 1 or s = 1.

       ► r = 1 or s = 0.

       ► r = 2 or s = 3.

       ► None of these

   

Question No: 10    ( Marks: 1 )    - Please choose one

 An integer n is even if, and only if, n = 2k for some integer k.

       ► True

       ► False

       ► Depends on the value of k

http://www.allvupastpapers.blogspot.com/

   

Question No: 11    ( Marks: 1 )    - Please choose one

 For any two sets A and B,  A – (A – B) =

       ► A Ç B

       ► A È B

       ► A – B

       ► None of these

   

Question No: 12    ( Marks: 1 )    - Please choose one

 A walk that starts and ends at the same vertex is called

       ► Simple walk

       ► Circuit

       ► Closed walk      

   

Question No: 13    ( Marks: 1 )    - Please choose one

 Associative law of union for three sets is

       ► A È (B È C) = (A È B) È C

http://www.allvupastpapers.blogspot.com/

       ► A Ç (B Ç C) = (A Ç B) Ç C

       ► A È (B Ç C) = (A È B) Ç  (A È B)

       ► None of these

   

Question No: 14    ( Marks: 1 )    - Please choose one

 Two distinct edges with the same set of end points are called

►Isolated

►Incident

►Parallel

   

Question No: 15    ( Marks: 1 )    - Please choose one

 The probability of getting 2 heads in two successive tosses of a balanced coin is

►

►

►

  http://www.allvupastpapers.blogspot.com/

 

Question No: 16    ( Marks: 1 )    - Please choose one

 What is the probability of getting a number greater than 4 when a die is thrown?

►

►

►

   

Question No: 17    ( Marks: 1 )    - Please choose one

 If two relations are reflexive then their composition is

       ► Antisymmetric

       ► Reflexive

  http://www.allvupastpapers.blogspot.com/

     ►  Irreflexive

       ►  Symmetric

   

Question No: 18    ( Marks: 1 )    - Please choose one

 If p and q are statement variables, the biconditional of p and q is

denoted by

       ► p«q

       ► ~q ®~p

       ► ~p ®~q

       ► None of these

   

Question No: 19    ( Marks: 1 )    - Please choose one

 Select the correct one

  http://www.allvupastpapers.blogspot.com/

     ► A proof by contradiction is based on the fact that a statement can be  true and false at the

same time.

       ► A proof by contraposition is based on the logical equivalence between a statement and its contradiction. 

       ► The method of loop invariants is used to prove correctness of a loop without any conditions.

       ► None of the given choices

   

Question No: 20    ( Marks: 1 )    - Please choose one

 According to Demorgan’s law

       ►

       ►   

       ►

       ►

   

Question No: 21    ( Marks: 2 )

 Find integers q and r so that a=bq+r , with 0≤r<b.

a=45 , b=6.

Ans:   www.allvupastpapers.blogspot.com

If a =45 and b = 6 are two integers with  b 0  such that the q and r are non negitive integers.

a=bq+r           

divides 45 by 6 

            this gives= 6.7 +3

divides 6 by  3

            this gives  = 3.2 +0

hence gcd of the (45,6 ) will be 3

   

Question No: 22    ( Marks: 2 )

 Give the degree of each vertex in the figure (given below)    

           www.allvupastpapers.blogspot.com

                              

Ans:     degree of A vertex = 1

            Degree of B vertex = 3

            Degree of C vertex = 3

            Degree of D vertex = 1

 Total degree of   vertices   = 8

Can be prove by formula

Degree of vertices = 2. no. of edges

                              =   2 . 4

                                =   8                                                    

   

Question No: 23    ( Marks: 2 )

 What is the probability of getting a number greater than 2 when a dice is tossed?

As dice has 6 sides so possible event will be 36.

No. greater than 2 will be

3 ,4 ,5 ,6  =  18

P(E) =n(E)/(n(S))

            = 18/36

 

            =   ½   will be the possibility to get no greater than 2       

Question No: 24    ( Marks: 3 )

 How many distinguishable ways can the letters of the word HULLABALOO be arranged if words are to begin with U and end with L

www.allvupastpapers.blogspot.com

   

Question No: 25    ( Marks: 3 )

 Write the Pre and Post Conditions of the

"Algorithm to compute a product of two negative integers".

Ans:

Pre condition: The input variables m and n are nonnegative integers.

Post condition:   the out put variables p equals m.n.

Example:

If, then extends to all n.
extends to k < 0 via

  www.allvupastpapers.blogspot.com

 

Question No: 26    ( Marks: 3 )

 Draw a full binary tree with seven vertices.

                                                           

www.allvupastpapers.blogspot.com

   

Question No: 27    ( Marks: 5 )

 Find n if

      P(n,2) = 72

Given

P(n,2) = 72

n.(n-1)=72  by using the definition of permutation

n2-1=72

n2-n-72=0

n=9,-8 since n must be positive so only the acceptable value for n is 9

   

Question No: 28    ( Marks: 5 )

 Five people are to be seated around a circular table. Two seating plans are considered as same if one is the rotation of other. How many different seating plans are possible?

   

Question No: 29    ( Marks: 5 )

 Use Kruskal’s Algorithm to draw the minimal spanning tree for the graph below. Indicate the order in which edges are added to form a tree.

 www.allvupastpapers.blogspot.com

   

Order of adding the edges:

{v3,v6},{v1,v2},{v4,v5},{v2,v3},{v2,v4},.

www.allvupastpapers.blogspot.com

Question No: 30    ( Marks: 10 )

 Show the sample space for tossing one penny and rolling one die.
 (H = heads, T = tails) using tree diagram

www.allvupastpapers.blogspot.com

   

Question No: 31    ( Marks: 10 )

 , is divisible by 7 for all n>=1

Let   is divisible by 7

Basis step:

            P(1) is true.now

P(1):  

www.allvupastpapers.blogspot.com

                                                                                                                                     

103n +13 n+1    is divisible by 7

Since 103.1+13 1+1 = 10(3)+132   

Which is divisible by 7

Hence P(1) is true.now

  Inductive step:

Suppose p(k is true)

103k +13 k+1    = 7.q

To prove p(k+1) 103n +13 n+1     is true is divdsible by 7

103k+1 + 13 k+1+1    = 234k+3

                                                =  234k+3   +2 -2

                                    =214k+3 +2

                                    =7.34k+3  +2

                                    = 7(34k+3  +2)

                                    =7. q   where q is ant positive integer equal to 34k+3  +2

So itwww.allvupastpapers.blogspot.com

s proved that  divisible by 7 for all n>=1

By ADEEL ABBAS, Bhakkar. AdeelAbbasbk@gmail.com