Code: AC-10                                                                        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 A be a finite set of size n.  The number of elements in the power set of  A X A is:

(A) (B)

(C) (D) 

b. Let * be a Boolean operation defined by , then A*A is:

(A) A (B)  B

(C)  0                                                  (D)  1

c. How many words can be formed out of the letters of the word ‘PECULIAR’ beginning with P and ending with R?

(A) 100 (B) 120

(C) 720 (D) 150

             d.   A debating team consists of 3 boys and 2 girls.  Find the number of ways they can sit in a row?

(A) 120                                             (B) 24

(C)  720                                             (D) 12      

             e.   Suppose v is an isolated vertex in a graph,  then the degree of v is:

(A) 0                                                  (B)  1

(C)  2                                                  (D)  3

             f.    Let p be “He is tall” and let q “He is handsome”.  Then the statement “It is false that he is short or handsome” is:

(A) (B)

(C) (D)

             g.   The Boolean expression  is independent of the Boolean variable:

(A) Y (B) X

(C) Z                                                  (D) None of these

             h.   Which of the following regular expression over  denotes the set of all strings not containing 100 as sub string

(A) .                                  (B) .

(C) .                                  (D)  .

             i.    In an undirected graph the number of nodes with odd degree must be

(A) Zero                                             (B) Odd

(C) Prime                                            (D) Even

             j.    Find the number of relations from A = {cat, dog, rat} to B = {male , female}

(A)  64                                                (B)  6

(C)  32 (D)  15

Answer any FIVE Questions out of EIGHT Questions.

Each question carries 16 marks.

Q.2     a.   Simplify the given expression

(8)

             b.   A fair six sided die is tossed three times and the resulting sequence of numbers is recorded.  What is the probability of the event E that either all three numbers are equal or none of them is a 4?       (8)

Q.3     a.   Define Euler Circuit and Euler Path.  Which of the following graphs have an Euler circuit and Euler path.                                                                 (8)

             b.   Prove that if a set A contains n elements, then P(A) contains elements.  Also find the number of proper subsets of the set of letters UTTAR PRADESH. (6+2=8)

Q.4     a.   Prove that Prim’s algorithm produces a minimum spanning tree of a connected weighted graph.                                                                  (8)

b.   Prove that, the complement of every element in a Boolean algebra B is unique.                    (8)

Q.5     a.   Prove that .                                                   (8)

     b.   Test the validity of argument:

                   “If it rains tomorrow, I will carry my umbrella, if its cloth is mended.  It will rain tomorrow and the cloth will not be mended.  Therefore I will not carry my umbrella”                                                     (8)

  Q.6     a. A valid identifier in the programming language FORTAN consists of a string of one to six alphanumeric characters (the 36 characters A,B,….,Z,0,1,…9) beginning with a letter.  How many valid FORTRAN identifiers are there?                                                                                           (8)

             b.   Let R be a relation on a set A.  Then prove that is the transitive closure of R. (8)

Q.7     a.   Show that  is divisible by (x - y) for all positive integral values of n.                       (8)

     b.   Build a Fine Automaton that accept all words that have different first and last letters (i.e. if the word begins with an “a” to be accepted it must end with “b” and vice versa.)                                          (8)

Q.8       a.   How many relations are possible from a set A of ‘m’ elements to another set B of ‘n’ elements?                                                                 (8)

             b.   What is Partially Ordered Set?  Let  and .  Draw the Hasse diagram of the poset A with the partial order  (set inclusion).                                                               (8)

Q.9 Write short note on:

(i) Pigeonhole Principle

(ii) Graph Isomorphism

(iii) Tree Traversal

(iv) Types of Grammar                                                      (4  4 = 16)