KEMBAR78
Discrete Math Exam Paper | PDF | Discrete Mathematics | Mathematical Relations
Scribd
Upload
845 views6 pages

Discrete Math Exam Paper

1. The document is a past exam paper for Discrete Mathematics. It contains 10 questions testing concepts in discrete structures like graphs, logic, functions, and algorithms. Students are required to answer question 1 and any 3 other questions. 2. The questions test a range of discrete math topics like graph theory, logic, functions, algorithms and proofs. Students must demonstrate understanding of concepts like graph representations, Boolean logic, one-to-one functions, shortest path algorithms and equivalence relations. 3. The exam aims to evaluate students' comprehension of core discrete math concepts and their ability to apply algorithms and logical reasoning to solve problems in areas such as graph theory, Boolean logic, functions and proofs.

Uploaded by

sanjayghosh
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
845 views6 pages

Discrete Math Exam Paper

1. The document is a past exam paper for Discrete Mathematics. It contains 10 questions testing concepts in discrete structures like graphs, logic, functions, and algorithms. Students are required to answer question 1 and any 3 other questions. 2. The questions test a range of discrete math topics like graph theory, logic, functions, algorithms and proofs. Students must demonstrate understanding of concepts like graph representations, Boolean logic, one-to-one functions, shortest path algorithms and equivalence relations. 3. The exam aims to evaluate students' comprehension of core discrete math concepts and their ability to apply algorithms and logical reasoning to solve problems in areas such as graph theory, Boolean logic, functions and proofs.

Uploaded by

sanjayghosh
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 6

ADCA / McA (II Yr)

Term-End F.xamination
June, 2OO7

CS-07@ : DISCRETEMATHEMATICS

Time : 3 hours Maximum Marks : 75

Note : Qu estion no. 1 is cgmpulsory. Answer any three


questions from the rest.
l
l l

1. (a) Determine the truth value for each of the following


statements : 3

(il 4 + 3: 6 AND 3 + 3 = 6

( i i )5 + 3 : 8 OR 3+1:5

(b) Representthe graph

G : { ( 1, 2 , 3 , 4 1 , : I x - y I S 1 }
"*
where e-...is an edge connecting vertices x and y. 3
xy

(c) Let G be a non directed graph with L2 edges. If G


has 6 vertices each of degree 3 and the rest have
degree less than 3, what is the minimum number of
vertices G can have ? 3

cs-07@ P.T.O.
(d) Consider the following relation on

{ 1 ,2 , 3 , 4 , 5 , 6 l l .
R = { ( i j, ) l l i - j l : 2 1

Is R transitive ?

Is R reflexive ? 3

(e) Write inverse,converse,contrapositivefor

t p n ( p - ) q ) l+ q 3

(0 Calculate -25 + 75 using 2's cornplement. 3

(g) LetA : {x € R : x *U and definef(x) : .V - .


x-1
f is bijective function with Range of f as the
set B : {y € R : y * Z }. Find f-l(y). 3

(h) Find diameter of treeT 3


v1

v3

cs-07@
(i) Consider the graph

vl t-----z v2

v5

Does the graph have Eulerian circuit ?


If Yes, write Euleriancircuit.
If No, justify.

0) Show that everydistributivelattice is modular.

2. (a) Is the directed graph given below strongly


connected?

(b) Prove the validity of the following argument, "lf I get


the job and work hard, then I will get promoted. If I
get promoted, then I will be happy. I will not be
happy. Therefore, either I will not get the job or I
will not work hard.

cs-07@ P.T.O.
(c) Function f : R -+ R is defined by
f(x) : *2
Is this function one-one ? Justify.

3. (a) Out of 250 candidateswho failed in an examination,


it was revealed that L28 failed in Maths, 87 in
Physics and 134 in aggregate.31 failed in Maths
and in Physics,54 failed in aggregateand in Maths,
30 failed in aggregate and in Physics. Find how
many candidatesfailed
(i) in all three subjects.
(ii) in Maths but not in Physics.
(iii) in aggregatebut not in Maths.

(b) Obtain PDNF form for


lp v q

(c) Draw switching circuit for


(xr + xr) x, + x4

(d) Give an example of compl,eteBipartite graph.

4. (a) Find Minimum Spanning Tree u$ng Prim's


Algorithm for

v5

cs-07@
(b) Let X : {51, 52, 53, 54} be the universe,of which
the following are two fuzry sets :
^ 0.2 0.5 0.9 1
A : + + - +
51 52 53 54
n 1 0.8 0.5 0.2
6 : + + +
51 52 53 54
FindAUB,ANB.
(c) If f : R -+ R, g : R -+ R are defined by
f ( x: )x + 2 V x € R
g ( x :) * 2 v x € R
Find (fod (x) and (gof)(x).
(d) Let A : {1, 3, 9, 27,81}. Draw Hassediagramof
poset (A, 1),

5. {a} Using Karnaugh ffiop, simplify

X ' : A ' B C ' D ' +A B C ' D ' +A ' B C D ' + A B C D '


(b) relationon set A, prove that
If R is an equlvalence
R-l is also an equivalencerelation. 3
(c) Apply Dijkstra's algorithm to find shortest path from
atof.

cs-07@ 3,000

You might also like