Download AKTU B-Tech 5th Sem 2015-2016 Modern Analytical Techniques Nbt 505 Question Paper

Code: 20MCA11

MCA I Semester Regular Examinations, February-2021

MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE

Time: 3 Hours Max. Marks: 70

Note: Answer all questions from Part-A & Part-B. Each question carries equal marks.

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

PART-A (10 x 2 = 20 Marks)

1. Answer all questions. Each question carries 2 marks

1. Define tautology and contradiction.
2. Write about converse and contrapositive.
3. Define partial order relation with example.
4. Write about Pigeonhole principle.

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

5. Define group and monoid.
6. Define homomorphism and automorphism.
7. Write about spanning tree.
8. Define chromatic number.
9. Define finite and infinite state machines.

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

10. Write about regular expressions.

PART-B (5 x 10 = 50 Marks)

Answer all questions. Each question carries 10 marks

1. (a) Obtain PDNF and PCNF of the formula
   (P ? (P ? ~Q)) ? (~P ? (~P ? Q))

   (OR)

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

   (b) Explain about rules of inference for propositional calculus.

2. (a) If f: A ? B and g: B ? C be two functions, then show that if g o f is one-to-one then f is one-to-one.

   (OR)

   (b) From 10 mathematics professors and 5 computer science professors, a committee of 6 is to be formed. How many different committees can be formed if

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

   1. There are no restrictions?
   2. The committee must contain at least 3 mathematics professors?
   3. The committee must contain at least 1 computer science professor?

3. (a) State and prove Lagrange's theorem.

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

   (OR)

   (b) Let (A, *) be a group. Show that (A, *) is an abelian group if and only if
   (a * b)² = a² * b², for all a, b ? A

4. (a) Explain Kruskal's algorithm with example.

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

   (OR)

   (b) Explain about graph coloring with example.

5. (a) Construct a finite state machine that accepts all strings over {a, b} containing "aba".

   (OR)

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

   (b) Convert the following NFA to DFA.

Get more at : FirstRanker.com