### Course Code : MCS-033

Course Code : MCS-033

Course Title : Advanced Discrete Mathematics

Assignment Number : MCA(3)/033/Assign/2012

Maximum Marks : 100

Weightage : 25%

Last Dates for Submission : 15

th

October, 2012 (For July 2012 Session)

15

th

April, 2013 (For January 2013 Session)

There are FIVE questions of total 80 marks in this assignment. Answer all

questions. 20 Marks are for viva-voce. You may use illustrations and diagrams to

enhance explanations. Please go through the guidelines regarding assignments given

in the Programme Guide for the format of presentation.

Question 1: (a) Using Karnaugh map, simplify

X': A'BC'D'+ ABCD+ ABCD'+ ABCD' (5 Marks)

(b) Describe Konigsberg’s 7 bridges problem and Euler's

solution to it. B (5 Marks)

(c) Show that the sum of the degrees of all vertices of a

graph is twice the number of edges in the graph. (5 Marks)

Question 2: (a) Let G be a non directed graph with 12 edges. If G has 5

vertices each of degree 3 and the rest have degree less

than 3, what is the minimum number of vertices G

can have? (5 Marks)

(b) What is Graph Cloning? Explain K-edge cloning with

an example. (5 Marks)

(c) Let f(n)= 5 f(n/ 2) + 3 and f(1) = 7. Find f(2k) where k

is a positive integer. Also estimate f(n) if f is an increasing

function. (5 Marks)

Question 3: (a) Define r-regular graph. Give an example of 3-regular

graph. (5 Marks)

(b)

f is bijective function with Range of f as the

(5 Marks)6

(c) What are isomorphic graphs? Are the graphs given below isomorphic?

Explain why? (7 Marks)

(i) (ii)

(d) What is connected Graph? Construct a graph with chromatic number 5.

(4 Marks)

Question 4:

(a) Solve following recurrence relations (9 Marks)

i) = + n, = 2

using substitution method

ii) 9

iii) =

(b) Write a short note on Tower of Hanoi Problem. How can it be

solved using recursion ? (4 Marks)

Question 5:

(a) Show that for subgraph H of a graph G (4 Marks)

∆ (H) ≤ ∆ (G)

(b) What is Divide and Concuer relations? Explain with an example? (4 Marks)

(c) Find a power series associated with the problem where we have to

find a number of ways to select 10 people to form and expert committee

from 6 Professors and 12 Associate Professors. (4 Marks)

(d) Tree is a Bipartite Graph” justify the statement with an example? (4 Marks)

**IGNOU Coaching for BCA, MCA, MBA in Jaipur**

IGNOU JAIPUR

Regional Director,

IGNOU Regional Centre,

70/79,

Sector - 7,

Patel Marg,

Mansarovar

Rajasthan - 302020

India

Ph :+91-0141-2785763 / 2785750

Fax :+91-0141-2784043

IGNOU Regional Centre,

70/79,

Sector - 7,

Patel Marg,

Mansarovar

Rajasthan - 302020

India

Ph :+91-0141-2785763 / 2785750

Fax :+91-0141-2784043

## 1 comments:

plz post the solution

## Post a Comment