Download JNTUH (Jawaharlal nehru technological university) MCA (Master of Computer Applications) 1st Sem (First Semester) Regulation-R15 2018 June-July 821AA Mathematical Foundations Of Computer Science Previous Question Paper
R15
Code No: 821AA
JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD
MCA I Semester Examinations, June/July - 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)
Prove that the following is a tautology.
[ (p q) (r s) (p r) ] (q s).
[5]
b)
Let X={1,2,3,4,5,6,7} and R={(x,y)|(x-y) is divisible by 3} in X. Show that R is an
Equivalence Relation.
[5]
c)
A bit is either 0 or 1. A byte is a sequence of 8 bits. Find the number of bytes. Among
these how many are
i) Starting with 11 and ending with 00
ii) Starting with 11 but not ending with 00.
[5]
d)
Solve the following recurrence relation by generating function method.
[5]
An-9an-1+27an-2-27an-3= 3n, n3.
e)
Let H be a sub graph of a connected graph G. Show that H is a sub graph of some
spanning tree T of G iff H contains no cycle.
[5]
PART - B
5 ? 10 Marks = 50
2.
Show that (S R) is tautologically implied by (P Q) (P->R) (Q->S). [10]
OR
3.
Symbolize the following argument and check for its validity.
a) All men are mortal
b) Every apple is red
[10]
4.a)
Show that the set N of natural numbers is a semi group under the operation
x * y =max {x, y}. Is it a Monoid?
b)
Prove that if (G, *) is an Abelian group, if and only if (a * b)2 = a2 * b2 .
Prove that intersection of two subgroups is a subgroup, but their union need not be a
subgroup of G.
[5+5]
OR
5.
Suppose that 10 integers 1,2,....10 are randomly positioned around a circular wheel. Show
that the sum of some set of 3 consecutively positioned numbers is atleast 17.
[10]
6.a)
In A survey of 100 students, it was found that 30 studied Mathematics, 54 studied
Statistics, 25 studied Operations Research, 01 studied all the three subjects, 20 studied
Mathematics and Statistics, 3 studied Mathematics and Operation Research and 15 studied
Statistics and Operation Research. Find how many students studied none of these subjects
and how many students studied only Mathematics?
b)
A total of 1232 students have taken a course in Spanish, 879 have taken a course in
French, and 114 have taken a course in Russian. Further, 103 have taken courses in both
Spanish and Russian, 23 have taken courses in both Spanish and French and 14 have taken
courses in both French and Russian. If 2092 students have taken atleast one of Spanish,
French and Russian, how many students have taken a course in all three languages?[5+5]
OR
7.a)
How many 6- digit numbers without repetition of digits are there such that the digits are
all non zero and 1 and 2 do not appear consecutively in either order.
b)
A palindrome is a word that reads the same forward or backward. How many 9 letter
palindromes are possible using the English alphabet.
[5+5]
8.a)
Find a recurrence relation for the number of n-digit binary sequences with no triple of
connective 1's.
b)
In how many ways can a person climb up a flight of n steps if the person can skip at most
one step at a time?
[5+5]
OR
9.a)
Using generating functions solve the recurrence relation an- 5an-1 + 6an-2 = 0 for n 2 and
a0 = 1, a2 = -2.
b)
Find the number of prime numbers that are not exceeding 100.
[5+5]
10.
Find spanning tree for the following graph using depth first search.
[10]
OR
11.
Using Prim's and Krushkal's algorithm, find a minimal spanning tree for the following
graph.
[10]
---oo0oo---
This post was last modified on 16 March 2023