Code: C-10                                                                          Subject: DISCRETE STRUCTURES

Time: 3 Hours                                                                                                     Max. Marks: 100

NOTE: There are 11 Questions in all.

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

· Answer any THREE Questions each from Part I and Part II. Each of these questions carries 14 marks.

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

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

a. The description of the shaded region in the following figure using the

        operations on set is,

(A) 

(B)

(C)

(D)

             b.   A  matrix has an inverse if and only if,  

(A)   x, y, u and v are all nonzeros.       (B) xy - uv  0

(C)  xv - uy 0                                   (D) all of the above.

`           

             c.   If x and y are real numbers then max (x, y) + min (x, y) is equal to  

(A) 2x                                                (B)  2y

(C)  (x+y)/2                                         (D)  x+y

             d.   The sum of the entries in the fourth row of Pascal’s triangle is

(A)  8                                                  (B)  4

(C) 10                                                (D)  16

             e.   In the following graph

                   the Euler path is

(A) abcdef                                         (B)  abcf

(C)  fdceab                                          (D)  fdeabc

             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 = b^k. Which one of the following belongs to R?

(A)  (8, 128)                                      (B) (16, 256)

(C)  (11, 3)                                         (D) (169, 13)                           

             g.   For the sequence defined by the following recurrence relation

, the explicit formula for T_n is

(A) (B)

(C)  (D)

             h.   Which one of the following is not a regular expression?

(A)  (B) 

(C)  (D)

PART I

Answer any THREE Questions. Each question carries 14 marks.

Q.2     a.   A set contains (2n+1) elements.  If the number of subsets of this set which contain at most n elements is 8192.  Find the value of n.                   (7)

     b.   Solve for , the recurrence relation .    (7)

Q.3     a.   Consider an chess board.  It contains sixty-four  squares and one  square.  What is the total number of all the squares for, it contains?                                                    (6)

             b.   Show that the following statements are equivalent:

  n is even integer.

 is an odd integer.

 is an even integer.                                                                            (8)

Q.4     a.   State DeMorgan’s law. Prove it using the truth table.                                          (4)

             b.   Consider the function , where N is the set of natural numbers, defined by . Show that the function f is one-one but not onto.                                                                (6)

             c.   Let T be a binary tree with n vertices. Determine the number of leaf nodes in tree.               (4)

Q.5     a.   Construct the grammar G that generates the language over an alphabet     {0, 1, 2}, and prove that L(G) = .                                     (10)

             b.   Let Q(x,y) denote x + y = 0. Determine the truth values of .                                                                   (4)

  Q.6     a. Let  and be a one-one function where Z is a set of integers and N is a set of natural numbers. Let R be a relation on A defined as under:

 if and only if f (y) = k f (x) where

                   Prove that R is a partial order relation on A.                                                        (8)

b.   A speaks truth in 60% of the cases and B in 90% of the cases.  Find the percentage of cases when they are likely to contradict each other in stating the same fact.                                                         (6)

PART II

Answer any THREE Questions. Each question carries 14 marks.

Q.7     a.   Give the regular expression of the set of all even strings over the alphabet {a, b} with at least one of the two substrings aa or bb. Also construct the finite automata that can accept the above language.  (8)

             b.   Compute A (2, 1) when , where N is the set of natural numbers,  is defined by

(3)

c.  Express the following statement as a disjunction (in DNF) also using quantifiers:  

There does not exit a woman who has taken a flight on every airline in the world.              (3)

Q.8     a.   Let L be a bounded distributive lattice. Show that if  a complement exists it is unique.                      (7)

             b.   Find the least number of cables required to connect 100 computers to 20 printers to guarantee that 20 computers can directly access 20 different printers.  Justify your answer.                             (7)

Q.9     a.   Prove that a simple graph is connected if and only if it has a spanning tree.           (7)

b.  Let  and let R and S be the relations on A described by  and

Use Warshall’s algorithm to compute the transitive closure of .                 (7)

Q.10           a.                                                        Express the negation of the statement so that no negation precedes a quantifier.                                                                            (3)

     b.   Let P(n) be the statement  is an odd number for . Is P (n) true for all n? Explain.                                                              (3)

              c.  Draw the Hasse diagram for the poset  where and is the power set of A.                                                               (8)

Q.11           a. Show that a positive logic NAND gate is equivalent to negative logic NOR gate.                                                                                                        (4)          

             b.   Suppose (5)

c.   Show that among any n+1 positive integers whose value does not exceed 2n, there must be an integer that divides one of the other integers.                                                                         (5)