Download JNTUA MCA 2018 July Reg-Supply 1st Sem 17F00101 Mathematical Foundations for Computer Science Question Paper

FirstRanker.com
Firstranker's choice
Code: 17F00101

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

Answer all the questions

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

1. (a) Write a note on mathematical induction.
   (b) Show that 1² + 2² + ...+ n² = wn > 1 by mathematical induction.
2. (a) Show that any positive integer n greater-than or equal to 2 is either a prime or a product of prime.
   OR
   (b) Let R be a binary relation on the set of all positive integers such that;
   

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

   R ={(a,b)/a — b is an odd positive integer}. Show that R is an equivalence relation.
3. (a) Prove that P? Q = ¬(¬P ? ¬Q) using truth table.
   (b) State and prove Lagrange’s theorem.
4. (a) Let (A, *) be an algebraic system where * is a binary operation such that for any a & b in A, a*b = a.
   (i) Show that * is an associative operation.
   

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

   (ii) Can * ever be a commutative operation.
   OR
   (b) Show that any subgroup of a cyclic group is cyclic.
5. (a) Show that every group containing exactly two elements is isomorphic to (Z₂, ?).
   (b) Write down the rules of sum and product.
   

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

   (c) In how many ways can two integers be selected from the integers 1, 2,..... 100 so that their difference is exactly seven.
   (d) In how many ways can two adjacent squares be selected from 8 x 8 chessboard.
6. (a) Five boys and five girls are to be seated in a row. In how many ways can they be seated if:
   (i) All boys must be seated in the five left most seats.
   (ii) No boys can be seated together.
   

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

   OR
   (b) Solve the recurrence relation:
   a_n —7a_n-1+10a_n-2 = 0 given that a₀ =0 & a₁ = 3.
7. (a) Determine the particular solution for the difference equation: a_n — 3a_n-1 + 2a_n-2 = 2ⁿ.
   (b) Write a note on total solutions.

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

8. (a) In a directed or undirected graph with n vertices, if there is a path from vertex V₁ to vertex V_n, then there is a path of no more than n-1 edges from vertex V₁ to vertex V_n. Prove this theorem.
   (b) Briefly discuss about shortest paths in weighted graph.
   OR
   (c) There is always a Hamiltonian path in a directed complete graph. Prove this theorem.
9. (a) Briefly discuss about operations on graphs.
   

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

   (b) State and explain the Kruskal's algorithm with an example.
10. (a) Briefly discuss about binary search tree.
    OR
    (b) State and explain the Prim’s algorithm with an example.
11. Let a=3ⁿ
    

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

    b=2ⁿ
    (i) Does a dominate b asymptotically.
    (ii) Does b dominate a asymptotically.