First question is compulsory.Answer any FOUR from the remaining question.

All questions carry equal marks. Answer all Parts of any question at one place.

1.  (a)   Construct the truth table for (~p)->(~Q);

(b)   Prove that the product of ttwo integers is even then either of them is even by using proof by contra positive.

(c)   The result of 50 football(win,lose,tie) are to be predicated.  How many different forecasts can contain exactly 28 correct results?

(d)   Show thatan=c1+c22nis solution ofan-3an-1+2an-2 =0

(e)   Write DFS for spanning tree of a graph.

(f)    Define colsed path, open path,simple path,

and cycle.

(g)    Prove that G  is non-triveal tree then G              contains at least 2vertices of degree 1.

2.   (a)  Check whether the statement is tautology or   not

((~P vQ)->(P->Q))^((P->Q)->(~PVQ))

(b)   Prove that n(n2+5) is a factor of 6 using mathematical induction.

3.   (a)  For what values of ‘r’ is it true that X1+X2=X3=X4=r has no integral solutions with X1>=7, X2>=8,  X3>=9,X4>=10?

(B) In how many ways can we package 20 books Into 5 packages such that 2 packages contain S books each, 2 other packages contain 3 each, 1 package has 4 books?

4.   (a) Solve the recurrence relation an – 7an-1+ 12an-2 =0 for n>=2 using generating functions.

(b) An abvertining agency has 1,000 clients, anong them 415 using television advertising, 350 using      radio, and 280 using newspaper advertising. 100 clients us all 3 types.  Find the number of clients who are using exactly 2-type of advertising.

5.  (a)  LetX ={ 2,3,6,12,24,36) and relation ‘<=’ be such that s<=y if x divides y. Draw the Hasse diagram (digraph) of (X,<=).  Also verify whether it is lattice or not.

(b) Given the adfacency matrix of the relation <= on the set {0,1,2,3,4). How can we say that this relation is reflexive using adjacency matrix?

6.  (a)   Explain the merging techni2que of two sorted sequences.

(b)   Defome Chromatic Number, Prove that G is bipartite graph if it is a 2-colorable.

7.   (a)  If Gis a simple graph with at least one edge the there is a vertex v of Gsuch that degree (v)< 5.

(b)   Define Isomorphism of graphs. Are the folowing pgaphs  Iso morphic?

(DIAGRAM)

8.   (a) Explain Kruskal’s asgorithm foer finding a minimal spanning tree.

(b) Write the pre order algorithm for tree traversal, Also find the traversal path of the following tree in pre order (DIAGRAM).

IT 2.1 Previous PapersCSE,CSE Previous Papers,Discrete Mathematical Structures-I Previous Papers,IT,IT Previous Papers
First question is compulsory.Answer any FOUR from the remaining question. All questions carry equal marks. Answer all Parts of any question at one place.  1.  (a)   Construct the truth table for (~p)->(~Q); (b)   Prove that the product of ttwo integers is even then either of them is even by using proof by contra positive. (c)  ...