JAN 2010 MCA i SEM QUESTION PAPER(JNTUK-REG)
Time: 3 Hours Max Marks: 60
Answer any FIVE questions All questions carry EQUAL marks
1. a) Find the conjunctive normal form and disjunctive normal forms for
i) p (p¢Úq¢)
ii) (pÚq¢)® q
b) Determine the contra positive of the each statement
i) If john is a poet, then he is poor.
ii) Only if Marc studies well he pass the test
2. a) Express the following statements using quantifiers. Then construct the
negation of the statement
i) Every bird can fly
ii) Some birds can talk
b) Prove that if n is an integer and n3+5 is odd then n is even.
3. Let R be a binary relation on the set of all positive integers such that
R = { (a,b)/ a-b is an add positive integer}
Is R Reflexive? Symmetric? Antisymmtric? Transitive? An equivalence
relation? A partial ordering relation?
4. a) let (A, *) be a semi group. Show that, for a, b, c in A, if a*c=c*a and
b*c=c*b, then (a*b)*c = c* (a*b)
b) Let f and g be homomorphism from a group (G, +) to a group (H,*). Show
that (C,+) is a subgroup of (G,+), where C={ xÎ G\ f(x)=g(x)}
5. a) Find the sum of all four digit numbers that can be obtained by using (without
repetition) the digits 2, 3,5 and 7.
b) Enumerate the number of ways of placing 20 indistinguishable balls in to 5 boxes
where each box is non empty.
6. a) Solve the recurrence relation tn = 4(tn-1 – tn-2 ) subject to initial condition
tn=1 for n=0 and n=1
b) What is an nth order linear homogenous recurrence relation with constant
coefficients? Give examples
7. a) What are the necessary and sufficient conditions to specify that two
graphs are isomorphic. Explain with an example.
b) Briefly explain Prim’s algorithm for minimum spanning trees.
8. Give example for each of the following
i)Graph having Euler’s circuit
ii)Graph having Hamiltonian circuit
JAN 2010 MCA i SEM QUESTION PAPER(JNTUK-SUPPLY)
Time: 3 Hours Max Marks: 60
Answer any FIVE questions All questions carry EQUAL marks
1
a) Prove (P-> Q)<=>(~PVQ)
b) Translate each of the following into symbols using quantifiers, variables and predicate
symbols.
i) All birds can fly
ii) Some babies are illogical
2 a) Prove that (A-B)-C= (A-C)-(B-C)
b) Let L denote the relation <= , D denote the relation “divides” (1) where xDy means x divides y.
Both L and D are defined on the set {1,2,3,6}.
Write L and D as sets and find L ^ D
3 a) A man has 5 female friends and his wife has 7 female friends. In how many ways can they
invite 6 males and 6 females if husband and wife are to invite 6 friends each.
b) In how many ways can two A’s are together but not two R’s of the word “ARRANGE”
4. Solve the recurrence relation T(k)-7T(k-1)+10T(k-2)=k2+1 and T(0)=4, T(1)=17.
5. a) Construct a graph on 12 vertices with 2 of them having degree 1,
three having degree 3 and the remaining seven having degree 10.
b) How many vertices does a regular graph of degree 4 with 10 edges have?
6 a) Show that if G is a simple planar graph with | V| 11, then the complement of G is non
planar.
b) Let G be a connected simple planar graph containing n vertices and m edges in which every
region show that m<= k(n-2)/ k-2.
7 a) Write briefly about binary trees.
b) Draw the BFS tree for the following graph.
8 a) Prove that every circuit has an even number of edges in common with any cut set.
b) Explain Prim’s algorithm to find a minimum spanning tree with an example
JAN 2010 MCA i SEM QUESTION PAPER(JNTUK-SUPPLY)
Time: 3 Hours Max Marks: 60
Answer any FIVE questions All questions carry EQUAL marks
1.
a) Write the truth table for the following preposition.
(pÚq)Ù(~pÚq) Ù(pÚ~q)Ù( ~pÚ~q)
b) Show that the negation of p q is logically equivalent to pÙ~q
2. a) Obtain the principal of disjunctive and conjunctive normal forms of the following
formula
pÚ(~p (qÚ(~q r)))
b) Express the statements with quantifiers and logical connectives “ X can speak Marathi”. “X
knows the computer language C”
3. a) Prove that A relation R on A is symmetric if and only if R=R-1
b) Draw the Hasse diagram for the partial ordering {(A,B): A£B} on the power set
P(S) where S= {a,b,c}
4. a) Let (S,*) be a semi group and (Ss,o) be a semi group where Ss is the set of all
functions from S to S. Then, prove that there exists a homo morphism f:S Ss
b) Prove that a homomorphism f from (G,*) onto (G¢, o) with the kernel K is an
isomorphism if and only if K={e}
5. a) Two pair die are rolled. What is the probability that sum of the numbers on the die is
Odd?
b) In how many ways can we select 5 balls from 6 red, 6 green and 8 purple?
6. Solve the recurrence relation for the initial conditions
an= -2nan-1 + 3n(n-1)an-2, a0=1,a1=2
7. a) Use BFS to find a spanning tree for the graph
b) Determine whether the graphs G and G’ are isomorphic.
8. a) What is a chromatic number of a cycle and a tree? Find t he chromatic number of
the “wheel “given below
b) Show that a connected graph is Eulerian if and only if it has no vertices of odd degree.
Posts
0 comments:
Post a Comment