Assignment July - 2016 & January - 2017 MCS-033 Advanced Discrete Mathematics

MCS-033

1.     Solve the following recurrence relation through substitution.

        (i)    a_n = a_n-1 + 5, subject to initial condition a₁ = 2

        (ii)   S_n = 5 S_n-1, subject to initial condition S₀ = 1   (8 Marks)

2.     Draw these graphs

        (i) C6, (ii) W6 (iii) Q3 (iv) K4,4 (v) K6                                      (5 Marks)

3.     For which value of n are these graph regular ?                      (5 Marks)

        (a) K_n (b) C_n (c) W_n (d) Q_n

4.     Draw five subgraphs of the following graph                          (5 Marks)

               

5.     Determine whether the given graph has a Hamilton circuit. If it does, find such a circuit. If it does not, give an argument to show why no such circuit exists.

6.     Find the order and degree of the following recurrence relation. Also, determine whether they are homogeneous or non-homogeneous. Constant coefficient and non constant coefficient.

        (i)    a_n = na_n-1 + n²a_n-2 + a_n-1 a_n-2

        (ii)   a_n = 5 a_n-1 + n₃

        (iii)  a_n = C a_n/m + b

        (iv)  a_n = na_n-1 + n₂a_n-2 + a_n-1 a_n-2

        (v)   a_n = C₁ a_n-1 + C₂ a_n-2+ ….. C_n-k a_n-k (10 Marks)

7.     A person invests Rs. 10,000 at 10 percent interest compounded annually. If An represents the amount at the end of n years, find a recurrence relation and initial condition that define the sequence {A_n}. Using the recurrence relation find amount payable after five years.                                            (7 Marks)

8.     State Dirac’s and Ore’s Theorem.                                                          (6 Marks)

9.     Determine whether the directed graph shown below has an Euler circuit. Construct an Euler circuit if one exists, if no Euler circuit exists, determine when the directed graph has Euler path. If yes, construct an Euler path if one exists.

10. What is the solution of the recurrence relation.     (7 Marks)  

        A_n = a_n-1 + 2 a_n-2

        With a₀ = 2 and a₁ = 7                  

11.  Define bipartite graph. Also given an example of it, where do you use this type of graph. (5 Marks)

12. What is the chromatic number of the following graph ?      (5 Marks)

13. Solve the following recurrence relation by substitution t_n = t_n-1 + n for n > 1 t₁ = 1

  

*****************************************************************

Note: Answer with Dotcom Books

www.dotcombooks4u.com

(Last 5 year solved question paper with Assignment solutions)

 ****************************************************************