Find a recurrence relation and the initial condition for the

Assignment Help Software Engineering

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.

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)

Reference no: EM131420680

Questions Cloud

Point on the roof where the ball lands : Find the horizontal distance from the wall to the point on the roof where the ball lands.

Does restaurant have the liability for reservation breach : Find at least one case similar to these legal issues and explain the case result and provide relevant law. . It does not have to be a case involving hotels or restaurants, but find a case which illustrates at least one legal issue you have identified..

How the experience personally affected you : Describe the following in your personal essay: A description of the art you experienced and How the experience personally affected you

How music supports and nurture children developmental skill : Explain how music supports and nurtures children's developmental skills. Question: What are some ways parents can integrate musical activities at home.

Find a recurrence relation and the initial condition for the : How many edges the graph has? How many regions are there? 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 recur..

Construct the corresponding excitation table : Use method 1 to find a critical race-free assignment for the table. Construct the corresponding excitation table.

Person actively promotes specific change within corporation : An example of this type of change would be the FX television network producing a new television show. open evolution b. disruptive innovation c.product change. technology change. This person actively promotes a specific change within a corporation, a..

Dispersive material at an angle of incidence : Consider a ray of white light incident from air on a dispersive material at an angle of incidence of 49.5 degrees. The red light refracts to an angle of 32.5 degrees in the dispersive material. If the index of refraction for green light is 7.50% l..

Analyzing types of errors made on a test or on student work : EDPT 514- When a teacher assesses daily from curriculum content, the assessment is called __. Analyzing the types of errors made on a test or on student work samples is called __.

User Account

All Pages