Download JNTUH MCA 1st Sem R15 2018 June-July 821AA Mathematical Foundations Of Computer Science Question Paper

FirstRanker.com

Code No: 821AA R15

--- Content provided by⁠ FirstRanker.com ---

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.

--- Content provided by​ FirstRanker.com ---

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 x 5 Marks = 25

1. a) Prove that the following is a tautology. [P->(Q->R)]^[(P->Q)->(P->R)]. [5]
2. 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]

--- Content provided by⁠ FirstRanker.com ---

3. 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
   1. Starting with 11 and ending with 00
   2. Starting with 11 but not ending with 00. [5]
4. a) Solve the following recurrence relation by generating function method. [5]
   An-9an_1+27an_2-27an_3= 3ⁿ n>3.

--- Content provided by​ FirstRanker.com ---

5. b) 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 x 10 Marks =50

1. Show that (S v R) is tautologically implied by (P v Q) ^ (P->R) ^ (Q->S).[10]
   OR
   

   --- Content provided by FirstRanker.com ---

   Symbolize the following argument and check for its validity.
   a) All men are mortal b) Every apple is red [10]
2. 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?
3. b) Prove that if (G, *) is an Abelian group, if and only if (a * b)^-1 =a^-1 * b^-1.
4. a) Prove that intersection of two subgroups is a subgroup, but their union need not be a subgroup of G. [5+5]
   

   --- Content provided by‌ FirstRanker.com ---

   OR
   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]
5. FirstRanker.com
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?
7. 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]
   

   --- Content provided by‌ FirstRanker.com ---

   OR
   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.
8. a) 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]
9. b) Find a recurrence relation for the number of n-digit binary sequences with no triple of connective 1’s.
   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]
   

   --- Content provided by‍ FirstRanker.com ---

   OR
   Using generating functions solve the recurrence relation a_n- 5a_n-1 + 6a_n-2 =0 for n>2 and a₀=1,a₁=-2.
10. a) Find the number of prime numbers that are not exceeding 100. [5+5]
11. b) Find spanning tree for the following graph using depth first search. [10]
    OR
    

    --- Content provided by‌ FirstRanker.com ---

    Using Prim’s and Krushkal’s algorithm, find a minimal spanning tree for the following graph. [10]

---00000---

FirstRanker.com