--- Content provided by FirstRanker.com ---
--- Content provided by FirstRanker.com ---
JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD
--- Content provided by FirstRanker.com ---
2021 MCA I Semester Examinations, July/August - 2021
MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE
--- Content provided by FirstRanker.com ---
Time: 3 Hours--- Content provided by FirstRanker.com ---
--- Content provided by FirstRanker.com ---
Max. Marks: 75
--- Content provided by FirstRanker.com ---
Answer any five questions
All questions carry equal marks
--- Content provided by FirstRanker.com ---
- - -1.a)
--- Content provided by FirstRanker.com ---
Prove that the following statement is valid
p q
p (
--- Content provided by FirstRanker.com ---
q r)
--- Content provided by FirstRanker.com ---
s rs
--- Content provided by FirstRanker.com ---
b) Find the conjunctive normal form of q ( p q
) ( p
--- Content provided by FirstRanker.com ---
q) .
--- Content provided by FirstRanker.com ---
[7+8]
2.a)
--- Content provided by FirstRanker.com ---
Write the following sentences in the symbolic form
--- Content provided by FirstRanker.com ---
i) Arjun is a studentii) All students like easy courses
--- Content provided by FirstRanker.com ---
iii) Sociology is an easy course.
--- Content provided by FirstRanker.com ---
b)
Prove that the following argument is valid.
--- Content provided by FirstRanker.com ---
--- Content provided by FirstRanker.com ---
No mathematicians are fools.,--- Content provided by FirstRanker.com ---
No one who is not a fool is an administrator.
--- Content provided by FirstRanker.com ---
Sita is a Mathematician.
--- Content provided by FirstRanker.com ---
Sita is not an administrator.
--- Content provided by FirstRanker.com ---
--- Content provided by FirstRanker.com ---
[7+8]
--- Content provided by FirstRanker.com ---
3.a) Let A = (0, 1, 2, 3, 4) Show that the relation
--- Content provided by FirstRanker.com ---
R = [(0, 0), (0, 4), (1, 1), (1, 3), (2, 2), (3, 1), (3, 3), (4, 0), (4, 4)]
is an equivalence relation.
b)
--- Content provided by FirstRanker.com ---
Let X={1,2,3} and f, g, h and s be functions from X to X given by
f={(1,2), (2,3), (3,1)}, g={(1,2), (2,1), (3,3)} h={(1,1), (2,2), (3,1)}
Find: i) fog, ii) fohog.
--- Content provided by FirstRanker.com ---
--- Content provided by FirstRanker.com ---
--- Content provided by FirstRanker.com ---
[8+7]
--- Content provided by FirstRanker.com ---
4.a)
--- Content provided by FirstRanker.com ---
A={1,2,3,4}is a Relation R from A to A.R={(1,1),(1,2),(2,3), (3,4),}. S = [ (3, 1), (4, 4),(2, 4), (1, 4)]
Determine
2
--- Content provided by FirstRanker.com ---
2
RoS, SoR, R , S .
--- Content provided by FirstRanker.com ---
b)If f(x) = x+2, g(x) = x-2, h(x) = 3x, then find: i) gof ii) foh iii) hog .
[8+7]
--- Content provided by FirstRanker.com ---
5.a)
Using the principle of mathematical induction, prove that
--- Content provided by FirstRanker.com ---
n(n 1)(4n 1)
1 ? 2 + 3 ? 4 + 5 ? 6 + .... + (2n - 1) ? 2n =
--- Content provided by FirstRanker.com ---
3
b)
--- Content provided by FirstRanker.com ---
Prove that for any positive integer number n, prove that 3
n 2n is divisible by 3. [7+8]
--- Content provided by FirstRanker.com ---
6.a)
--- Content provided by FirstRanker.com ---
Use the mathematical induction to prove that
2
--- Content provided by FirstRanker.com ---
3n n for n a positive integer greaterthan 2.
2021
--- Content provided by FirstRanker.com ---
b)
Using the principle of mathematical induction, prove that
1/(1 2) + 1/(2 3) + 1/(3 4) + ..... + 1/{n(n + 1)} = n/(n + 1)
--- Content provided by FirstRanker.com ---
--- Content provided by FirstRanker.com ---
[7+8]7.a)
--- Content provided by FirstRanker.com ---
There are Three boxes I ,II and III Box I contains 4 Red 5 Blue and 6 White balls.
BoxII contains 3 Red 4 Blue and 5 White balls.
BoxIII contains 5Red 10 Blue and 5 White balls. One box is chosen and one ball is
drawn from it. What is the probability that
--- Content provided by FirstRanker.com ---
i) Red ball is chosen ii) Blue ball is choseniii) White ball is chosen
1
--- Content provided by FirstRanker.com ---
b)
Solve the recurrence relation. a
--- Content provided by FirstRanker.com ---
a 12a 10, a 0, a .[7+8]
--- Content provided by FirstRanker.com ---
n2
n 1
--- Content provided by FirstRanker.com ---
n0
1
--- Content provided by FirstRanker.com ---
3
8.a)
--- Content provided by FirstRanker.com ---
Prove that a graph G is a tree with n vertices if and only if It has (n-1) edges.
b)
--- Content provided by FirstRanker.com ---
Construct the minimum spanning tree for the following graph using Prim's algorithm.--- Content provided by FirstRanker.com ---
--- Content provided by FirstRanker.com ---
--- Content provided by FirstRanker.com ---
--- Content provided by FirstRanker.com ---
--- Content provided by FirstRanker.com ---
[7+8]
16
V1 V2
--- Content provided by FirstRanker.com ---
19 21 11 5 6
18 V6 14 10 V3
--- Content provided by FirstRanker.com ---
V5 33 V4
--- Content provided by FirstRanker.com ---
---ooOoo------ Content provided by FirstRanker.com ---