Download JNTUH MCA 1st Sem R15 2017 August 821AA Mathematical Foundations Of Computer Science Question Paper

FirstRanker.com

Code No: 821AA R15

JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD

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

FirstRanker.com

MCA I Semester Examinations, August - 2017

MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE

Time: 3hrs Max.Marks:75

Note:

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

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 as sub questions.

PART - A

5 x 5 Marks =25

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

1. What do you mean by a well-formed formula? Give examples of formulas that are well-formed and not well-formed. [5]
2. What do you mean by a lattice? List the properties of a lattice. [5]
3. What are the two basic counting principles. [5]
4. Give the generating functions for the sequences C(k,n), aⁿ, (-1)ⁿ and n. [5]
5. Is there a graph with degree sequence (1,3,3,3,5,6,6)? Justify your answer. [5]

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

PART -B

5 x 10 Marks =50

1. a) Show the following equivalences:
   i) A?(P?C) = (A?¬P)?C
   ii) P?(Q?¬Q) = (¬P?Q)?C
   

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

   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]
   

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

   OR
2. 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]

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

3. a) Let X ={1,2,...;7}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, (a*b)^-1 =a^-1 *b^-1, then (G,*) must be abelian. [5+5]
   OR
4. 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₇, x₇) [5+5]

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

5. 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

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

6. a) Find the number of integral solutions for the following:
   i) x₁ +x₂ +x₃ +x₄ +x₅ =10 where x_i =0
   ii) x₁ +x₂ +x₃ +x₄ =50, where x₁ =4, x₂ =7, x₃ =-14, x₄ =10
   b) Determine the coefficient of x⁹ in (a +bx +cx²)¹⁰ and (x-7y)¹⁶. [5+5]
7. a) Build a generating function for a_r =the number of integral solutions to the equation x₁ +x₂+x₃=r
   

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

   i) 0<x_i <3 for each i
   ii) 2<x_i < 5 for each i
   b) Write a generating function for a_n, the number of ways of obtaining the sum n when tossing 9 distinguishable dice. Then find a₁₅. [5+5]
   OR
8. a) Solve the following recurrence relations using the characteristic roots:
   

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

   i) a_n-3a_n-1-4a_n-2=0 for n=2 and a₀=a₁ =1.
   ii) a_n-4a_n-1-12a_n-2=0 for n=2 and a₀=4,a₁=16/3. [5+5]
9. a) Write the general form of a particular solution a_p to the following recurrence relations:
   i) a_n-7a_n-1+12a_n-2=n
   ii) a_n-7a_n-1+12a_n-2=2ⁿ [5+5]

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

10. a) Demonstrate with an example breadth-first search algorithm.
    b) Are the graphs shown below isomorphic? Justify your answer. [5+5]
11. a) Draw a full regular tree of degree 2 and height 3. [5+5]

FirstRanker.com

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