Discrete Mathematics-Practice Questions

MCS-033 

 

Question 1: Give an example of a second order linear homogenous recurrence relation with constant coefficients.

 (a): Find the order and degree of the following recurrences relation. Which of the following belongs to the linear homogenous recurrence relation with constant coefficient?

(i) 𝑓n = 𝑓n-1 + 𝑓n-2
(ii) 𝑎n =5𝑎n-1 + 𝑛3
(iii) 𝑎n =𝑎n-1 + 𝑎n-2 +…. 𝑎0

 (b): Solve the following recurrences relation
i) Sn = 2Sn-1

ii) Find an explicit recurrence relation for minimum number of moves in which the 𝑛-disks in tower of Hanoi puzzle can be solved! Also solve the obtained recurrence relation through an iterative method.

Question 2: Draw 2-isomorphic graphs and 3 non- isomorphic graphs on five vertices.

Question 3: Prove that the complement of 𝐺 is 𝐺.

Question 4: Find λ(𝐺), when 𝐺 is a Peterson graph.

Question 5: Write the expression for a linear homogenous recurrence relation with constant coefficients of degree 𝐾 and explain the basic approach to solve it.

Question 6: Draw the following graphs and state which of following graph is a regular graph?

(i) 𝐶5 (ii) 𝑊5 (iii) 𝑄4 (iv) 𝐾5,5 (v) 𝐾5

 

Question 8 (a): What is the solution of the following recurrences relation
an = an-1 + 2an-1, n > 2 
with a0 = 0, a1=1
(b) an =2n an-1, n > 0 with initial condition a0 =1

Question 10: Determine the number of subsets of a set of n element, where n > 0

Question 11: Show that K5 is not a planar graph.