DECEMBER 2006

Code: C-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. Transitivity and irreflexive imply:

(A) Symmetric (B)  Reflexive

(C)  Irreflexive                                     (D)  Asymmetric

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 Grammar                         (B) Type 1 grammar

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

             e.   Let * be a Boolean operation defined by

                   A * B = AB +    , then A*A is:

(A) A                                                 (B)  B

(C)  0                                                  (D)  1

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

(A) 6!                                                (B) 7!

(C) 5! (D) 7

             g.   In how many ways can a hungry student choose 3 toppings for his prize from a list of 10 delicious possibilities?

(A) 100 (B) 120

(C) 110                                              (D) 150

             h.   Which of the following statement is true:

(A) Every graph is not its own sub graph.

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

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

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

             i.    Seven (distinct) car accidents occurred in a week.  What is the probability that they all occurred on the same day?

(A) (B)

(C) (D)

             j.    Which of the following proposition is a tautology?

(A)  (B)

(C) (D) 

Answer any FIVE Questions out of EIGHT Questions.

Each question carries 16 marks.

Q.2     a.   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 of the word UTTAR PRADESH.                                              (6+2=8)

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

                   (i)  How many players are there in all?

                   (ii) How many play only football?                                                               (4+4=8)

Q.3     a.   Prove that a given connected graph G is an Euler graph if all vertices of G are of even degree.                                                                    (8)

             b.   Simplify the Boolean function:              

(8)

Q.4     a.   What is minimum spanning tree?  Determine a railway network of minimal cost for the cities in the following graph using Kruskal’s algorithm.           (10)

b.   Prove that A tree with n vertices has (n – 1) edges.                                            (6)

Q.5     a.   Prove the De Morgan’s Law by algebraic method

For every pair of elements x and y in A

                   (i) 

                   (ii)  (10)

     b.   Find the equivalent formula for that contains  only.                     (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.   What is equivalence relation?  Prove that relation ‘congruence modulo’         ( mod m) is an equivalence relation. (8)

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

     b.   Specify the transition function of the DFA shown below and describe the language.             (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.   Let L, be distributive Lattice, for any a,b,c L

                   If  and , prove that b = c                                          (8)

Q.9 Write short note on:

(i) Pigeonhole Principle

(ii) Graph Isomorphism

(iii) Tree Traversal

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