Download JNTUH MCA 1st Sem R13 2018 January 811AA Mathematical Foundations Of Computer Science Question Paper

FirstRanker.com

Code No: 811AA R13

JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD

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

MCA I Semester Examinations, January - 2018

MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE

Time: 3hrs Max.Marks: 60

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

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

PART - A 5 x 4 Marks = 20

1. Define suitable predicates and symbolize each of the following:
   1. Some of my friends are clever
   2. All clever people are boring
   3. None of my friends is wealthy
   4. Some of my wealthy friends are clever

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

   5. All my clever friends are boring. [4]
2. Determine whether the relation with the directed graph shown is an equivalence relation. [4]
3. Define product and sum rules and give examples. [4]
4. What is a generating function? Give the applications of generating function. [4]

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

5. How many edges does a graph have if its degree sequence is 4,3,3,2,2? Draw such a graph. [4]

PART - B 5 x 8 Marks = 40

1. a) Using logical equivalences prove the following.
   1. ~(p⇒q)≡(p∧~q)
   2. (p∧~q)⇒r)≡(p⇒(q∨r))
   b) Give the rules of inference in propositional logic. [4+4]

   OR

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

2. a) Prove by contradiction that there is no positive integer n such that n²+1=100. b) Obtain the principal disjunctive normal form of (p=>(p>(qv-p))) ∧ (p∨q) [4+4]
3. a) Let A={3,5,9,15,24,45} and for any a,b ∈ A, a ≤ b iff a divides b.
   1. Draw Hasse diagram
   2. Find its maxima, minima, greatest and least elements if they exist.
   b) Find maxima, minima, greatest and least elements of the set {3,9,15} if they exist.

   OR

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

4. a) Give the definition of a group and list the properties of a group. [4+4]
5. a) If G is a group such that (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.
   1. The poset of the divisors of 60, ordered by divisibility.
   2. The poset of the subsets of {0,1,2} ordered by the subset relation. [4+4]

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

6. a) How many strings of 10 ternary digits (0,1, 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]
8. a) Find the coefficient of x¹⁶ in the generating function G(x) = 1/(1-x)²(1+x) b) Solve the recurrence relation a_n = a_n-1 +2ⁿ with a₀ =5. [4+4]

   OR

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

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 3,5,11,21,43,85,... 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.
    
    b) Obtain a coloring of the following graph shown in figure 2. [4+4]
11. a) Draw a planar representation of the following graph shown in figure 3.
    

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

    
    b) Explain isomorphism with example. [4+4]

FirstRanker.com