http://www.makaut.

com

MATHEMATICS ( SEMESTER - 4 )

CS/B.TECH (CSE/IT)/SEM-4/M-401/09

1. ………………………………
Signature of Invigilator

2. ……………………………… Reg. No.

Signature of the Officer-in-Charge

Roll No. of the

Candidate

– – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – –
CS/B.TECH (CSE/IT)/SEM-4/M-401/09
ENGINEERING & MANAGEMENT EXAMINATIONS, JUNE – 2009
MATHEMATICS ( SEMESTER - 4 )
Time : 3 Hours ] [ Full Marks : 70

INSTRUCTIONS TO THE CANDIDATES :

1. This Booklet is a Question-cum-Answer Booklet. The Booklet consists of 32 pages. The questions of this
concerned subject commence from Page No. 3.
2. a) In Group – A, Questions are of Multiple Choice type. You have to write the correct choice in the
box provided against each question.
b) For Groups – B & C you have to answer the questions in the space provided marked ‘Answer
Sheet’. Questions of Group – B are Short answer type. Questions of Group – C are Long answer
type. Write on both sides of the paper.
3. Fill in your Roll No. in the box provided as in your Admit Card before answering the questions.
4. Read the instructions given inside carefully before answering.
5. You should not forget to write the corresponding question numbers while answering.
6. Do not write your name or put any special mark in the booklet that may disclose your identity, which will
render you liable to disqualification. Any candidate found copying will be subject to Disciplinary Action
under the relevant rules.
7. Use of Mobile Phone and Programmable Calculator is totally prohibited in the examination hall.
8. You should return the booklet to the invigilator at the end of the examination and should not take any
page of this booklet with you outside the examination hall, which will lead to disqualification.
9. Rough work, if necessary is to be done in this booklet only and cross it through.
No additional sheets are to be used and no loose paper will be provided
FOR OFFICE USE / EVALUATION ONLY
Marks Obtained
Group – A Group – B Group – C
Question Total Examiner's
Number Marks Signature
Marks
Obtained

…………………………………………………………
Head-Examiner/Co-Ordinator/Scrutineer
4521 (10/06)
CS/B.TECH (CSE/IT)/SEM-4/M-401/09
2

E
P AG
IS
TH
N
O
E
IT
R
W
T
O
N
O
D

4521 (10/06)
CS/B.TECH (CSE/IT)/SEM-4/M-401/09
3
ENGINEERING & MANAGEMENT EXAMINATIONS, JUNE – 2009
MATHEMATICS
SEMESTER - 4

Time : 3 Hours ] [ Full Marks : 70

GROUP – A

( Multiple Choice Type Questions )

1. Choose the correct alternatives for any ten of the following : 10 × 1 = 10

i) The generating function for the numeric function

 1 1 1 1 1 
 1‚ – 2 ‚ 3 ‚ – 4 ‚ 5 ‚ – 6 ‚ ……  is

1
a) log ( 1 + x ) b) log ( 1 + x )
x

1
c) ex d) log ( 1 – x ).
x

ii) If a network contains 6 vertices, then the number of cuts in the network is

a) 14 b) 15

c) 16 d) 32.

iii) The hamming distance between 0011011 and 0111001 is

a) 2 b) 3

c) 4 d) 0.

iv) The minimum number of edges in a connected graph having 21 vertices is

a) 18 b) 20

c) 10 d) 11.

4521 (10/06)
CS/B.TECH (CSE/IT)/SEM-4/M-401/09
4
v) The minimum number of pendant vertices in a tree with five vertices is

a) 1 b) 2

c) 3 d) 4.

vi) If S and T are two subgroups of a group G, then which of the following is a

subgroup ?

a) S U T b) S I T

c) S –T d) G – S.

vii) If R is a ring without zero divisors, then x . y = 0 implies

a) x = 0 or y = 0 b) x = 0 and y = 0

c) x = 0, y ≠ 0 d) x ≠ 0, y = 0.

