Flowchart: Alternate Process: DECEMBER 2008Code: 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 best alternative in the following:                                         (2x10)

          

             a.   Let  X and Y be the sets , then the set

                  

 

                   (A)                                           (B) 

                   (C)                                       (D) 

 

             b.   A graph G with n vertices has a Hamiltonian circuit if, for any two vertices u and v of G that are not adjacent, the degree of u plus the degree of v is:

 

                   (A)  Equal to n+1                                (B)  Less than or equal to n

                   (C)  Greater than or equal to n+1         (D)  Greater than or equal to n

 

             c.   FSM (Finite State Machine) can recognize.

 

                   (A)  Only CFG                                    (B)  Any Grammar

                   (C)  Only Regular Grammar                 (D)  Any ambiguous grammar

 

             d.   The number of possible binary trees with 4 nodes is:

 

                   (A)  12                                                (B)  13

                   (C)  14                                                (D)  15

 

             e.   The Boolean expression   is independent of the Boolean variable.

 

                   (A)  X                                                 (B)  Y

                   (C)  Z                                                  (D)  None of the above

 

             f.    In how many ways can you arrange the letters of SUBSET?

 

                   (A)  120                                              (B)  360

                   (C)  420                                              (D)  720

 

             g.   In MCA examination a candidate has to pass in each of six papers. In how many ways can he fail?

 

                   (A)  63                                                (B)  64

                   (C)  60                                                (D)  62

 

 

             h.   Consider the following conditional statement:

                                

                   P: If the flood destroy my house or the fire destroy my house, then my insurance company will pay me.

 

                   Which of the following is the contra positive of p?

 

                    (A)  If my insurance company pays me, then the flood destroys my house or the fire destroys my house.

                    (B)  If my insurance company pays me, then the flood destroys my house and the fire destroys my house.

                    (C)  If my insurance company does not pays me, then the flood  does not destroy my house or the fire does not destroy my house

                    (D)  If my insurance company does not pays me, then the flood  does not destroy my house and the fire does not destroy my house

 

             i.    How many different reflexive, symmetric, relations are there on a set with three elements?

 

                   (A)  22                                                 (B)  23

                   (C)  24                                                 (D)  21

 

             j.    When the compound statement is false for all its components then statement is called:

 

                   (A)  Negation Statement                      (B)  Fallacial Statement

                   (C)  Conjunctive Statement                  (D)  Disjunctive Statement.

 

 

 

Answer any FIVE Questions out of EIGHT Questions.

Each question carries 16 marks.

 

 

  Q.2     a.   In class of 60 boys, 45 boys play cricket and 30 boys play chess. How many boys play both games? How many play cricket only and how many plays chess only?                                                     (8)

 

             b.   Prove that if x is a rational number and y is an irrational number, then x + y is an irrational number.                                                             (8)

 

  Q.3     a.   Design a FA that accept all words that have different first and last letters.            (8)

 

             b.   Draw the simplified logic diagram using NAND gates to implement the three input Function F denoted by the expression:

                                                                                                                 (8)          

 

  Q.4     a.   A truth table has four input variables. The first eight outputs are 0’s, and the last eight outputs are 1’s. Draw the K – map and then simplify it.          (10)

 

             b.   If G is a non-trivial tree then G contains at least 2 vertices of degree 1.                (6)

 

  Q.5     a.   What are context-free, context sensitive and regular grammars?                          (6)

 

             b.   Use Prim’s greedy algorithm to find minimal spanning tree for the graph given below. Use vertex E as the initial vertex and list the edges in the order in which they are chosen.                                   (10)

  

 

  Q.6     a.   Let  L = ( a1,a2,……an) be a finite Lattice. Then prove that L is bounded.         (7)

 

             b.   Draw the diagraph of each of the following relations.

                    (i)    The relation ‘divides’ defined by “ a divides b iff there exists a positive integer c such that a.c = b” on the integers { 1,2,3,4,5,6,7,8 }.

                    (ii)    The relation  on all the nonempty subsets of the set { 0, 1, 2 }.

                    (iii)   The relation ≠ on the set { 0, 1 ,2}                                                             (9)

 

  Q.7     a.   Let B = { 1, 2, 3, 4, 5} , A = B Х B , and define R on A as follows: (u,v) R (x,y) if and only if u – v = x – y.

                   (i) Prove that R is an equivalence relation.

                   (ii) Find [(2,3)].

                   (iii) Compute A/R.                                                                                             (9)

 

                   b.                                                        Let the number of edges in a graph G be m. Then G has Hamiltonian circuit if 

                   m ≥ ½(n2 – 3n + 6)  where n is the number of vertices.                                       (7)

 

  Q.8     a.   Solve S(k) – 4.S(k-1) – 11.S(k–2) + 30.S(k–3) = 0

                   When S(0) = 0, S(1) = –35, S(2) = –85.                                                         (10)

 

             b.   How many ways are there for ten women and six men to stand in a line so that no two men stand next to each other?                                          (6)

 

  Q.9     a.   Prove by induction that for all integers .                                       (8)

 

             b.   Prove that                                                (8)