Download JNTUH (Jawaharlal nehru technological university) MCA (Master of Computer Applications) 1st Sem (First Semester) Regulation-R13 2018 January 811AA Mathematical Foundations Of Computer Science Previous Question Paper
R13
Code No: 811AA
JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD
MCA I Semester Examinations, January - 2018
MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE
Time: 3hrs
Max.Marks: 60
Note: This question paper contains two parts A and B.
Part A is compulsory which carries 20 marks. Answer all questions in Part A. Part B
consists of 5 Units. Answer any one full question from each unit. Each question carries
8 marks and may have a, b, c as sub questions.
PART - A
5 ? 4 Marks = 20
1.a)
Define suitable predicates and symbolize each of the following:
i) Some of my friends are clever
ii) All clever people are boring
iii) None of my friends is wealthy
iv) Some of my wealthy friends are clever
v) All my clever friends are boring.
[4]
b)
Determine whether the relation with the directed graph shown is an equivalence relation.
[4]
c)
Define product and sum rules and give examples.
[4]
d)
What is a generating function? Give the applications of generating function.
[4]
e)
How many edges does a graph have if its degree sequence is
,
3
,
3
,
4
,
2 2 ? Draw such a
graph.
[4]
PART - B
5 ? 8 Marks = 40
2.a)
Using logical equivalences prove the following.
i) ~ ( p )
q ( p ~ )
q
ii) (( p ~ )
q r) ( p (q r))
b)
Give the rules of inference in propositional logic.
[4+4]
OR
3.a)
Prove by contradiction that there is no positive integer n such that n3+1=100.
b)
Obtain the principal disjunctive normal form of
i) p ((p )
q (
q
))
p
ii) (
p )
q ( p )
q
[4+4]
4.a)
Let A
,
24
,
15
,
9
,
5
,
3
{
}
45 and for any ,
a b A , a
b iff
a divides b
.
i) Draw Hasse diagram
ii) Find its maxima, minima, greatest and least elements if they exist.
Find maxima, minima, greatest and least elements of the set
}
15
,
9
,
3
{
if they exist.
b)
Give the definition of a group and list the properties of a group.
[4+4]
OR
5.a)
If G is a group such that
2
2 2
(ab) a b for all a
,b G , then show that G must be abelian.
b)
Show that the following posets are lattices and interpret their meets and joins.
i) The poset of the divisors of 60, ordered by divisibility.
ii) The poset of the subsets of
,
1
,
0
{
}
2 ordered by the subset relation.
[4+4]
6.a)
How many strings of 10 ternary digits (0,2, or 2) are there that contain exactly two 0s,
three 1s, and five 2s?
b)
How many positive integers less than 1,000,000 have the sum of their digits equal to 19.
[4+4]
OR
7.
State and prove binomial theorem by induction.
[8]
1
8.a)
Find the coefficient of 2005
x
in the generating function G(x)
2
2
1
( x) 1
( x)
b)
Solve the recurrence relation
n
a a
2 with a 5 .
[4+4]
n
n 1
0
OR
9.a)
Find a recurrence relation for the number of ways to make a pile of n chips using garnet,
gold, red, white and blue chips such that no two gold chips are together.
b)
Find the next two terms in the sequence
,
11
,
5
,
3
,
21
,
85
,
43
... and give a recursive definition
for the sequence.
[4+4]
10.a) Find a minimum cost spanning tree in the following graph shown in figure 1.
Figure: 1
b) Obtain a coloring of the following graph shown in figure 2.
[4+4]
Figure: 2
OR
11.a) Draw a planar representation of the following graph shown in figure 3.
Figure: 3
b) Explain isomorphism with example.
[4+4]
---ooOoo---
This post was last modified on 16 March 2023