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 :

a_n + 5a_n-1 + 4a_n-2 = 56.3ⁿ

(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:

a_n - 4a_n-1 = 6.4ⁿ , a₀ = 1.

(f) Let n be a +ive integer and D_n denotes the set of all divisors of n. Consider the partial order of divisibility in D_n, draw Hasse diagram of D₃₆.

(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:

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) = 2n² + 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 ) + log₂n

(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)