<--BACK
Note
: This paper is of two hundred (200) marks
containing four (4) sections.
Candidates are required to attempt the questions contained in these sections
according to the detailed instructions given therein.
Answer
to all questions must be written in English only.
SECTION – I
Note
: This section consists of two essay
type questions of twenty (20) marks each, to
be answered in about five hundred (500) words
each. (2 × 20
= 40 marks)
1. (a) Design
an algorithm to reverse a singly linear linked list without using any
temporary
memory location.
(b) Construct
a binary tree representing the infix expression(a + b) k
(g – m) | f *
p – 5 * t and make it a post order threaded binary tree. (10
+ 10)
OR
(a) Give an
O(n2) time algorithm to find the longest
monotonically increasing
subsequence of
a sequence of n numbers.
(b) Write
Floyd-Warshall algorithm to solve the all-pairs shortest path
problems on a
directed graph G. Compute its time complexity. (10
+ 10)
2. (a) Given
the set of functional dependencies
{A ® BCD,
CD ® E, E ® CD,
D ® AH, ABH ® BD,
DH ® BC}
Find the non-redundant
cover.
(b) Given the
relation R(ABCDE) with the FD’s
{A ® BCDE,
B ® ACDE, C ® ABDE}
Give the
lossless decomposition of R. (10 + 10)
OR
Why is
frequency modulation superior to amplitude modulation ? Give
comparative
study between encoding and modulation. (20)
SECTION – II
Note
: This section contains three (3) questions
from each of the electives/specializations.
The candidate
has to choose only one elective/specialization
and answer all the
three
questions contained therein. Each question carries fifteen
(15) marks and is to
be answered in
about three hundred (300) words.
(3 × 15 = 45 marks)
Elective – I
3. Let G be
the grammar with productions
S ® AACD
A ® aAb
| l
C ® aC
| a
D ® aDa
| bDb | l
(15)
Convert the
grammar G into Chomsky Normal Form.
4. Design
Turing Machine which accepts language (15)
L = {an
bn cn
| n > 0 }
5. Give
deterministic finite automata accepting the set of strings of length five or
more in which
the fourth symbol from the right end is different from the left most
symbol defined
over the alphabet {a, b}. (15)
Elective – II
3. Describe
the construction of a typical parity check matrix for Hamming code over
GF(2) give its
code words and error correction capability. (15)
4. Explain
different components of a typical image processing system with diagram.(15)
5. Mention
various techniques of video files and explain any one technique in detail.(15)
Elective – III
3. The diagram
represents a network and the numbers on the arcs are their capacities.
A flow is defined
as follows :
(x,
y) : (s, a) (s, b) (s, c) (a, b) (a, d) (b, c)
f(x,
y) : 5 6 0 0 5
1
(x,
y) : (b, d) (b, e) (c, e) (d, t) (e, t)
f(x,
y) : 2 3 1 7 4
(i) What is
the value of f ?
(ii) Find an
f–augmented path and compute the value of augmented flow.
(iii) Find the
cut, which can justify the statement “Max flow = Minimum Cut”.(3
× 5 = 15)
4. Use revised
simplex-method to solve the following linear programming problem :
Maximize Z = x1
+ 2x2
Subject to the
constraint : x1
+ x2
< 3, x1
+ 2 x2
< 5
3
x1 +
x2 <
6 and x1,
x2 >
0 (15)
5. Derive the
Kuhn Tucker conditions for the following quadratic programming
problem and
find the value of x1,
x2 and
x3.
Maximize Z = –
x12
– x22
– x3
2+ 4x1
+ 6x2 subject
to the constraints :
x1
+ x2
< 2, 2 x1
+ 3 x2
< 12, x1,
x2 >
0
(15)
Elective – IV
3. Explain the
concept of feed forward Neural Network with an example. (15)
4. How
unsupervised learning is different from supervised learning ? Which is more
complex ?
Justify with an example. (15)
5. Prove that
fuzzy set A on, IR is convex if and only if
A(lx2
+ (1 – l)
x2) > min (A(x1),
A(x2) for all x1,
x2 ÎIR
and all l[0, 1]
where min
denotes the minimum operator. (15)
Elective – V
3. List out
any 8 features of UNIX and explain any two of them. (15)
4. What is
syntax of “create” system call in UNIX ? Write an algorithm for creating a
file.
(15)
5. How object
library, dynamic linking library and import library works in WINDOWS
environment ? (15)
SECTION – III
Note
: This section contains nine (9) questions
of ten (10) marks, each to be answered in
about fifty
(50) words. (9 × 10
= 90 marks)
6. Construct a
logic circuit diagram for the exclusive – OR function using only NOR
gates. (10)
7. Consider
the following graph-based locking protocol, which allows only exclusive
lock modes,
and which operates on data graphs that are in the form of a rooted
directed
acyclic graph :
– A transition
can lock any vertex first.
– To lock any
other vertex, the transaction must be holding a lock on the
majority of
the parents of the vertex.
Show that the
protocol ensures serializability and dead lock freedom. (10)
8. Explain
terms Aspect Ratio, Refresh Rate and Resolution of a Graphics Display
System. (10)
9. Let w =
{11, 13, 24, 7} and m = 31. Find all possible subsets of w that sum to m.
Draw the
portion of the state space tree that is generated. (10)
10. Explain
under what circumstances asynchronous and synchronous transmission
technique are
employed. Why asynchronous communications require additional
standard stop
bits ? What is wrong with letting the first-bit in a transmission act as
a start bit
and last one act as a stop bit ? (10)
11. Write an
algorithm to compute maximum and minimum of a given set of n
elements. (10)
12. Discuss
any two constraints imposed while designing an object model. (10)
13. Define the
role of “prototyping” and “4GT” paradigm in software engineering. (10)
14. Discuss
characteristics of deadlock in an operating system. (10)
SECTION – IV
Note
: This section contains five (5) questions
of five (5) marks each based on the following
passage. Each
question should be answered in about thirty (30) words.
(5
× 5 = 25 marks)
M/s Greenlay
Bank has just ventured into a retail banking system with the following
function (sub
processes) at the beginning :
– Saving Bank
accounts
– Current Bank
accounts
– Fixed
deposits
– Loans
– Demat
Account
With reference to above, answer the following qu
No comments:
Post a Comment