Code: 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 P(S) denotes the powerset of set S. Which of the following is always true?

(A) (B)

(C) (D) 

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

(A) mⁿ (B)  m + n

(C)  n^m (D)  m * n

  c.   A binary Tree T has n leaf nodes. The number of nodes of degree 2 in T is:

(A) log n                                             (B) n

(C) n–1 (D)  n+1

             d.   Push down machine represents:

(A) Type 0 grammer                          (B) Type 1 grammer

(C)  Type-2 grammer                          (D) Type-3 grammer         

             e.   In how many ways can a party of 7 persons arrange themselves around a circular table?

(A) 6!                                                (B)  7!

(C)  5!                                                 (D)  7

             f.    Which of the following statement is true:

(A) Every graph is not its own subgraph

(B) The terminal vertex of a graph are of degree two.

(C) A tree with n vertices has n edges.

(D) A single vertex in graph G is a subgraph of G.

             g.   Which of the following proposition is a tautology?

(A) (p v q)®p (B) p v (q®p)

(C)  p v (p®q)                                    (D)  p®(p®q)

h.   What is the converse of the following assertion?

                   I stay only if you go.

(A) I stay if you go. (B)  If you do not go then I do not stay

(C)  If I stay then you go.                     (D)  If you do not stay then you go.

             i.    The length of Hamiltonian Path in a connected graph of n vertices is

(A) n–1 (B)  n

(C)  n+1 (D)  n/2

             j.    A graph with one vertex and no edges is:

(A)  multigraph                                    (B)  digraph

(C)  isolated graph (D)  trivial graph

Answer any FIVE Questions out of EIGHT Questions.

Each question carries 16 marks.

Q.2     a.   Shirts numbered consecutively from 1 to 20 are worn by 20 members of a bowling league. When any three of these members are chosen to be a team, the league proposes to use the sum of their shirt numbers as the code number for the team. Show that if any eight of the 20 are selected, then from these eight one may form at least two different teams having the same code number. (8)

             b.   In a group of athletic teams in a certain institute, 21 are in the basket ball team, 26 in the hockey team, 29 in the foot ball team. If 14 play hockey and basketball, 12 play foot ball and basket ball, 15 play hockey and foot ball, 8 play all the three games.

                   (i) How many players are there in all?

                   (ii) How many play only foot ball?        (4+4)

Q.3     a.   Let A = {a,b,c,d,e} and R={(a,a), (a,b), (b,c), (c,e), (c,d), (d,e)}

Compute (i) R² and (ii) R^¥ (8)

             b.   Simplify the Boolean function:

                   F(w,x,y,z) = å (0, 1, 2, 3, 4, 6, 8, 9, 12, 13, 14)                                               (8)

Q.4     a.   Use Kruskal’s algorithm to find a minimal spanning tree for the following graph.       (10)

b.   How do you find the second minimum spanning tree of a graph?  Find the second minimum spanning tree of the above graph.                                  (6)

Q.5     a.   Prove that for every pair of elements x and y in A (using algebraic method).

                   (i) (x+y)' = x'.y'

                   (ii) (x.y)' = x'+y' (10)

     b.   Prove that   (p « q)  « r = p « (q « r) (6)

  Q.6     a. Find the number of ways in which 5 prizes can be distributed among 5 students such that

(i) Each student may get a prize

                   (ii) There is no restriction to the number of prizes a student gets.                          (8)

             b.   Prove that the relation "congruence modulo m" is an equivalence relation in the set of integers. (8)

Q.7     a.   Show that   is divisible by 3.   (8)

     b.   Find the state table for the NFA with the state diagram given below.  Find the language recognized by it.                                                                (8)

Q.8       a.   Find the number of ways in which we can put n distinct objects into two identical boxes so that no box remains empty. (8)

             b.   Let L, be distributive Lattice, for any a,b,c Î L, then show that

                   a Ù b = a Ù c    and   a Ú b = a Ú c   imply b = c                                               (8)

Q.9     a.   Which of the following sets are equal?

S₁ = {1, 2, 2, 3},      S₂ = {x | x² – 2x + 1 = 0},

                   S₃ = {1, 2, 3},          S₄ = {x | x³ – 6x² + 11x – 6 = 0},                                      (8)

             b.   A graph G has 21 Edges, 3 vertices of degree 4 and other vertices

are of degree 3. Find the number of vertices in G. (8)