CS/IT 09 304/PTCS 09 303-DISCRETE COMPUTATIONAL STRUCTURES (2009 admissions) OCTOBER 2011

SUBJECT - DISCRETE COMPUTATIONAL STRUCTURES

CODE -  09 304/09 303

SEMESTER - THIRD

BRANCH - CS/IT PTCS

UNIVERSITY - CALICUT

YEAR - 2011

DOWNLOAD LINK AT THE END OF THIS PAGE

Part A

Answer all Questions

1.Explain Contrapositive

2.Explain Equivalence relation.

3.Explain inverse functions.

4.Define Hamming Code.

5.Solve following recurrence relations.Assume n is even :

  T(n)= T(n-2)+1,T(0)=1.

(5x2=10 marks)

Part B

Answer any four questions.

6.Prove that -(p^q)<=>-p or -q.

7.Find the number of functions from m-element set to an n-element set.

8.Draw the Hasse diagram for the poset (A, (subset)), where A denotes the power set of set (a,b,c).

9. Prove that G is a abelian group  if and only if (a.b)^2=a^2.b^2 for all a,b belongs to G

10. Show that Z7={(1,2,3,4,5,6), * mod 7} is cyclic group.

11. Solve f(n)=f(n-1); f(0)=1.

(4x5=20 marks)

Part C

12.(a) Show that any propositon e can be transformed into CNF.

   or

   (b) Find disjunctive normal form of the following formula :

(P^Q)v(7P^Q)v(Q^R).

13.(a)  (i) Find the number of symmetric relations that can be defined on a set with n elements.

(ii) Using adjacency matrix, find the number of different reflexive relation on set A with

      n-element.

   Or

   (b) (i) f:X->Y

           (1) How many different functions are possible?

  (2) How many different one to one functions are possible?

       (ii) Define equivalence class. Find all equivalence classes of the congruence relation mod 5

   on the sets of integer.

14.(a) Let S be the set of real numbers expect -1. Define * on S by a*B=a+b+ab.Show that

       (S,*) is abelian group.

   Or

   (b) Let G be the set of all 2*2 matrix [a b], where a,b,c,d are real numbers,such that

                                          [c d]

       (ad-bc)=0. Show that the set G with matrix multiplication binary operation forms the group.

Let H=[a b] be the set of 2*2 matrix where a,b,d are real numbers,such that ad!=0.

     [0 d]

Prove that H is a subgroup of G.

15.(a) Using generating function, solve f(n)=f(n-1)+f(n-2); f(0)=1,f(1)=1.

  Or

   (b) Solve f(n)-5f(n-1)-6f(n-2)=2^n + n

(4x10=40 marks)

Download - 

Click Here For JPG  

Click Here For PDF