West Bengal Institute of Technology (WBIT) 2010-4th Sem B.Tech Computer Science and Engineering Computer Science - Mathematics - Question Paper
' Name :................. ...... ..............................
Roll No. : .......................................................
Invigilator's Signature:..............................................
CS/B.Tech (CSE/IT)/SEM-4/M-401/2010 2010 MATHEMATICS
Time Allotted: 3 Hours Full Mortis : 70
Thefgures in the margin indicate JuU marks.
Candidates are required to give their answers in their own words
as few as practicable.
GROUP - A (Multiple Choice Type Questions)
1. Choose the correct alternatives for any ten of the following :
10 x 1 - 10
i) The generators of the cyclic group ( Z, + ) are a) 1,-1 b) 0, 1
c) 0, - 1 d) 2,-2.
ii) The mapping / given by/(*) = | x |,xe Rls a) Injective b) Suijective
c) Bijective d) None of these.
iii) Let S be a finite set of n distinct elements. Tlie number of bijective mapping from S to S is
a) n2 b) n! /
c) 2n d) None of these.
Iv) If three Boolean variables x, y and z are defined on Boolean Algebra B, then which one of the following is a fundamental product ?
a) xy'z b) xy
e) xy{x+y) d) none of theses
, v) If G is binary tree on n vertices, the G has edges
a) n( n- 1) b) n -1
yl) Solution of the recurrence'relation Sn = 2Sn_ 1 with S0-llsSn.
a) 2 b) 2"-
c) 2n +1 . d) none of these.
vU) A complete graph is ,
a) regular b) connected simple
c) circuit d) planar graph.
viii) On the set A { 1. 2, 3 }, the relation fis { (2) 1), ( 1. 2), (3, 3 ) }. Then jR is
a) symmetric b) reflexive
c) transitive d) not a relation at all.
1j0 In the additive group Zg the order 6f the element [ 4) is
a) 0 b) 2
c) 3 d) 6.
30 Let G be a group and a e G. If o ( a ) = 17, then o ( a8 ) is
a) 17 b) 16
c) 8 d) 5.
xi) If S and T are two subgroup of a group G. then which of the following is a subgroup ? . . >
a) S U T b) S PI T
c) S-T d) G-S.
xii) Hie dual of a planar graph is dual. It is
a) True b) False.
xiii) A binary tree should have at least
a) one vertex b) two vertices
c) three vertices d) four vertices.
3dv) A connected graph is Eulerian iff it has no vertex of odd
degree. It is
' '1 \
a) Tine b) False,
xv) The number of idempotent element in Z is
a) 0 b) 1
cj 2 d) none of these.
GROUP-B ( Short Answer Type Questions)
Answer any three of the following. 3 x 5 =-15
2. Let G = { ( a, b ) : a 0.be R } and * be a binary compostion defined on G by ( a, b) ( c, d) = ( ac, be + d). Show that ( G,* ) is a non Abelian group. !
3. Show that for any two subgroups H and K of a group GHf\K is also a subgroup of G.
4. Let G be a group, Ii a, be G such that a4 = e, the identity element of G and ab= ba2, prove that a = e.
5. Prove that eveiy cyclic group is an Abelian group.
6. Show that the mapping F: (Z, ) - ( R, J defined by /(x) x2 Vxe Zis a monomorphism but not isomorphism,
' ' -
7. If in a ring R with unity, ( xy )2 * x2 y 2 Vx, y e R, then show that J? is a commutative.
GROUP-C (Long Answer Type Questions)
. Answer any three of the following. 3 x 15 = 45
8. a) Examine whether the following two graphs are
isomorphic.
b) Draw the dual of the graph.
c) Determine the adjacency matrix of the following di-graph :
9. a) Construct a simple logic circuit which would satisfy the truth table.
| |||||||||||||||
|
, . . : 5 |
b) Prove that a graph G has a spanning kee if and only If G is connected. 5
[ Turn over
i
c) Find the minimal spanning tree by Kruskal's Algorithm from the following graph G:
10. a) Consider the lattice L {1, 2, 3. 4. 6, 12}, the divisors of 12 ordered by divisibility. Find the lower and upper bound of L. Is L a complemented lattice ? 5
b) For any Boolean Algebra, show that.
. ' 5
c) Using generating function solve the recurrence relation, an~ 7an -I + 10a n - 2 * for n > 1 and a0 = 3,
11. a) Provethat the number of vertices to a binary tree is
always odd. ,
b) Find the truth table of the Boolean function
f = z'xy + xy'+ y. 5
. - . . ' . <, .
c) Prove that a complete graph with n vertices consist of n I P. number of edges. 5
12. a] Prove that the identity elements and the inverse of an
element in a group is unique. 5
b) Prove that in a group ( G, * ), ( a * b)
5
c) Prove that the set of matrices
|
' x 0 ' | |||
|
H |
: x e R,x* 0 | ||
|
. 0 x , |
' - |
forms a normal
subgroup of GL ( 2. R ), the grdup of all real non-singular 2x2 matricesunder multiplication. 5
13. a) Using Ford-Fulkersons algorithm, find the maximum flow in the following network :
CS/BiTech tCSteyrn/iSE<(!-4/M-401/2010
b) Using Floyd's algorithm, find the shortest path between
ij w2 and w6
ii) w j and tv q
4101 8
|
Attachment: |
| Earning: Approval pending. |
