JNTU
JNTU MCA 2018 MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE Previous Question Paper (January - 2018 - R13)
Note: 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, c as sub questions.
PART - A
Define suitable predicates and symbolize each of the following:
i) Some of my friends are clever
ii) All clever people are boring
iii) None of my friends is wealthy
iv) Some of my wealthy friends are clever
v) All my clever friends are boring.
Answer
Let F(x) be 'x is my friend', C(x) be 'x is clever', B(x) be 'x is boring', and W(x) be 'x is wealthy'.
- (∃x)(F(x) ∧ C(x))
- (∀x)(C(x) → B(x))
- (∀x)(F(x) → ¬W(x)) or ¬(∃x)(F(x) ∧ W(x))
- (∃x)(W(x) ∧ F(x) ∧ C(x))
- (∀x)((F(x) ∧ C(x)) → B(x))
Determine whether the relation with the directed graph shown is an equivalence relation.
Answer
A relation is an equivalence relation if it is reflexive, symmetric, and transitive. For a directed graph, this means:
- Reflexivity: Every vertex must have a self-loop.
- Symmetry: For every edge from u to v, there must be an edge from v to u.
- Transitivity: If there is an edge from u to v and v to w, there must be an edge from u to w.
If the graph lacks any self-loops, lacks reverse edges for non-symmetric paths, or fails the composition requirement, it is not an equivalence relation.
Define product and sum rules and give examples.
Answer
Sign in to view the complete answer paper.
What is a generating function? Give the applications of generating function.
Answer
Sign in to view the complete answer paper.
How many edges does a graph have if its degree sequence is 4, 3, 3, 2, 2? Draw such a graph.
Answer
Sign in to view the complete answer paper.
PART - B
Using logical equivalences prove the following:
i) ~ (p q) (p ~ q)
ii) (( ~ ) ) ( ( )) p q r p q r
Answer
Sign in to view the complete answer paper.
Give the rules of inference in propositional logic.
Answer
Sign in to view the complete answer paper.
Prove by contradiction that there is no positive integer n such that n3 + 1 = 100.
Answer
Sign in to view the complete answer paper.
Obtain the principal disjunctive normal form of:
i) p ((p q) (q p))
ii) (p q) (p q)
Answer
Sign in to view the complete answer paper.
Let A = {3, 5, 9, 15, 24, 45} and for any a, b ∈ A, a ≤ b iff a divides b.
i) Draw Hasse diagram
ii) Find its maxima, minima, greatest and least elements if they exist.
Find maxima, minima, greatest and least elements of the set {3, 9, 15} if they exist.
Answer
Sign in to view the complete answer paper.
Give the definition of a group and list the properties of a group.
Answer
Sign in to view the complete answer paper.
If G is a group such that (ab)2 = a2b2 for all a, b ∈ G, then show that G must be abelian.
Answer
Sign in to view the complete answer paper.
Show that the following posets are lattices and interpret their meets and joins:
i) The poset of the divisors of 60, ordered by divisibility.
ii) The poset of the subsets of {0, 1, 2} ordered by the subset relation.
Answer
Sign in to view the complete answer paper.
How many strings of 10 ternary digits (0, 1, or 2) are there that contain exactly two 0s, three 1s, and five 2s?
Answer
Sign in to view the complete answer paper.
How many positive integers less than 1,000,000 have the sum of their digits equal to 19.
Answer
Sign in to view the complete answer paper.
State and prove binomial theorem by induction.
Answer
Sign in to view the complete answer paper.
Find the coefficient of x2005 in the generating function G(x) = (1-x)2/(1-x)2.
Answer
Sign in to view the complete answer paper.
Solve the recurrence relation an = an-1 + 2 with a0 = 5.
Answer
Sign in to view the complete answer paper.
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.
Answer
Sign in to view the complete answer paper.
Find the next two terms in the sequence 3, 5, 11, 21, 43, 85,... and give a recursive definition for the sequence.
Answer
Sign in to view the complete answer paper.
Find a minimum cost spanning tree in the following graph shown in figure 1.
Answer
Sign in to view the complete answer paper.
Obtain a coloring of the following graph shown in figure 2.
Answer
Sign in to view the complete answer paper.
Draw a planar representation of the following graph shown in figure 3.
Answer
Sign in to view the complete answer paper.
Explain isomorphism with example.
Answer
Sign in to view the complete answer paper.