Download JNTUA MCA 2014 Aug Supple 1st Sem 9F00104 Mathematical Foundations of Computer Science Question Paper

FirstRanker.com
Firstranker's choice
FirstRanker.com

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

Code: 9F00104

MCA I Semester Supplementary Examinations August 2014

MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE

(For students admitted in 2009, 2010, 2011, 2012 & 2013 only)

Time: 3 hours Max. Marks: 60

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

Answer any FIVE questions

All questions carry equal marks

1. (a) Write short notes on natural forms.
   (b) Show that (?x) (P(x) ? Q(x)) = (?x) (P(x) ? ?(x) Q(x)) using rules of inference.
2. (a) What do you mean by proof of contradiction? Explain with a suitable example.
   

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

   (b) Show that ¬(¬Q ? (P ? Q)) ? ¬P by using automatic theorem proving.
3. (a) Define lattice. Let ‘n’ be the +ve integer and S_n be the set of all divisors of ‘n’. Let n=6 and D denotes the relations “Division”, ? a,b ? S_n aDb iff “a divides b”. Find out whether (S₆, D) is a lattice or not? Draw Hasse diagram.
   (b) Write short note on partial order relations.
4. (a) Show that the set G = {0, 1, 2, 3, 4, 5} is not a group under addition and multiplication module 6.
   (b) What is a monoid? Give three examples for a monoid.

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

5. (a) State and explain pigeon hole principle.
   (b) Let <R, +, .> be a ring and a,b,c be any elements of R. Prove the following:
   (i) a.(-b) = (-a).b = -(a.b)
   (ii) (-a).(-b) = a.b
   (iii) -(a+b) = (-a) +(-b)

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

6. (a) Find the number of integer solutions of the equation x₁ + x₂ + x₃ + x₄ +x₅ = 30. Under the constraints x_i > 0 for i = 1,2,3,4,5 and further x₁ is even and x₂ is odd.
   (b) Using generating function. Solve Y_n+2 -4Y_n+1+ 3Y_n =0 given Y₀=2, Y₁ = 4.
7. (a) Write and explain the procedure of BFS algorithm.
   (b) Construct the duals of the following planar graph.
8. Explain and exhibit the following: (i) A graph which has both an Euler circuit and a Hamilton cycle.
   

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

   (ii) A graph which has an Euler circuit but no Hamilton cycle.
   (iii) A graph which has a Hamilton cycle but no Euler circuit.
   (iv) A graph which has neither a Hamilton cycle nor an Euler circuit.

FirstRanker.com

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