MCS-033 Advanced Discrete Mathematics Solved Assignment 2018-2019

Course Code : MCS-033
Course Title : Advanced Discrete Mathematics
Assignment Number : MCA(III)/033/Assignment/2018-19
Maximum Marks : 100
Weightage : 25%
Last Dates for Submission : 15th October, 2018 (For July session)
15th April, 2019 (For January session)

This assignment has eleven questions, which carries 80 marks. Answer all the
questions. The rest 20 marks are for viva voce. You may use illustrations. Place
go through the guidelines regarding assignments given in the Programme Guide
for the format of presentation.

Question 1: Give an example of a second order linear homogenous recurrence
relation with constant coefficients. (2 Marks)
Question (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? (8 Marks)
(i) ?n = ?n-1 + ?n-2
(ii) ?n =5?n-1 + ?
3
(iii) ?n =?n-1 + ?n-2 +…. ?0
(iv) ?n = 5?n-1 ?n-2
Question (b): Solve the following recurrences relation
i) ?n = 2?n-1 (5 Marks)
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.
(5 Marks)
Question 2: Draw 2-isomorphic graphs and 3 non- isomorphic graphs on five
vertices. (5 Marks)
Question 3: Prove that the complement of ? is ? (5 Marks)
Question 4: Find λ(?), when ? is a Peterson graph (5 Marks)
Question 5: Write the expression for a linear homogenous recurrence relation with
constant coefficients of degree ? and explain the basic approach to solve
it. (5 Marks)
7
Question 6: Draw the following graphs and state which of following graph is a
regular graph? (5 Marks)
(i) ?5 (ii) ?5 (iii) ?4 (iv) ?5,5 (v) ?5
Question 7 (a): What is a chromatic number of a graph? What is a chromatic number
of the following graph? (5 Marks)
(b) Determine whether the above graph has a Hamiltonian circuit. If it has,
find such a circuit. If it does not have, justify it (5 Marks)
Question 8 (a): What is the solution of the following recurrences relation
an = an-1 + 2an-1, n > 2 (10 Marks)
with a0 = 0, a1=1
(b) an =2n
an-1, n > 0 with initial condition a0 =1
Question 9: Show that if G1, G2 …. Gn are bipartite graph UG is a bipartite graph
(5 Marks)
Question 10: Determine the number of subsets of a set of n element, where n > 0
(5 Marks)
Question 11: Show that K5 is not a planar graph.
MCS-033, MCS-33, MCS 033, MCS 33, MCS033, MCS33, MCS