West Bengal Institute of Technology (WBIT) 2009 B.Tech Computer Science and Engineering Mathematics - Question Paper
Mathematics
M401
2009
i .
C8/B.TECH (C8E/ID/8SM-4/M-401/09 3
ENGINEERING ft MANAGEMENT EXAMINATIONS, JUNE - 2009
Time: 3 Hours I [ Full Marks : 7C
GROUP - A ( Multiple Choice Type Questtoas )
1. Choose the correct alternatives for any ten of the following : 10 x 1 = 10
i) The generating function for the numeric function /
1 I .1 I _I ) I8
2 3 4 5 6.......J
a) log ( 1 + xJ b) log(. i+'x)
c) ex d) ~ log( 1 -x). 1 .....
II) If a network contains 6 vertices, then the number of cuts In the network is
a) 14 b) 15
c) 16 d) 32. 1
III) The hamming distance between 0011011 and 0111001 Is
a) 2 b) 3
. . '. . ' - \ ' ''
c) 4 d) 0. 1........
iv) The minimum number of edges In a connected graph having 21 vertices is
a) 18 b) 20
c) 10 . d) 11. |
v) Hie minimum number of pendant vertices in a tree with five vertices is
a) 1 c) 3
b) 2 d) * 4.
vi) If S and T are two subgroups of a group G, then which of the following is a subgroup ?
a) SUT c) S - T
b) Sn-T d) G-S.
vii) If R is a ring without zero divisors, then x. y = 0 implies
b) x - 0 and y = 0 d) x * 0, y = 0.
0 x - 0 or y - 0 c) x = 0, y *0
viii) The solution of recurrence relation
an+l-2an = 5
n St 0, a0 = 1
b) 5 - 6 . 2 n d) none of these.
a) 6 . 2 n - 5 c) 2 n + 1 - 1
ft)
x)
Which of the: following sets is closed under multiplication ? a) { 1, - 1, 0, 2 } b) { 1. t}
c) { 1, a, to2} d) {to, 1 }.
In a Boolean Algebra x + ( y . z') =
a) x + z c) x + y
b ) xy d) x + y + z.
xi) The generating function corresponding to the sequerjce 1, 1,0, 1, 1, 1, ... is
b)
d)
a)
c)
- X-
1 + x 1
1 + X
+ X*
1 + x2 1
-- jc2 2 X .
1 -x
1
xii) The maximum degree of any vertex in a simple graph with 10 vertices is
b) 9 d) 20.
a) 5 c) 10
xiii) Let S be a finite, set of n distinct elements. Then the number of bijective mapping from S to S is
0 n2
, n I c) -g-
b) n! d) 2n.
GROUP -B ( Short Answer Type Questions )
Answer any three of the following questions. 3x5=15
Show that the group ( Z6 , + } is cyclic. Find all the generators of the group (Ze*{[0), 11], 121.131,1 4 ]. [ 51} ) .
If G is a finite group and H is a subgroup of G, then prove that O ( H ) is a divisor of O ( G).
Prove that the set of all even integers form a commutative ring.
4.
5.
6.
Show that all roots of the equation x4 = 1 form an Abelian group under multiplication. Using generating functions solve the recurrence relation with initial conditions : an = 2an-l for 1. a0 - 3.
. GROUP-C
( Long Answer Type Questions )
Answer any three of the following questions. 3x15 = 45
7. a) Let G = { ( a, b ) : a * 0, b e R] and * be a binary composition defined on Gby { a, b) * ( c, d) - ( ac, be + d).
b) Let G be a group, if' a, be G such that a4 = e, then identity element of G and db= ba2. Prove that a = e.
a 0
is a subring of the ring of matrices.
c) Slow that the set of matrices
Lb 0
5 + 5 + 5
8. a) Using generating function solve the recurrence relation
0n-7an-l+ 10an-2 * 0
for n > 1 and a0 = 3, a t = 3.
b) Solve the recurrence relation an = 8 an_ t + 10 1 for n > 1 and a0 = 1.
8 + 7
9. a) Convert ix+y){y + z)(x'+z){xl+yl) into conjunctive normal form
* ' . , -x,y,ze Boolean Algebra B.
b) Construct the truth table of the Boolean function
' /(x, y, 2) = iyz + xz')[xy' + z)1. 5+10
10. a) If A, B and C are three sets, prove analytically that
A U(BflC) = (A U B) D (A U C).
b) Show that the intersection of two equivalence relations is also an equivalence relation.
C) Prove that the order of each subgroup of a finite group is a divisor of the order of the, group. 3 + 4 + 8
CS/B.TECH ECSE/IT) /SEM-4/M-401 /OO 7
11. a) Examine whether the following two graphs are Isomorphic :
B
Gt-
b) Find the adjacency matrix of the following digraph G
Oz
10 + 5
12. a) Find by Prims algorithm a minimal spanning tree from the following graph :
' 8
b| Applying Dijkstras Algorithm tad the shortest path from the vertex , to 4 In
the following simple graph :
8 + 7
END
|
Attachment: |
| Earning: Approval pending. |
