AMIETE – CS (OLD SCHEME)

 

Flowchart: Alternate Process: DECEMBER 2009Code: AC10                                                                         Subject: DISCRETE STRUCTURES

Time: 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.   How many number of rows are there in the truth table for a compound proposition with 20 variables?

                  

                   (A) 220                                                (B) 210

                   (C) 219                                                (D) none

 

             b.   The number of permutations of {a,b,c,d,e,f,g} ending with a are

 

                   (A) 600                                               (B) 720

                   (C) 560                                               (D) none

 

             c.   f(x) = log (x+) is

 

                   (A) Even function                                 (B) Odd function

                   (C) Periodic function                            (D) None

 

             d.   The number of edges in a Tree with n vertices are

                   (A) n                                                   (B) n–1

                   (C) n–2                                               (D) none

 

             e.   A relation that is reflexive, symmetric and transitive is a

                  

                   (A) function                                         (B) partial order

                   (C) equivalence relation                       (D) none

 

             f.    Which value of the Boolean variables x and y satisfy xy=x+y

 

                   (A) (1,1)                                             (B) (0,1)

                   (C) (1,0)                                             (D) None

 

             g.   The String 11101 is in the set

 

                   (A) {1}*{0}*{1}*                              (B) {1}*{0}*{0}*

                   (C) {1}*{1}*{1}*                              (D) None

 

            


 

h.   A path in a graph G is called an Euler path if it includes every edge

 

                   (A) Once                                             (B) Twice

                   (C) Thrice                                           (D) None

 

             i.    The set of Intelligent students in a class is

 

                   (A) null set                                           (B) finite set

                   (C) singleton set                                   (D) not a well defined collection.

 

             j.    The number of non-negative integral solutions to x+y+z+w=20 is

 

                   (A) 882                                               (B) 1771

                   (C) 1770                                             (D) none

 

 

 

Answer any FIVE Questions out of EIGHT Questions.

Each question carries 16 marks.

 

 

  Q.2     a.   Let A = {1,2,4}, B = {2,5,7}, C = {1,3,7}.

                   Show that                                                      (4)

 

             b.   Determine whether a relation R on the set of all web pages is reflexive, symmetric, anti-symmetric, and/or Transitive, where (a,b)  R iff             

                   (i)   Every one who has visited web page a has also visited web page b               (3)

                   (ii)  There are no common links found on both web page a and web page b        (3)

                   (iii) There is at least one common link on web page a and web page b                 (3)

                   (iv) There is a web page that includes links to both web page a and web page b                 (3)

 

  Q.3     a.   let Q be the set of rational numbers and f: QQ be defined by f(x) = ax+b (a0). Show that f is bijective. Also find a formula that defines the inverse function f–1                                                        (8)

 

             b.   Write Fleury’s algorithm in pseudocode.                                                             (8)

 

  Q.4     a.   Define Hasse diagram. Draw the Hasse diagram for the partial ordering {(A,B):AB} on the power set P(S), where S={1,2,3}                        (8)

 

             b.   Show that the relation R on ZZ defined by (a,b)R(c,d) iff a+d=b+c is an equivalence relation.                                                                 (8)

                                                                       

  Q.5     a.   Define Moore Machine and Mealy Machine.                                                      (6)

 

             b.   Write an algorithm/ method to find the second minimum spanning tree of a graph.                (10)

 

  Q.6     a.   Let G=(V,T,S,P) be the phrase structure grammar with V={0,1,A,B,S}, T={0,1}, and the set of production rules P consisting of S0A, S1A, A0B, B1A, B1.                                       (8)

 

                   (i)   Show that 10101 belongs to the language generated by G.

                   (ii)  Show that 10110 does not belong to the language generated by G.

 

             b.   A farmer buys 4 cows, 3 goats and 2 hens from a man who has 6 cows, 5 goats and 7 hens. How many choices does the farmer has?                (8)

 

 

  Q.7     a.   Show that (pq)(pq) is a tautology                                                           (8)

 

             b.   Prove that if n is a positive integer, then n is odd iff 5n+6 is odd.                          (8)

 

  Q.8     a.   Compute A(2,1) where A:NNN is defined by                                            (8)

 

                                        A(0,y)=y+1

A(x+1,0)=A(x, 1)

A(x+1,y+1)=A(x+1,y)

 

b.  Prove that a simple graph is connected iff it has a spanning Tree.                          (8)

            

  Q.9     a.   How can you obtain NAND gate using NOR gates only.                                    (8)

 

             b.   Show that a positive logic NAND gate is equivalent to negative logic NOR gate.                (8)