Download JNTU Anantapur (JNTU Anantapur) Master of Computer Applications (MCA) 2019 May Reg-Supply 1st Sem 9F00104 Mathematical Foundations of Computer Science Previous Question Paper
MCA I Semester Supplementary Examinations May/June 2019
MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE
(For 2009, 2010, 2011 & 2012 (LC), 2013, 2014, 2015 & 2016 admitted batches only)
Time: 3 hours Max. Marks: 60
Answer any FIVE questions
All questions carry equal marks
*****
1 (a) Differentiate between PDNF and PCNF with two examples.
(b) State and explain the rules that can generate a well formed formula and give an example.
2 (a) Prove or disprove the validity of the following arguments using the:
Rules of inference,
All men are fallible,
All kings are men,
Therefore, all kings are fallible.
(b) Show that R is valid conclusion from the given set of premises P, P ? Q, Q ? R.
3 (a) Show that the sets of even numbers and odd numbers are both recursive.
(b) Differentiate equivalence relation and partial ordering relation with example.
4 (a) Let G = { ?1, 0, 1}, verify whether G forms a group under usual addition.
(b) If a, b are any two elements of a group (G,.) which commute, show that a
-1
and b commute, b
-1
and
commute, a
-1
and b
-1
commute.
5 (a) Show that if eight people are in a room, at least two of them have birthday that occur on the same
day of the week.
(b) How many ways are there to place 20 identical balls into 6 different boxes in which exactly 2 boxes
are empty?
6 (a) Solve a
n
? 5a
n ? 1
+ 6a
n ? 2
= (n + 1)
2
, a
0
= 0, a
1
= 1.
(b) Solve a
n
? 7a
n ? 1
+ 12a
n ? 2
= 0; n ? 2 by generating function.
7 (a) Differentiate between BFS and DFS with an example.
(b) In any planar graph, show that |V| ? |E| + |R| = 2.
8 (a) Define Hamiltonian cycles and write basic rules for constructing Hamiltonian cycles.
(b) Define chromatic number and explain it with four examples.
*****
FirstRanker.com - FirstRanker's Choice
This post was last modified on 28 July 2020