Download JNTUH (Jawaharlal nehru technological university) MCA (Master of Computer Applications) 1st Sem (First Semester) Regulation-R15 2017 August 821AA Mathematical Foundations Of Computer Science Previous Question Paper
R15
Code No: 821AA
JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD
MCA I Semester Examinations, August - 2017
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)
What do you mean by a well-formed formula? Give examples of formulas that are well-
formed and not well-formed.
[5]
b) What do you mean by a lattice? List the properties of a lattice.
[5]
c) What are the two basic counting principles.
[5]
d) Give the generating functions for the sequences C(k, )
n , n
a ,
n
( )
1 and n .
[5]
e) Is there a graph with degree sequence (1,3,3,3,5,6,6)? Justify your answer.
[5]
PART - B
5 ? 10 Marks = 50
2.a)
Show the following equivalences:
i) A (P C) (A )
P C
ii) (P C) (Q C) (P )
Q C
b)
Show that the following premises are inconsistent:
i) If Jack misses many classes through illness, then he fails high school.
ii) If Jack fails high school, then he is uneducated.
iii) If Jack reads a lot of books, then he is not uneducated.
iv) Jack misses many classes through illness and reads a lot of books.
[5+5]
OR
3.a)
Obtain a principal conjunctive normal form of each of the following formulas:
i) ( P
)
R (Q )
P
ii) P (P (Q )
P )
b)
Show that ( )(
x
(
P )
x (
Q ))
x ( )(
x
(
Q )
x (
R ))
x ( )(
x
(
P )
x (
R ))
x
[5+5]
4.a)
Let X
}
7
,...,
2
,
1
{
and R {(x, y) | x y is divisible by 3} . Show that R is an equivalence
relation. Draw the graph of R.
b) Show that in a group ( ,
G *), if for any a, b G,
2
2
2
(a *b) a *b , then ( ,
G *)must be
abelian.
[5+5]
OR
5.a)
Let f ( )
x x ,
2 g( )
x x ,
2 and h(x) 3x for x ,
R where R is the set of real
numbers. Find g f , f g, f f , g g, f h g .
b) Find all the subgroups of (Z , ) and ( *
Z , )
[5+5]
12
12
7
7
6.a)
How many ways are there to distribute 10 balls into 6 boxes with atmost 4 balls in the
first 2 boxes if:
i) The balls are indistinguishable
ii) The balls are distinguishable
b)
Verify that C(n ,
3 r) 3C(n ,
2 r) 3C(n ,
1 r) C( ,
n r) C( ,
n r )
3
[5+5]
OR
7.a)
Find the number of integral solutions for the following:
i) x x x x x 10 where x 0
1
2
3
4
5
i
ii) x x x x
,
50 where x ,
4 x 7 ,x ,
14 x 10
1
2
3
4
1
2
3
4
b) Determine the coefficient of 5
x in
2
10
(a bx cx ) and
15
(x 7 y) .
[5+5]
8.a)
Build a generating function for a the number of integral solutions to the equation
r
x x x r
1
2
3
i) 0 x
3 for each i
i
ii) 2 x 5 for each i
i
b)
Write a generating function for a , the number of ways of obtaining the sum n when
n
tossing 9 distinguishable dice. Then find a .
[5+5]
25
OR
9.a)
Solve the following recurrence relations using the characteristic roots:
i) a 3a
4a
0 for n
2 and a a 1.
n
n 1
n2
0
1
ii) a 4a
12a
0 for n
2 and a 4, a 16 / 3.
[5+5]
n
n 1
n2
0
1
b)
Write the general form of a particular solution P
a to the following recurrence relations:
n
i) a 7a
12a
n
n
n 1
n2
ii)
n
a 7a
12a
2
n
n 1
[5+5]
n2
10.a) Demonstrate with an example breadth-first search algorithm.
b) Are the graphs shown below isomorphic? Justify your answer.
[5+5]
OR
11.a) Obtain the minimal spanning tree for the following graph.
b) Draw a full regular tree of degree 2 and height 3.
[5+5]
---ooOoo---
This post was last modified on 16 March 2023