University of Delhi 2009-2nd Sem M.C.A DISCRETE MATHEMATICS - Question Paper

Download the paper from Attachment.

This question paper contains 3 printed pages.

Your Roll No

MCA/II Sem.

J

Paper MCA - 202 - DISCRETE MATHEMATICS (Admissions of 2009 and onwards)

Maximum Marks 50

(Write your Roll No on the top immediately on receipt of this question paper)

Attempt all questions.

Parts of a question must be answered together.

1. a) Determine the discrete numeric function corresponding to the following generating function

04

b) Obtain the generating function for the fibonacci sequence of number, 1 e f = f _f + f

for n > 2 and f_Q = 0 and f, - L

04

c) Solve the recurrence relation

b) For the formula

(P -> (Q AR))A(~P->(~Q A~R))

Obtain the

(i)    principal disjunctive normal form

(ii)    principal conjuctive normal form. 2^XA +2^XA - 5

3 a) Let Z_n = {0, 1,2, . . n-1}. Let 0 be a binary operation on Z_n s.t for a and b m Z_n,

fa + b if a + b < n a b =<

ja + b- n if a + b > n

CO show that (Zn, 0 ) is a group.

(H) Does (Zn, 0) form an abelian group ? Give

b) Prove that the rate of growth of an exponential function, f(n) = aⁿ, a > 1, is greater than any polynomial

function.

5 a) Apply Dijkstras Algorithm to determine a shortest path between v_Q and v₅, where the numbers associated with the edges weights of the edges.    06

b) Determine a minimum spanning tree using Kruskals Algorithm for the graph given below    04

c) For the following weights, construct an optimal binary

prefix code using Huffmans procedure. For each

weight in the set give the corresponding code word.

weights: 5,7,8,15,35,40    03

100

1

a) Let B(x), (x), G(x) be the statements x is a book, x is expensive and x is good respectively.

Express each of the following statements using quantifiers, logical connectives and B(x), (x) and G(x), where the universe of discourse is the set of all objects

(i)    No books are expensive

(ii)    All expensive books are good.    03

PTO

Attachment: university-of-delhi-2009-m-c-a--35536-1.pdf

Earning:   Approval pending.