Jawaharlal Nehru Technological University Kakinada 2010 B.Tech Information Technology 2-1 ENGG.R07 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE SUPPLY SET-3 - Question Paper

Code No: X0522/R07 Set No. 3

II B.Tech I Semester Supplementary Examinations, May 2010

MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE

( Common to Computer Science & Engineering and info
Technology)

Time: three hours
Max Marks: 80

ans any 5 ques.

All ques. carry equal marks


1. (a) Let p,q and r be the propositions.
P: you have the ?ee
q: you miss the ?nal exam.
r: you pass the course.
Write the subsequent proposition into statement form.
i. P ? q
ii. 7p ? r
iii. q ? 7r
iv. pVqVr
v. (p ? 7r) V (q ?~ r)
vi. (p?q) V (7q?r)

(b) De?ne converse, contrapositive and inverse of an implication. [Marks 12+4]

2. (a) Let P(x) denote the statement. "x is a professional athlete" and let Q(x)denote
the statement" "x plays soccer". The domain is the let of all people. Write
every of the subsequent proposition in English.
i. ?x (P (x) ? Q(x))
ii. ?x (P (x)?Q(x))
iii. ?x (P (x) V Q(x))
(b) Write the negation of every of the above propositions, both in symbols and in
words. [Marks 6+10]

3. (a) De?ne a bijective function. discuss with reasons whether the subsequent func-
tions are bijiective or not. obtain also the inverse of every of the functions.
i. f(x) = 4x+2, A=set of real numbers
ii. f(x) = 3+ 1/x, A=set of non zero real numbers
iii. f(x) = (2x+3) mod7, A=N7.
(b) Let f and g be functions from the positive real numbers to positive real numbers
described by
f(x) = b2xc
g(x) = x2
compute f o g and g o f. [Marks 10+6]

4. (a) Let G be a group. Then prove that Z(G) = { x ? G/ xg = gx for all g ? G}
is a subgroup of G.

(b) Let P(S) be the power set of a non -empty set S. Let n0
be an operation in
P(S). Prove that associate legal regulations and commutative legal regulations are actual for the operation
n in P(S). [Marks 10+6]

5. (a) How many 10-digit binary numbers are there with exactly 6 1s ?

(b) There are 25 actual or false ques. an an exam. How many various ways can a learner do the exam if he or she can also select to leave
the ans blank

(c) obtain the number of non-negative integral solutions of x1 + x2 + ..... + xn = r.

(d) In how many ways the committees of five or more can be chosen from nine people.
[Marks 16]
6. (a) Let Sn denote the number of n - bit strings that do not contain the trend
111. Develop recurrence relation for Sn and initial conditions that de?ne the
sequence.

(b) Solve an + 3an-1 - 10an-2 = 0, n = 2, provided a0 = 1, a1 = four using generating
functions. [Marks 8+8]

7. (a) Derive the directed spanning tree from the graph shown Figure 7a
Figure 7a

(b) discuss the steps involved in deriving a spanning tree from the provided undi-
rected graph using breadth ?rst search algorithm. [Marks 8+8]

8. A mathematics department plans to o?er 7 graduate courses next semester,
namely combinatorics (C), group theory (G), Field theory (F), numerical analysis
(N), topology (T), applied mathematics (A), and real analysis (R). The mathematics graduate students and the courses they plan to take are as follows: [Marks 16]
learner Courses
Abe C,F,T
Bob C,G,R
Carol G,N
Dewitt C,F
Elaine F,N
Fred C,G
learner Courses
George A,N
Herman F,G
Ingrid C,T
Jim C,R,T
Ken A,R
Linda A,T

Earning:   Approval pending.