Reference no: EM131420680
DISCRETE STRUCTURE
There are two sections in this question paper : A and B. Section A is compulsory. Attempt any four questions from section B. Parts of a question MUST be answered together.
SECTION A
Q1(a) The vertices of a connected graph has following degree sequence { 2,2,2,3,3,3,4,4,5 }.
(i) How many edges the graph has?
(ii) How many regions are there?
(b) Suppose that the population of a village is 100 at time n=0 and 110 at time n=1. The population increment from time n-1 to time n is twice the increment from time n-2 to time n-1.Find a recurrence relation and the initial condition for the population at time n and then also find the explicit formula for it.
(c) Find the particular solution of the following difference equation :
an + 5an-1 + 4an-2 = 56.3n
(d) State the converse,inverse and contrapositive of the following statement:
"If triangle ABC is a right angled triangle,then | AB2| + |BC2| = |AC2| ".
(e) Solve the following recurrence using generating function method:
an - 4an-1 = 6.4n , a0 = 1.
(f) Let n be a +ive integer and Dn denotes the set of all divisors of n. Consider the partial order of divisibility in Dn, draw Hasse diagram of D36.
(g) What is a cut edge? Give suitable example.
(h) If 14 shoes are selected from 13 pairs of shoes, show that there must be a pair of matched shoes among the selection.
(i) If a vertex of a graph is not of even degree,then show that it does not have an Eular circuit.
(j) Prove that in a tree with two or more vertices ,there are at least two pendant vertices (leaves).
(k) What do you mean by chromatic number of a graph ? Explain with a suitable example.
SECTION B
Q2(a). Show that the following premises are inconsistent:
If Jack misses many classes through illness ,then he fails high school.
If Jack fails high school ,then he is uneducated.
If Jack reads a lot of books ,then he is not uneducated.
Jack misses many classes through illness and reads a lot of books.
(b) Use Kruskal's algorithm to determine a minimal spanning tree of the following connected weighted graph:
![1749_11.png](https://secure.expertsmind.com/CMSImages/1749_11.png)
Q3(a) Show that the necessary condition for a simple connected graph to be planar is e ≤ 3n - 6 where e and n denote total number of edges and vertices of the graph respectively.
(b) Describe CONVOLUTION of two numeric functions with suitable example.
Q4(a) Check the validity of the following arguments:
All intelligent persons are Engineers.
John is not an Engineer.
Therefore, John is not intelligent.
(b) Let f(n) = 2n2 + 5n + 5. Express f(n) in Big oh notation. Also find the necessary constants.
Q5(a) Solve the following recurrence using Master theorem method:
T(n) = 2 T(√n ) + log2n
(b) Sort the following numbers using insertion sort method. Also find the running time of this algorithm:
1,2,3,4,5,6
Q6(a) Obtain PDNF of the following formula:
( P ^ Q ) v ( Q ^ R )
(b) Show that (Ξx) M (x) follows logically from
(x) H (x) → and (Ξx) H (x)