Code No: 123BN
R15
JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD
B.Tech II Year I Semester Examinations, November/December - 2017
MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE
(Common to CSE, IT)
Time: 3 Hours Max. Marks: 75
Note: This question paper contains two parts A and B.
Part A is compulsory which carries 25 marks. Answer all questions in Part A.
Part B consists of 5 Units. Answer any one full question from each unit. Each
question carries 10 marks and may have a, b, c as sub questions.
PART- A
(25 Marks)
1.a) Define well-formed formulae and clause form. [2]
b) Write the statement in symbolic form then negate statements:
i) Some Drivers do not obey the speed limit.
ii) All dogs have fleas. [3]
c) If R is set of real numbers, then show that the function: F : R R defined by
f x 5x 3 1 is one-one function. [2]
d) Give an example of group which is abelian but not cyclic. [3]
e) From 6 boys and 4 girls, 5 are to be selected for admission for a particular course. In
How many ways can this be done if there must be exactly 2 girls? [2]
12 3 10
f) Determine the co-efficient of x in x (1-2x) . [3]
g) Find the generating function for the following sequence 0, 1, -2, 3, -4…. [2]
h) Define first order and second order recurrence relations. [3]
i) What is minimum spanning tree? Give an example. [2]
j) Define Bipartite graph and Isomorphic graphs. [3]
PART-B
(50 Marks)
2.a) Show that the following premises are inconsistent.
If Jack misses many classes through illness, then he fails high school.
If Jack fails high school, then he is uneducated.
If Jack reads a lot of books, then he is not uneducated.
Jack misses many classes through illness and reads a lot of books.
b) Show that R → S can be drawn from the premises P → (Q → S), ¬ R ˅ P and Q.
[5+5]
OR
3.a) Show that x P x Q x xP x xQ x .
b) Obtain principle disjunctive normal form of the following: [5+5]
p p q q q
www.ManaResults.co.in
4.a) If R and S are equivalence relations on a set A. Prove that R S is an equivalence
Relation.
b) Let B a, b, c and A P B be the power set of B. Draw the Hasse diagram for
and poset A. [5+5]
OR
5.a) Prove that every subgroup of a cyclic group is cyclic.
b) In any group G,* , by proving the inverse of every element is unique. Show that
a * b
1
b1 * a 1 , a, b G . [5+5]
iC n, i n2n 1 .
n
6.a) Show that i 1
b) In how many ways can 4 mathematics books, 3 history books, 3 chemistry books and
2 sociology books be arranged on the shelf so that all books of the same subject are
together. [5+5]
OR
7. State and prove extended pigeon principle. Using it show that 9 colors are used to
paint 100 houses at least 12 houses will be of the same color. [10]
8.a) Solve recurrence relation an=3an-1-2an-2 for n 2 .
b) Find the recurrence relation and initial condition for the following sequence:
6, -18, 54, -162 … [5+5]
OR
9.a) If the person invests Rs.10, 000 at 10% annual interest compounded quarterly, in how
Many months the money will become 15000.
b) Solve the following recurrence relation an1 2an 2n , n 0, a0 1 . [5+5]
10.a) Prove that a simple graph with n vertices and k components can have at most
n k n k 1 edges.
b) What is the shortest path between 1 and 7 in the following weighted figure 1?
[5+5]
Figure: 1
OR
www.ManaResults.co.in
11. Determine whether the given graphs have Hamilton circuits. If it has for such circuits
shown in figure 2. [10]
Figure: 2
---ooOoo---
www.ManaResults.co.in
