M.C.A. DEGREE EXAMINATION, 2008 Question paper - Annamalai University

[ganeshbala]

M.C.A. DEGREE EXAMINATION, 2008 Question paper - Annamalai University

( FIRST SEMESTER )
( PAPER - I )
110. MATHEMATICAL FOUNDATIONS OF
COMPUTER SCIENCE
( Old Regulations )
May ] [ Time : 3 Hours
Maximum : 100 Marks
Answer any FIVE questions.
All questions carry equal marks.
(5 × 20 = 100)
1. Solve the following LPP by big M method :
Maximize
z = 5x1 + 3x2
Subject to
2x1 + x2 < 1
x1 + 4x2 > 6
x1, x2 > 0.
2. Solve the following LPP by revised simplex
method :
Maximize
z = x1 + x2 + 3x3
Subject to
3x1 + 2x2 + x3 < 3
2x1 + x2 + 2x3 < 2
x1, x2, x3 > 0.
3. Solve the following LPP by Dual Simplex
method :
Minimize
z = 2x1 + x2
Subject to
3x1 + x2 > 3
4x1 + 3x2 > 6
x1 + 2x2 < 3
x1, x2 > 0.
4. Solve the following assignment problem :
Jobs
Men
I II III IV V
1 11 17 8 16 20
2 9 7 12 6 15
3 13 16 15 12 16
4 21 24 17 28 26
5 14 10 12 11 13
5. (a) Let A = { 1, 2, 3 }.
Let
be the matrices of relations R and S on
A. Find MSOR and MROS.
5. (b) Draw the Hasse diagram of the partially
ordered set of the divisors of 30 under
the divisibility ordering.
MR = [1 0 1
0 1 0
0 0 1 ]
and MS = [0 1 0
1 0 1
1 1 1 ]
6. (a) Let
A = { 1, 2, 3, 4 }.
Let
MR =
[0 0 0 1
0 0 0 0
0 1 0 0
0 0 1 0 ]
and MS =
[1 1 0 0
0 1 0 0
0 0 1 0
0 1 0 1 ]
be the matrices of relations R and S on A.
Compute the transitive closure of
R È S by using Warshall?s algorithm.
(b) Find a Boolean expression for f defined
in the following table :
x y z f(x, y, z)
0 0 0 1
0 0 1 1
0 1 0 0
0 1 1 0
1 0 0 1
1 0 1 0
1 1 0 0
1 1 1 1
7. (a) For the algebraic expression
( ( (2 × 7 ) + x ¸ y ) ¸ (3 ? 11)
construct a tree.
(b) Prove that a tree with n vertices has
n - 1 edges.
8. (a) Consider the machine whose transition
table is given below :
(Here S = { 1, 2, 3, 4 } is the set of states)
0 1
1 1 4
2 3 2
3 2 3
4 4 1
Show that
R = { (1, 1), (1, 4), (4, 1), (4, 4), (2, 2),
(2, 3), (3, 2), (3, 3), }
is a machine congruence.
(b)Let H=
[0 1 1
0 1 1
1 0 0
0 1 0
0 0 1
]
be a parity check matrix. Determine the
(2, 5) group code function
eH : B2 ® B



Source : ISC