JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD MCA 2017 MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE Previous Question Paper (August - 2017 - R15)

What do you mean by a well-formed formula? Give examples of formulas that are well-formed and not well-formed.

What do you mean by a lattice? List the properties of a lattice.

What are the two basic counting principles.

Give the generating functions for the sequences C(k,n), a^n, (-1)^n and n.

Is there a graph with degree sequence (1,3,3,3,5,6,6)? Justify your answer.

Show the following equivalences:
i) (P → C) ∨ (A → C) ⇔ (P ∧ A) → C
ii) (P → Q) ∧ (P → C) ⇔ P → (Q ∧ C)

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.

Obtain a principal conjunctive normal form of each of the following formulas:
i) ¬(P → R) ∧ (Q ↔ P)
ii) P ∧ (P → Q) → P

Show that (x)(P(x) → Q(x)) ∧ (x)(Q(x) → R(x)) ⇒ (x)(P(x) → R(x))

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.

Show that in a group (G, *), if for any a, b ∈ G, (a * b)^2 = a^2 * b^2, then (G, *) must be abelian.

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.

Find all the subgroups of (Z12, +12) and (Z7*, ×7).

How many ways are there to distribute 10 balls into 6 boxes with at most 4 balls in the first 2 boxes if:
i) The balls are indistinguishable
ii) The balls are distinguishable

Verify that C(n + 3, r) - 3C(n + 2, r) + 3C(n + 1, r) - C(n, r) = C(n, r - 3)

Find the number of integral solutions for the following:
i) x1 + x2 + x3 + x4 + x5 = 10 where xi ≥ 0
ii) x1 + x2 + x3 + x4 = 50 where x1 ≥ -4, x2 ≥ 7, x3 ≥ -14, x4 ≥ 10

Determine the coefficient of x^5 in (a + bx + cx^2)^10 and (x - 7y)^15.

Build a generating function for ar = the number of integral solutions to the equation x1 + x2 + x3 = r
i) 0 ≤ xi ≤ 3 for each i
ii) 2 ≤ xi ≤ 5 for each i

Write a generating function for na, the number of ways of obtaining the sum n when tossing 9 distinguishable dice. Then find 25a.

Solve the following recurrence relations using the characteristic roots:
i) an - 3an-1 - 4an-2 = 0 for n ≥ 2 and a0 = a1 = 1.
ii) an - 12an-2 + an-1 = 0 for n ≥ 2 and a0 = 4, a1 = 16/3.

Write the general form of a particular solution Pan to the following recurrence relations:
i) an - 7an-1 + 12an-2 = n
ii) an - 7an-1 + 12an-2 = 2^n

Demonstrate with an example breadth-first search algorithm.

Are the graphs shown below isomorphic? Justify your answer.

Obtain the minimal spanning tree for the following graph.

Draw a full regular tree of degree 2 and height 3.