NMBV

www.android.previousquestionpapers.com | www.previousquestionpapers.com | www.ios.previousquestionpapers.
com
JJ JJ JJ JJ JJ JJ JJ J
Code No: 133BC R16
JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD
B.Tech II Year I Semester Examinations, April/May - 2018
JJ JJ JJ JJ
MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE
Time: 3 Hours
(Common to CSE, IT)
JJ JJ
Max. Marks: 75
JJ J
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) Construct the truth table for the following formula:
( P  (Q  R))  (( P  Q)  ( P  R)) [2]
b) Explain duality law. [3]
c) Give the formal definition for the composition of binary relations. [2]
d) What are the properties of a group? [3]
e) State addition principle and give an example of a problem solved by addition principle.
[2]
f)
g)
h)
State pigeon-hole principle.
P
What is the general form of a first-order recurrence relation?
Q
What is the generating function of 1,1,1,1,...
[3]
[2]
[3]
JJ JJ JJ PJJ JJ JJ JJ J
i) If a simple graph G contains n vertices and m edges, how many number of edges are
present in Graph G' (complement of G). [2]
j) How many edges are present in a complete graph with n vertices? Explain. [3]
PART- B
(50 Marks)
2.a) Show the following equivalence without constructing the truth table.
(( P  Q  A)  C)  ( A  ( P  Q  C))  ( A  ( P  Q))  C
JJ b)
JJ JJ JJ JJ JJ
Without constructing a truth table, show that A  E is not a valid consequence of
A  B B  (C  D) C  ( A  E) A  E
OR
JJ
[5+5] J
3.a) Obtain the principal disjunctive and conjunctive normal form of the following formula.
( P  (Q  R))  (P  (Q  R))
b) For the following formulas, let the universe be ℝ. Translate each of the following
sentences into a formula (using quantifiers):
JJ JJ JJ
i) There is a smallest number.
JJ JJ JJ JJ
ii) Every positive number has a square root. (Do not use the square root symbol; use only
multiplication.) [5+5]
J
www.android.universityupdates.in | www.universityupdates.in | www.ios.universityupdates.in
www.android.previousquestionpapers.com | www.previousquestionpapers.com | www.ios.previousquestionpapers.com
4.a) Consider the following Hasse diagram of a partially ordered set P, R , where
P  {x1 , x2 , x3 , x4 , x5 } . Find the least and greatest members in P if they exist. Also find
the maximal and minimal elements of P . Find the upper and lower bounds of
{x2 , x3 , x4 } , {x2 , x4 , x5 } and {x1 , x2 , x3 } . Also indicate the LUB and GLB of these subsets
if they exist.
b) Let n  N  and G1 , G2 ,..., Gn be groups, and consider
n
G
i 1
i : G1  G2  ...  Gn  {(a1 , a 2 ,..., a n ) : ai  Gi i  1,2,..., n} with the operation †
where if x  (a1, a2 ,..., an ) and y  (b1, b2 ,..., bn ) , then x† y  (a1b1 , a2 b2 ,..., an bn ), where
each product ai bi is performed according to the operation of the group Gi . Show
n
that G
i 1
i is a group. [5+5]
OR
5.a) Find the transitive closure of the relation R  {(1,2), (2,3), (3,4), (4,1)} . Show R i for all
values of i that give new elements of the transitive closure.
b) Find all the subgroups of (i) ( Z12 ,12 ) ; and (ii) ( Z 7* ,7 ) . [5+5]
6.
P
In the United States and Canada, a telephone number is a 10-digit number of the
form NXX  NXX  XXXX where N  {2,3,..,9} and X  {0,1,2,...,9} . How many
Q
telephone numbers are possible? The first three digits of a telephone number are called an
area code. How many different area codes must a city with 23,000,000 phones have? A
JJ JJ JJ PJJ JJ JJ JJ J
previous scheme for forming a telephone numbers required a format of
NYX  NXX  XXXX where N and X are defined as above and Y is either a 0 or a 1. How
many more phone numbers are possible under the new format than under the old format?
[10]
OR
7.a) How many four letter words can be formed using the letters a, a, a, b, b, c, c, c, c, d , d ?
b) Expand (2 x  y) 7 using the Binomial Theorem. [5+5]
JJ 8.a)
b)
JJ JJ JJ JJ JJ
Solve the recurrence relation an  2an1  3an2 for n  2 where a0  2 and a1  2 .
Using generating function find a n in terms of n if a0  1, a1  2 and
JJ J
an 2  5an1  4an for n  0 . [5+5]
OR
9.a) Solve the recurrence relation T (n)  4T (n  1)  2 n , with T (0)  6 .
JJ b)
JJ JJ JJ
Find the coefficient of x 2005 in the generating function
JJ1
(1  5 x) 2
.
JJ
[5+5]
JJ J
www.android.previousquestionpapers.com | www.previousquestionpapers.com | www.ios.previousquestionpapers.com
10.a) Determine whether the given pair of graphs is isomorphic?
b) Determine whether the following graph has an Euler circuit or path. [5+5]
OR
11.a) How do you test the planarity of a graph? Explain.
b) What are the chromatic numbers of the graph G and H? [5+5]
Q P
JJ JJ JJ PJJ ---oo0oo---JJ JJ JJ J

NMBV

Uploaded by

Copyright:

Available Formats

NMBV

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

NMBV

Uploaded by

Copyright:

Available Formats

www.android.previousquestionpapers.com | www.previousquestionpapers.com | www.ios.previousquestionpapers.

You might also like