Download JNTUA MCA 2014 Aug Supple 1st Sem 9F00104 Mathematical Foundations of Computer Science Question Paper

Download JNTUA (JNTU Anantapur) MCA (Master of Computer Applications) 2014 August Supplementary 1st Sem 9F00104 Mathematical Foundations of Computer Science Question Paper

Code: 9F00104
MCA I Semester Supplementary Examinations August 2014
MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE
(For students admitted in 2009, 2010, 2011, 2012 & 2013 only)

Time: 3 hours Max. Marks: 60
Answer any FIVE questions
All questions carry equal marks
*****
1. (a) Write short notes on natural forms.
(b)
Show that ( ?x) (P(x) ? Q(x)) ? ( ?x) (P(x) ? ?(x) Q(x)) using rules of inference.

2. (a) What do you mean by proof of contradiction? Explain with a suitable example.
(b)
Show that (7Q ? (P ? Q))
?
???? ? 7P by using automatic theorem proving.

3. (a) Define lattice. Let ?n? be the +ve integer and S
n
be the set of all divisors of ?n?. Let n=6
and D denotes the relations ?Division?, ? a,b ? S
6,
aDb iff ?a divides b?. Find out
whether (S
6
, D) is a lattice or not? Draw Hasse diagram.
(b) Write short note on partial order relations.

4. (a) Show that the set G = {0, 1, 2, 3, 4, 5} is not a group under addition and multiplication
module 6.
(b) What is a monoid? Give three examples for a monoid.

5. (a) State and explain pigeon hole principle.
(b) Let < R, t, ? > be a ring and a,b,c be any elements of R. Prove the following:
(i) a.(-b) = (-a).b = -(a.b)
(ii) (-a).(-b) = a.b
(iii) ?(a+b) = (-a) + (-b)

6. (a) Find the number of integer solutions of the equation x
1
+ x
2
+ x
3
+ x
4
+x
5
= 30. Under
the constraints x
i
? 0 for i = 1,2,3,4,5 and further x
2
is even and x
3
is odd.
(b) Using generating function. Solve Y
n + 2
? 4Y
n+1
+ 3Y
n
= 0 given Y
0
= 2, Y
1
= 4.

7. (a) Write and explain the procedure of BFS algorithm.
(b) Construct the duals of the following planar graph.




8. Explain and exhibit the following:
(i) A graph which has both an Euler circuit and a Hamilton cycle.
(ii) A graph which was an Euler circuit but no Hamilton cycle.
(iii) A graph which has a Hamilton cycle but no Euler circuit.
(iv) A graph which has neither a Hamilton cycle nor an Euler circuit.
*****
FirstRanker.com - FirstRanker's Choice