viii) The solution of recurrence relation

a n + 1 – 2 a n = 5,

n ≥ 0, a 0 = 1 is

a) 6 . 2n – 5 b) 5 – 6 . 2n

c) 2n+1 – 1 d) none of these.

ix) Which of the following sets is closed under multiplication ?

a) { 1, – 1, 0, 2 } b) { 1, i }

c) { 1, ω, ω 2 } d) { ω, 1 }.

x) In a Boolean Algebra x + ( y . z l ) =

a) x +z b) xy

c) x+y d) x + y + z.

4521 (10/06)
CS/B.TECH (CSE/IT)/SEM-4/M-401/09
5
xi) The generating function corresponding to the sequence 1, 1, 0, 1, 1, 1, … is

1 2 1
a) –x b)
1+x 1+x2

1 2 1 2
c) +x d) 2 –x .
1+x 1–x

xii) The maximum degree of any vertex in a simple graph with 10 vertices is

a) 5 b) 9

c) 10 d) 20.

xiii) Let S be a finite set of n distinct elements. Then the number of bijective mapping

from S to S is

a) n2 b) n!

n!
c) d) 2n .
2

GROUP – B

( Short Answer Type Questions )

Answer any three of the following questions. 3 × 5 = 15

2. Show that the group ( Z 6 ‚ + ) is cyclic. Find all the generators of the group

( Z 6 = { [ 0 ]‚ [ 1 ]‚ [ 2 ]‚ [ 3 ]‚ [ 4 ]‚ [ 5 ] } ) .

3. If G is a finite group and H is a subgroup of G, then prove that O ( H ) is a divisor of

O ( G ).

4. Prove that the set of all even integers form a commutative ring.

5. Show that all roots of the equation x 4 = 1 form an Abelian group under multiplication.

6. Using generating functions solve the recurrence relation with initial conditions :

an = 2 an–1 for n ≥ 1, a 0 = 3.

4521 (10/06)
CS/B.TECH (CSE/IT)/SEM-4/M-401/09
6
GROUP – C
( Long Answer Type Questions )
Answer any three of the following questions. 3 × 15 = 45

7. a) Let G = { ( a, b ) : a ≠ 0, b∈R } and ✳ be a binary composition defined on G by

( a, b ) ✳ ( c, d ) = ( ac, bc + d ).

b) Let G be a group, if a, b ∈ G such that a 4 = e, then identity element of G and

ab = ba 2 . Prove that a = e.
a 0
c) Slow that the set of matrices   is a subring of the ring of matrices.
b 0

5+5+5

8. a) Using generating function solve the recurrence relation

a n – 7 a n – 1 + 10 a n – 2 = 0

for n > 1 and a 0 = 3, a 1 = 3.

b) Solve the recurrence relation a n = 8 a n – 1 + 10 n – 1 for n ≥ 1 and a 0 = 1.

8+7

9. a) Convert ( x + y ) ( y + z ) ( x l + z ) ( x l + y l
) into conjunctive normal form

x, y, z ∈ Boolean Algebra B.

b) Construct the truth table of the Boolean function

f ( x, y, z ) = ( yz + xz l ) ( xy l + z ) l . 5 + 10

10. a) If A, B and C are three sets, prove analytically that

A U ( B I C ) = ( A U B ) I ( 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

4521 (10/06)
CS/B.TECH (CSE/IT)/SEM-4/M-401/09
7
11. a) Examine whether the following two graphs are isomorphic :

dia

b) Find the adjacency matrix of the following digraph G :

dia

10 + 5

12. a) Find by Prim’s algorithm a minimal spanning tree from the following graph :

dia

4521 (10/06)
CS/B.TECH (CSE/IT)/SEM-4/M-401/09
8
b) Applying Dijkstra’s Algorithm find the shortest path from the vertex v 1 to v 4 in
the following simple graph :

dia

8+7

END

4521 (10/06)