AMIETE – CS (OLD SCHEME)

 

Flowchart: Alternate Process: JUNE 2010Code: 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:                                (210)

          

             a.   Which of these sets are equal A={r,t,s}, B={ s,t,r,s} , C={ t,s,t,r} and D={s,t,r,s}?

                  

                   (A) sets A and B                                (B) sets A and D

                   (C) sets  B and D                               (D) all these sets are equal

 

             b.   Let A= { 1,2 ,3,4} and R=F . Determine that the relation is:

 

                   (A) reflexive                                       (B) symmetric

                   (C) transitive                                      (D) none of these

 

             c.   How many straight lines can be drawn through 10 points on a circle?

 

                   (A) 50                                                 (B) 20

                   (C) 45                                                 (D) 40

 

             d.   A È B = A Ç B if and only if:

       

                   (A) A is empty set                              (B) B is empty set

                   (C) A and B are non-empty sets        (D) A and B are empty sets

 

             e.   A graph in which all nodes are of equal degree is known as:

                  

                   (A) multigraph                                   (B) non regular graph

                   (C) regular graph                                (D) complete graph

 

             f.    The number of circuits in a tree with ‘n’ nodes is:

 

                   (A) zero                                              (B) one

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

 

             g.   How many ways can you arrange the letters of the word ‘APPLE’?

 

                   (A) 120                                               (B) 60

                   (C) 100                                               (D) None of these

 

 

 

             h.   Turing machine is more powerful then Finite State Machine because

 

                   (A) Tape movement is confined to one direction.                                                         

                   (B)  It has no finite set.

                   (C)  It has the capability to remember arbitrary rely long sequences of            input symbol.   

                   (D)  None of these.

 

             i.    The number of colors required to properly colors the vertices of every planar graph is

 

                   (A) 2                                                   (B) 3

                   (C) 4                                                   (D) 5

 

             j.    When two dice are thrown, find the probability of getting total score seven.

 

                   (A) 1/6                                                (B) 1/3

                   (C) 1/12                                              (D) 1/4

 

 

Answer any FIVE Questions out of EIGHT Questions.

Each question carries 16 marks.

 

 

  Q.2     a.   In a survey  of 60 people, it was found that 25 read Newsweek magazine, 25 read Time magazine, 26 read Fortune magazine, 9 read both Newsweek and Fortune, 11 read both Newsweek and Time, 8 read both Time and Fortune, 3 read all the magazine.

              (i)  Find the number of people who read at least one of the three magazines.

                  (ii) Find in the correct number of people in each of the eight regions of             

                        Venn diagram.                                                                                            (8)            

 

             b.   Give the converse and contrapositive of the implications

                   (i)   If it is hot, then I take cold drinks.                                                               

                   (ii)  If today is Monday, then tomorrow is Tuesday.                                       (8)          

 

  Q.3     a.   Design an FA that accept those strings over {0, 1} for which the last two input symbols are 1.                                                                      (8)

 

             b.   Prove that, A graph G with n vertices, (n – 1) edges, and no circuits is a tree. Construct a graph that has 6 vertices and 5 edges but it is not tree.                                                    (8)

 

  Q.4     a.   Prove that every Boolean function can be put in Disjunction Normal Form (DNF).                  (8)

 

             b.   Show that the following Boolean expressions are equivalent to one another. Obtain there sum of product canonical form.

                   (i)  

                   (ii)                                                                             

                   (iii)                                                                                                      (8)

 

 

 

  Q.5     a.   Let A = {1, 2, 3, 4, 6}, and let R be the relation on A defined by “x divides y”, written x ½ y.

 

                   (i)   Write R as a set of ordered pairs

                   (ii)  Draw its diagraph

                   (iii) Find the inverse relation R -1of R. Can R-1 be described in word?           (8)

 

             b.   Explain Kruskal’s algorithm and find minimal spanning tree for the graph given below.                                                                     (8)
 
 

 

 

 

 

 

 

 

 

 

 

 


  Q.6           Write short notes on following:

                   (i)    Pigeonhole Principle

                   (ii)  Warshall’s algorithm to find transitive closure

                   (iii) Hamiltonian path

                   (iv) Equivalence relations.                                                                              (16)

 

  Q.7     a.   What is Partially Ordered Set? Let S = {a,b,c} and A = P(S). Draw the Hasse diagram of the poset A with the partial order Í   (set inclusion).                                                          (8)

 

             b.   Prove that, A given connected graph G is an Euler graph if all vertices of G are of even degree.                                                                    (8)

 

  Q.8     a.   What is the solution of the recurrence relation                                                (8)

                                                                                                                  

                   With initial conditions ?

       

             b.  A man is known to speak the truth 2 out of 3 times. He throws a dice and reports that it is one. Find the probability that it is actually one.                                                               (8)

            

  Q.9     a.   Prove by induction that for all integers                                                 (8)

 

             b.   How many bit strings of length nine either start with 1 bit or end with the two bits 00?                                                                     (8)