AMIETE – CS (NEW SCHEME)   –   Code: AC65

 

Subject: DISCRETE STRUCTURES

Flowchart: Alternate Process: DECEMBER 2009Time: 3 Hours                                                                                                     Max. Marks: 100

 

 

NOTE: There are 9 Questions in all.

·      Question 1 is compulsory and carries 20 marks. Answer to Q. 1 must be written in the space provided for it in the answer book supplied and nowhere else.

·      Out of the remaining EIGHT Questions answer any FIVE Questions. Each question carries 16 marks.

·      Any required data not explicitly given, may be suitably assumed and stated.

 

 

Q.1       Choose the correct or the best alternative in the following:                                  (210)

       

             a.  is logically equivalent to

 

                  (A)                                             (B)

                  (C)                                           (D)

 

             b. Every odd integer is the

 

                  (A)  difference of two cubes.                

                  (B)  sum of two perfect squares

                  (C)  difference of two perfect squares. 

                  (D)  none of the above.

 

             c.  Let A = {1,2} and B = {a,b} then R = {(1,a),(1,b),(2,a),(2,b)} is a/an

 

                  (A) equivalence relation                        (B) universal relation

                  (C) inverse relation                               (D) power relation

 

             d.  A,B,C throw a fair coin in that order one who throws a head first wins. The probability that A wins is 

 

                  (A) 4/7                                                 (B) 3/7

                  (C) 2/7                                                 (D) 1/7

 

             e.  The number of diagonals that can be drawn in a polygon of n sides is equal to

 

                  (A) n(n-2)/2                                         (B) n(n-3)/2

                  (C) n!/2                                                (D) n(n-1)/2

 

             f.   Let A = Z+, be the set of positive integers, and R be the relation on A defined by a R b if and only if there exist a Z+ such that a = bk. Which one of the following belongs to R?

 

                  (A) (9,198)                                          (B) (16,256)

                  (C) (11,3)                                            (D) (144,12)

 

             g. The number of functions from m element set to n element set is:

 

                  (A) mn                                                  (B) m + n

                  (C) nm                                                  (D) m * n

 

             h.  A function f is invertible iff

 

(A)  f is one to one & onto                     (B) f is one to one                                                 

                  (C) f is onto                                          (D) f is neither one to one nor onto

 

             i.   If n is an integer and n2 is odd, then n is:

 

                  (A) even.                                              (B) odd.

                  (C) even or odd.                                   (D) prime.

 

             j.   In how many ways can a party of 7 persons be arranged around a circular table?

 

                  (A) 6!                                                   (B) 7!

                  (C) 5!                                                   (D) 7

 


Answer any FIVE Questions out of EIGHT Questions.

Each question carries 16 marks.

 


  Q.2     a.   In a survey, 2000 people were asked whether they read India Today or Business Times. It was found that 1200 read India Today, 900 read Business Times and 400 read both. Find how many read at least one magazine and how many read neither?                                                                (8)

                  

             b.   In a university, 60% of the professors are men and 40% are women. It is also found that 50% of the male professors and 60% of the female professors know computer programming. Find the probability that a professor knowing programming is a woman.                                                                     (8)

 

Q.3     a.   Construct truth tables for the following wffs. Note any tautology or contradiction    or contingencies.

                 (i)  (A ® B) « (Ø A Ú B)

(ii) (A Ù B) Ú C ® A Ù (B Ú C)                                                                      (8)

            

             b.   Prove that p®(q®r) and (pÙØr)®Øq are logically equivalent.                          (8)

            

  Q.4     a.   Determine whether the following is a valid argument:

                   I am happy if my program runs. A necessary condition for the program to run is it should be error free. I am not happy. Therefore the program is not error free.                                                            (8)

                  

             b.   Translate the following statements into logical notation. Let the universe of discourse be the real numbers.

(i)                  For any value of x, x2 is non negative.

(ii)                For every value of x, there is some value of y such that

            x.y = 1.

                                       (iii)       There are positive values of x and y such that x.y>0

(iv)       There is a value of x such that if y is positive, then x+y is negative.                   (8)

       

Q.5        a. Prove by mathematical induction the following:

                    12 + 22 + 32 +……n2 = (n(n+1)(2n+1))/6.                                                         (8)

                  

             b.   If AÍC and BÍD, prove that A´BÍC´D                                                         (8)

            

  Q.6     a.   Let a binary operation o is defined on Z by x o y = x + y + 1. Show that (Z, o) is an Abelian group.                                                                      (8)

 

             b.   Let G be the additive group of integers i.e. G={…,-3,-2,-1,0,1,2,3…}. Let H = {…,-9,-6,-3,0,3,6,9,…} be a subgroup of G. Find right cosets of H in G.                                                                             (8)

  Q.7     a.   Let n be a positive integer, prove that “is – congruent – to – mod – n” relation is an equivalence relation on the set of positive integers.                   (8)

 

             b.   Let (A,£) be a lattice with a universal upper and lower bounds 0 and 1. For any element aÎA, prove

aÚ1=1,     aÙ1=a

                   aÚ0=a,      aÙ0=0                                                                                              (8)

                  

  Q.8     a.   Function f,g,h are defined on a set X={1,2,3} as

                   f={(1,2),(2,3),(3,1)}

                   g={(1,2),(2,1),(3,3)}

                   h={(1,1),(2,2),(3,1)}.

(i)                  Find fog, gof. Are they equal?

                        (ii)        Find fogoh and fohog.                                                                       (8)

 

             b.   Let A is a set of all positive real numbers and B is a set of all real numbers. Let f be a function f:A®B defined as f(x)=logex. Show that f is one to one and onto function.                                      (8)

            

  Q.9     a.   Given the parity check matrix

                   Find the minimum distance of the code generated by H. How many errors it can detect and correct?                                                                      (8)

 

             b.   If  is a ring with identity 0 and unit element 1, then prove the following for all elements

(i)            unit element is unique.

(ii)    a . (-b)=(-a) . b= -(a . b)                                                        (8)