AMIETE – CS (OLD SCHEME)

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 the best alternative in the following:                                 (2 10)

             a.   Let A, B be  matrices. Which of the following is not true?

(A) (B)

(C) (D) A is symmetric only if

             b.   Let P(x) means “x can fly”. Then  is

(A) Some body can fly.                        (B) Nobody can fly.

(C) Everybody can fly.                         (D) Some body can not fly.

             c.   The number of different permutations of the letters of the word INDIA is

(A) 24.                                                (B) 60.

(C) 70.                                                (D) 120.

             d.   How many self complementary graphs are there with 6 vertices?

(A) 4                                                   (B) 3

(C) 0                                                   (D) 2

             e.   Letbe a binary relation on the set. Which of the following is true for R?

(A) R is reflexive, symmetric and transitive

(B) R is reflexive, anti-symmetric and transitive

(C) R is not reflexive, but is symmetric and transitive

(D) R is reflexive and symmetric, but is not transitive

             f.    Let A be the poset of all the subsets of the set {1, 2} under set-inclusion. Which of the following partially ordered set is isomorphic to A?

(A) The set of all even integers under the relation “less than”

(B) The set of all integers under the relation “less than”

(C) The set {1, 2, 3, 6} under the relation “divides”

(D) None of the above

             g.   Let A be a Boolean algebra. Which of the following cannot be the number of elements of A?

(A) 2                                                   (B) 3

(C) 4                                                   (D) 8 

             h.   Which of the following is equivalent to the Boolean polynomial function

(A)

(B)

(C)

(D)

             i.    Let G be a tree with n vertices and m edges. Which of the following is not true for G?

(A) G is a connected graph and m = n + 1

(B) For any edge e of G, the graph G-e is a disconnected graph

(C) For any edge e of G, the graph G+e does not contain more than one

 cycle.

(D) G has no cycles and n = m+1

             j.    Consider the phase-structure grammar G = (V, T, S, P); where

                   V = {0, 1, S}, T = {0, 1}, S is the starting symbol and P is the production defined as S  0S1 and S l. Which of the following is generated by G?

(A) The set of all binary strings consisting of the same number of 0’s

                          and 1’s.

(B) The set

(C) Both the above sets

(D) None of the above sets.

Answer any FIVE Questions out of EIGHT Questions.

Each question carries 16 marks.

  Q.2     a.   Use the truth table to show that  is a tautology.                (8)

             b.   Use Mathematical Induction to prove that

(8)

Q.3     a.   An urn contains 15 balls of black and white colors. There are 10 white balls. In how many ways 7 balls can be chosen so that the number of white balls chosen is more than the number of black balls. (8)

             b.   Use pigeonhole principle to prove that in any group of at least 6 people, there will be 3 persons who are mutually friends or there will be persons who are mutually strangers.                                   (8)

Q.4     a.   Find the solution of the recurrence relation (6)

             b.   Let G be a graph with vertices  and let A be the adjacency matrix of G. Prove that the (i, j)th element of is the number of different paths of length k joining  for any integer k,  (10)

Q.5     a.   Show that the relation R on the set of all real numbers defined by aRb if

 is an equivalence relation.                                                (8)

             b.   Find all the equivalence classes of the equivalence relation R on the set of all integers defined by aRb if  is an equivalence relation.                                                                (8)

  Q.6     a.   Check whether the function on the set of all positive real numbers is an injection, a surjection or a bijection or not. If yes, find its inverse.                                                                (8)

             b.   Find the BFS tree and the DFS tree of the following graph starting at the vertex V. Give the adjacency list representation.                                     (8)

Q.7     a.   State the Warshall’s algorithm and use it to find the transitive closure of  on a set.                                 (8)

             b.   Determine whether the set of all subsets of the set {1, 2, 3} under set-inclusion is a partially ordered set. If yes, find its Hasse diagram.                  (8)

Q.8     a.   Draw the logic circuit diagram for the Boolean polynomial: .                     (6)

             b.   Find the minimum spanning tree of the following graph given by the Kruskal’s algorithm and the Prim’s algorithm.                                            (10)

                   What is the difference between Prim’s algorithm and Kruskal’s algorithm in terms of the intermediate graph that you get in each iteration?

Q.9     a.   Obtain the expression tree of the expression,  and the pre-order traversal of the tree to obtain the prefix notation of the expression.     (8)

             b.   Prove that there is no finite state automaton that recognizes the set of bit strings consisting of an equal number of 0’s and 1’s.                                     (8)