Download JNTUH (Jawaharlal nehru technological university) MCA (Master of Computer Applications) 1st Sem (First Semester) Regulation-R17 2018 January 841AA Mathematical Foundations Of Computer Science Previous Question Paper
R17
Code No: 841AA
JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD
MCA I Semester Examinations, January - 2018
MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE
Time: 3hrs
Max.Marks:75
Note: This question paper contains two parts A and B.
Part A is compulsory which carries 25 marks. Answer all questions in Part A.
Part B consists of 5 Units. Answer any one full question from each unit. Each question
carries 10 marks and may have a, b, c as sub questions.
PART - A
5 ? 5 Marks = 25
1.a)
Give the formal definition of a well-formed formula in propositional logic with examples of
formulae that are well-formed and not-well-formed.
[5]
b)
Draw the Hasse diagram for divisibility on the set
}
17
,
16
,
13
,
11
,
7
,
5
,
3
{
[5]
c)
What is a Pascal triangle? Expand the binomial expression
3
(2x y) using Pascal triangle. [5]
d)
What is the general form of a non-homogeneous recurrence relation? Explain how the
solution is obtained.
[5]
e)
What is a spanning tree? Give the applications of a spanning tree.
[5]
PART - B
5 ? 10 Marks = 50
2.a)
Define the following terms and give examples.
i) Substitution Instance
ii) Logical equivalence
b)
Show that ( Q
(P Q)) P
using automatic theorem proving.
[5+5]
OR
3.a)
Write the following statements in predicate logic.
i) Everybody loves somebody
ii) There is somebody whom everybody loves
iii) Nobody loves everybody
iv) There is somebody whom no one loves.
b)
Find a CNF for ((
p (q r)) ( q
) ( r
) )
p
[5+5]
4.a)
Let S
,
3
,
2
,
1
{
...,
}
15
,
14
and R be the equivalence relation on S defined by x y(mod ),
5 that
is x y is divisible by 5. Find the partition of S induced by R.
b)
Define the following terms with examples:
i) Permutation group
ii) Normal subgroup
iii) Cyclic group
iv) Kernel
[5+5]
OR
5.a)
Draw the following posets, and determine the maximal and minimal elements:
i) Divisors of 36 ordered by divisibility
ii) The poset P(S) for S
}
2
,
1
,
0
{
ordered by subset relation.
b)
Simplify the following Boolean functions using Boolean algebra:
i) f ( ,
x ,
y z) xy (
x yz) x y
z
ii) f (x, y, z) xy xyz z
xy x yz
x z
y
[5+5]
6.a)
A multiple choice test contains 5 questions and each of these has four answer choices, with
one correct answer per question. In how many ways can the questions be answered if only
one of the answer choices is selected and nothing is left blank? Explain.
b)
We choose 12 cards from the deck of 52 playing cards.
i) How many different ways can it be done?
ii) How many ways can it be done if they must all come from the same suit?
iii) How many ways can it be done if we need exactly 3 kings and 3 queens?
iv) How many ways can it be done if all cards must have different face values?
[5+5]
OR
7.a)
Fill in the numerators:
tC
4
4.3.2.1
i)
7C
t
ii)
t(t )
1 .. 1
.
b)
Explain pigeon hole principles.
[5+5]
x3
8.
Find the sequence generated by the function f (x)
[10]
1 x
OR
9.
Solve the following recurrence relation using characteristic polynomial:
a 6a
11a
6a where a ,
2 a 5and a 15 .
[10]
n
n 1
n2
n3
0
1
2
10.a) Which of the following graphs have a Euler path/circuit? Explain
i.
ii.
iii.
b) Draw the planar representation of the following graph:
[5+5]
OR
11.a) Are the graphs given below bipartitie? Explain.
i.
ii.
b) Draw all the subgraphs of the following graph.
[5+5]
---oo0oo---
This post was last modified on 16 March 2023