MCN A

PGDCA / MCA (I Year) / BCA
Term-End Examination
December, 2006
CS-01 : GOMPUTERFUNDAMENTALS
Time : 3 hours Maximum Marks : 75
Note t - Question number 1 fs coJrr,pulsory. Answer any

three questionsfrom the rest.
l. (a) Simplifu the following expression using Karnaughls

map in product of sum form :
F (A, B, C, D) = I (1, 3, 7, 9, L2, 13' 15)
Also, draw the logic circuit for the simplified
expression. 5
(b) Conrrert the following decimal numbers to binary : 5
(i) 47.65
(ii) 702.29
(c) What is a FulFAdder ? Give the truth-table and draw
the logic diagram for the fulFadder. Also, explain its
functioning. 5
. (d) A flip-flop called T flipflop has the following
characteristics :
T = 0 No change of state
T = 1 Changesthe current state of the flip-flop
How will you construct T flip-flop using R-S flipflop ?
Draw the togic diagram also. 7 -
CS-01 P.T.O.
(e) show the outputs of the following assembly codes
step by step : 4+4
MOV AX, 3CD1 H

MOV CX, 2F77 H
TESTAX, CTaA H
JZ L1
ADD AX, OOOFH
DEC CX
Ll : XOR AX, CX
XOR CX, AX
XOR AX, CX
Show the contentsof AX and CX.
(ii) DATN( DW OOO5H

DATAY DW O
MOV CX, DATN(

MOV DX, OOOOH
MOV AX, DATN{
L5 : MUL DATN(
LOOP L5
MOVOnrexAx
MOV AX, DATN(
SHL AX, 02 H
SUB DATAY,AX
ADD 01
Show the contentof DATAY.
CS-O1
2. (a) Find the elror and explain one way to correct it
suB ISll , [BU
(b) Write a programthat addseachof the valuesdefined
in ARRAY1 and ARRAY2 and stores the sum in
"SUM" (i.e.SUM : sumof ARRAY1+ sum
of ARRAY2)
ARRAY1DB 10 20 30 40 50 60 70 80 90 100
ARRAY2DB 01 02 03 A4 05 06 07 08 09 010
SUM DB O 5
(c) Write a programto comPute: 8
F = (A x B) - (C + Dl /e
using zeroaddressmachinewhich has the following
instructions:
PUSH X Pusha valueX on to the top of the stack
POP X Pop the valueX from the top of the stack
ADD Addition
MUL Multiplication
SUB Subtraction
DIV Division
3. (a) What is a ripple counter ? Explain its working with

the help of a logic diagram. Comp are this ripple
counter with synchronouscounter. 6
(b) What is arithmetic pipelining ? Discuss with an
example. Comp are and contrast the
features,/characteristicsof arithmetic pipelining to
instruction pipelining.
CS-o1 P.T.O.
4- (a) Draw and explain the logic diagram for 8 words of
RAM using 3 x 8 decoder.(Assumethe word size to
be of 4 bits.) I
(b) What is a master-slave flip-flop ? Explain its
functioning with the help of a logic diagram. Also,
discussits importance for designingregisters. 7
5- comp areand contrastthe following : sxs:i5

(i) Dedicatedand MultiplexedBuses
(ii) Daisy chaining and Independent Requesting bus
arbitration schemes
(iii) Random Accessand Direct Access
(iv) Constant Angular Velocity (CAV) and Constant
Linear Velocity (CLV) disks
(v) 2D and Z*O memory organization
z
CS-O1 9,000
PGDCA / MCA (I Yr) / BcA
December, 2006
.{
CS-02 ; INTRODUCTIONTO SOFTWARE
Time : 2 hours Maximum Mal ks : 60
Note : Question number 1 is compulsory. Attempt any

L. (a) Design an algorithm and draw a corresponding

\r-n
flow chart to compute where 0 < n
;
(b) Write a shell program to generate the first "n"

terms of the following sequence without using
2, 4,8, 76, 32
multiplication 7
I
(c) Explain the different, categories of people involved

in system investigation and their activities. I
CS-02 P.T.O.
(d) Define mutual exclusion. How does a semaphore
solve the mutual exclusion problem ? Explain with the
help of an example. What are drawbacks of
semaphore ?
2. (a) Write context free grammar (CFG) for if-then-else

and assignmentstatementsof 'C'-language
. 5
(b) Explain the following loader schemes: 5

(i) Relocatingloader
(ii) Dynamic linker
.3.(a)WriteUNIXcommandsforthefollowing.'
(i) to print last 3 lines of a file.
(ii) to searcha particularpattern in a given file.
(iii) to count the number of words in a given file.
(iv) to list all the files with extension.txt.
(v) to move the contentsof one file to another file
with a different name
(b) What is a Virtual Memory ? Explain its advantages

and how it can be implemented. 5
4. (a) Explain the file system used in UNIX. Also explain

how do we mount the file systemin UNIX o/S . 5
(b) What is a feasibilitystudy ? Explain any three types

of feasibilitystudiesin brief. 5
CS-02
5. (a) What is X-Windowssystem? Explain the X-Windows
library and X-Toolkit in detail.
(b) How do we implement the macro facility within an

assembler? What are the issuesrelatedto the design
of a macro pre-processor? Explain with an example. 5
CS-02 5,000
,
PGDCA / MCA (I Year) / BCA
T"T--End Exarnination
December, 2006
.CS-03: FILE STRUCTUREAND

..PROGRAMMING
IN COBOL
Time : 2 hours Maximurn Marks : 60
Nofe ; Qu estion number 1 is compulsory. Answer sny

l. (a) How can SORTING of data in a data file be done

in COBOL ? Explainwith the help of an example. 5
(b) Why do you needsynchronisedclausein COBOL ?

Where do you use this clause ? Describe with the
help of an example. 5
(c) A me,Cicalshop has two branches which maintain

the customer recordsin the following format : 70
Customer file : (Not sorted)

Customer-no 10 characters
(unique acrossthe files)
Customer-name 25 characters
Doctor-name 25 characters
Medicine-code 10 characters
Date-of-purchase 10 characters
CS.O3 P.T.O.
Some of the customershave bought medicinesfrom
both the branches.The shop-ownerdecidedto close
one of its branchesand decided to merge the two
customerfiles so that customerrecord is kept at one
place. Write a program in CoBoL to merge the
two files. Make suitable assumptions, if dng, and
mention them.
(d) What are the various levets of working storage
section ? Give examplesfor at least two levels.
(e) Explain the various types of MOVE statements in
coBol- with the help of an example for each. 5
2. (a) What is the differencebetweena literal and figurative

constant? How many types of constantsare there in
COBOL and what are they ?
(b) How can you implement string "Find and Replace"
operation in COBOL ? Explain with an example.
3- Write a program in COBOL to cremtean indexed master

file from the files given below : 10
Employee master file :
Employee code 10 NUMBERS(Uniqueno.)
Employee_name 25 characters
Date-of-ioining 10 characters
Basic_salary 10 NUMBERS
CS-03
Employee Attendance Transactiol file :
Employee-code : 10 NUMBERS
No-of-days-present : 3 NUMBERS
The above two files are used to create an indexed payroll
file of the following format :
File name : ACCOUNT MASTER
Key : Employee-code
Total salary : Calculateas follows :
Basic-salaryxNo-of-days-present
Total salary(month):
Totaldaysin month
No te : Make suitable assumptions,if any.
4. (a) Why are files used to perform input-output

operations in COBOL ? Explain the OPEN,
CLOSE, READ and rWRITE statements I of
coBol.
(b) What arethe reasonsof using level 77 and level
88 entries in COBOL ? Explain with the help of an
example.
5. Explain the use and syntax'formatof each of the following

COBOL statements/uerbs,/clauses with the help of an
example for each : 10
(a) INSPECT TALLYING
(b) INVALID KEY Clause
(c) COMPUTE
(d) PERFORM
(e) AF|ER
CS-03 5,000
PGDCA / MCA (I Yr)
December, 2006
CS-04: DATA STRUCTURES THROUGH

"c't & "PAscAL"
Note r Qu estion number 1 is cotar.pulsory.Answer any

three questions f rom the rest. Alt algorithms
should be written nearer to C or PASCA:L
Ianguage.
l. (a) Write an algorithm and program code to implement

merge sort technique. 10
(b) Define solar systernas two dime-nsionalarray whose

elementscan be accessedusing STAR and PTANET
for the first subscript and SUN, EARTH, VENUS,
MOON, MERCURY as the secondsubscript. 5
(c) Write a C-function to insert an element into a AVL

tree 10
CS-04 P.T.O.
(d) Find the value of the following :
(i) abs(trunc (- 36.9))
(ii) round (+ 14.6)
(iii) trunc (sqrt (round(3.+yy1
(iv) abs(round(13.46:' round (18.6Tt)
(v) ord ('p' )
2'(a)
H::,,,::,:'t"l'H. ,,"-.:";*:
#::,,i:Tff::
complexity of the algorithm ?
(b) Write a program to exchange values of two variables

using pointers.
3. (a) Write an algorithm to compute the height of a given

Binary Tree.
(b) Explain the indexed sequential file organization. Write

a program to insert the following records into file
PERSONAL'.
(i) Adam Bede, 47, Engin eer
(ii) Silas Marner, 50, Doctor
Use a name field of siz,e20, age field of size 2 and

profession field of size 20.
CS-04
4. (a) Write a C-functionto count the number of nodes in
a linked list.
(b) Explain the purpose of MACRO with the help of

suitableexample.
5 . Write short notes on the following :
(a) Dynamic Memory Allocation 5

(b) SparseMatrix Representation 5
CS-04 7,000
i
December, 2006
CS-05 : ELEMENTSOF SYSTEMS

ANALYSIS & DESIGN
Time : 3 hours , Maximum Marks : 75
Note 3 Ansrreranvthree
";,:':n'""I{iulsorv
?::';,;;
1- (a) what is feasibility ? Describe any five types of

feasibilitystudy. 6
(b) Discussthe different types of systems g
(c) Explain the role of a SystemAnalyst. What are the

attributesof a good analyst? g
(d) What is a data dictionaryand why is it used ? What

are the major symbols used.in a data dictionary ?
Support your answerwith an example. 6
(e) Define Tangibleand IntangibleCosts and Benefits. 2
CS-05 P.T.O.
2 . (a) of a
Define System.Explain any four characteristics
System 5
(b) Elaboratethe five parts of the systemdesignprocess. 5
(c) List the major tasks of systemdevelopment 5
3. (a) What is testing ? Explain the variouslevelsof testing

involved in systemdevelopment.
(b) What is multimedia ? Explain the various
componentsof multimedia. 6
(c) Write a short note on "Civil Liability" 4
4. (a) What is the purpose of a DFD ? What are the

charting forms necessaryto draw a DFD ? List the
rules that govern constructionof a DFD
(b) Explain Preliminary Investigationas the first step in
the developmentof a system.What are the various
activitiesinvolvedin this step ? Explain them briefly.
5. (a) In an organization,a number of' project requestsare

generated. What methods are adopted by the
organization for selecting the requests to be
pursued?
(b) What are files and why are they needed ? Explain
briefly any,threetypes of file organizations. 5
(c) Write a short note on "Audit Trail". 4
CS-05 12,000
PGDCA / McA (I Yr)
December, 2006
CS-06 : DATABASE MANAGEMENT

SYSTEM
Time :"3 hours Mqximum Mqrks : 75
Note r Qu estion number 1 is compulsory. Attempt any

1. (a) A university registrar'soffice maintains data about

the followingentities: 10
(i) Course,includingnumber,title, credits,syllabus
and prerequisites
(ii) course offering, includingcoursenumber, year,
semester,section number, instructor(s),timings
and classroorn.
(iii) studenfs, including student-id, name and
program.
(iv) Instructors, including identification number,
name, departmentand title.
C5-06 P.T.O.
Further, the enrolment of studentsin courses and
grades awardedto studentsin each course they are
enrolledfor must be appropriatelymodelled.
Construct an E = R diagram for the Registrar's
office. Document all assumptionsthat you make
about the mapping constraints.
(b) Discuss the three level architecture of DBMS.

Explain how does it lead to data independence.
(c) With the help of an example, explain the inverted

file organization.
(d) What is a view ? Explain with the help of an

example.Also specifythe five conditionsthat a view
must meet in order to allow the updates.
(e) With the help of an example, explain how

knowledge representation can be done through
Semantic Network. 4
2. (a) Considerthe following 3 tables

PAINTER
PTR_NUM
PTR LASTNAME
PTR-FIRSTNAME
PTR INITIAL
PTR AREACODE
PTR PHONE
C5-06
GALLERY
GAL_NUM
GAL_OWNER
GAL_AREACODE
GAL PHONE
GAL-RATE
PAINTING
PNTG_NUM
PNTG_TITLE
PNTG-PRICE
PTR NUM
GAL-NUM
Write the relational algebraic expressions/queries for

the following operations :
(i) Find all painters who have painted in

GAL_NUM:4.
(ii) Find all paintings of Gallery whose rate is
(iii) Find the Gallery in which painter 'Ramesh' has
" displayed his paintings.

(iv) Find the number of paintings displayed in
'Shyam'.
Gallery owned by I
C5-06 P.T.O.
(b) Explain the concepts of Generalization and
Specialization with examples.
3. (a) Mention the features of OODBMS and give four

advantages of it.
(b) What are the general resistances faced by an

organization while implementing DBMS tool ?
Explain at least four of them
(c) What is client/s erver compuling ? Discuss the

components of client/server computing.
4. (a) Given the structure
PROJ PROJECT EMP EMP JOB CHG/ HRS TOTAL

NUM NAME NO NAIvTE CLASS HR BILLED CHARGE
13 Banking 103 RameshSystem 500 8 4000
Analyst
105 Ram Programmer 300 8 2400
26 Telecom 1 1 5 Amit Business 100 10 1000
Analyst
717 Shyam Engineer 300 7 2700
39 Finance 1 1 3 GopalTeam 1000 4 4000
Leader
720 Suresh DBA 800 3 2400
(i) Identify the anomalies in the given structure. 3

(ii) Normalise it upb third normal form (3NF). 6
(b) Explain any three aggregate functions of SQL with
an example for each.
C5-06
5. ,(a) Explain the structureof Index sequentialfile with the
help of a diagram. 5
(b) Explain briefly : 5
(i) Dynamic Data Exchange(DDE)
(ii) Object Linking & Embedding(OLE)
(c) Illustrate the differencesbetween hierarchical and
network data models. Explain why relational data
model is a better choice over the two.
C5-06 16,000
ADCA / MCA (II Year)
ry
December, 2006
CS -07 : DISCRETEMATHEMATICS
Time : 3 hours Maximum Mqrks ; 75
Nofe , Qu estion number 1 is compulsory. Answer any

l. (a) Write the negatiofl, converse and contrapositive of

'lf
the statement I get more than 9Ao/oin the higher
secondaryexamination,I will get admissionin some
engineeringcollege',in words.
(b) Let G : (V(G), E(G)) be a graph definedas follows :
V(G) : Set of all binary strings of length 3.
For Vl, vz € V(G),Vl vz € E(G)if v1 and vzdiffer
in only one position.
(il Draw the graph G.
(ii) Find a Hamiltonian cycle in the graph'
(c) L e t A = { 1 , 2 , 3 , 4 1 ,B : { 1 , 3 , 4 l a n d l e t R b e a
(
relation defined on A x B by xRy if 3 x + y S 5'
(i) Find the solution set R* of the relation.
(ii) RepresentR* by a coordinatediagram.
(iii) Find R-1.
CS-07 1 P.T.O.
(d) Give an example, with justification, of a compl ete
lattice with 8 elements. 4
(e) Find the missing entries in the following table : 4
P a P V A P t a
F F
T T
F T
(f) Find the domain of the function f , defined by
: t2:x
f(x) il?.
(g) Consid er the graph given below
v1
CS_07
(i) If the graph ulerian ? Justify your answer.
(ii) Apply Dirac theorem to check whether the
graph is Ha iltonian. If it is Hamiltonian, find a
Hamiltonian ycle with V1, V3 and v4 as the first
three vertice
(h) L e t U : { L ,2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 1 0 } ,
A : { 1 ,3 , 5 , 6 l ' B
, : { 1 ,2 , 7 , 8 , 9 } a n d
C : 14,56 , , 7,8, 9, 101.
Check that
( i ) A u ( B u C )- ( A u B )u C
( i i ) A u ( B n C ): ( A u B ) n ( A u C )
(i) L e t B : ( D ( 4 2 ) ,g . c . d . ,l . c . m . ) .
Draw the Hasse diagram of B.
Let o (x' xz, *3) = (xr A *z\ v (*2 A *3)'.
Find a (2, 14, 7) in B.
2. (a) Check whether the following system specifications

are consistent,using a truth table.
'The
systemis in multiusermode if and only if it is
operating normally.'
'lf it is
operatingnormally,the kernel is functioning.'
'The
systemis not in multiusermode or the kernel
is not functioning.'
'The
systemis operatingnormally.'
CS-07 P.T.O.
(b) Use the fusion algorithm to check wh etherthe graph
with the following adjacencymatrix is connected.
0 0 0 0 2
0 1 0 0 1
0 0 1 0 2
0 0 0 0 1
2 1 1 2 0
(c) Every Hamiltonian graph is ,Eulerian.Is this true ?
Give reasonsfor your answer.
3. (a) In a survey, r2o people were asked which of the

three TV programrnes a detective serial, a
comedy serial and a news magazine,did they watch.
60 said they watched the detective serial, 7 O said
they watched the comedy serial and 45 said they
watched !h" news magazine.Further, 40 said they
watched both the detective serial and the comedy
serial, 15 said they watched the detectiveserial and
the news magazine, 20 said they watched the
comedy serialand the news magazineand 5 watched
all the three programmes.
(i) How many watchedonly the comedyserial?
(ii) How many of those surveyeddid not watch the
comedyserial?
(iii) How many watched the comedy serial, but not
the detectiveserial?
(iv) How many watched none of the three
programmes?
CS-07
(b) Write 87 and 95 in 2's complement and find
87 15 in 2's complement.
(c) write (P v a) n I R in principal disjunctivenormal
form.
4.' (a) Find a minimal spanning tree in the following graph,

using Prim's algorithm.
v2
v5
(b) L e t X = { 1 , Z , 3 , 4 , 5 }
A { 0.2 0.3 0.1 0.4 03.l

n :
t l ' z
' B , T ' T]
r0.1 0.2 0.4 0.3 0'1.l
R
TJ
)
t 1 '2 ' 3
, 7 , TI
Check whether (A n B). = A ' U BC.
(c) I f f : A - + B a n d g : B - + C are two functions
such that gof is injective,mustf a n d g be injective ?
Justify your answer.
5' (a) Use the Karnaugh map to simplify the following

Boolean expression:
x1xzx3x4 + *rFzfg*+ + frxrF3x4 + f1f2f3x4
CS-07 P.T.O.
(r 2 3 4 5\
(b) Let f :l land
[s 1 2 5 L)
l 2 3 4 5 )
s: [ z
3 4 1 s )
Find fg as a product of disjoint cycles. Is fg even?
whv ?
(c) Find the binary tree representationof
(xy + yz). (xz + 1).
(d) 'x + y : 5' is a statement.Is this so ? Give reasons

for your answer.
t4,000
CS-07
Decernber, 2006
CS-08:NUMERICAL&STATISTICAL
COMPUTING

three questions from the remqining. Use of
calculatorsis not allowed.
l. (a) Identify the errors in the following statements and

give reasons :
(i) Complex constant declared as (282, 4DZ).
(ii) (- 2.0) * * 7-0
(iii) A .OR. B .OR. C (Let A, B and c be integers)
(b) Write FORTRAN expressions for the following

arithmetic expressions :
(i) pqt' + qcp
(ii) logro I sec x + 2 tan x I
( i i i l) p + i q l , i - F
CS-OB 1 P.T.O.
(c) Evaluatethe following integer expressions:
(i) 4**5/3
(ii) f*'r!**f
(iii) 3.0 + 7/5
(iv) 20/5.3
(d) Assume that P, O and R are defined. Write
FORTRAN statementswhich interchangethe values
of P, O and R such that P has Q's value,Q has R's
value and R has P's value.
(e) Write a FORTRAN program to evaluateT and print
x, g, T. Includeproper commentsin your program.
T:cos(x+ 2i/V2 + v2\+13* *+vl
4yl"l
for x : -.---1.0 to 4.0 in stepsof 0.5 and y : - 4.0
to 3'0 in stepsof 1.0. .
(fl Assumingthe declaration
INTEGER BAT(3, 3)
find the value assignedto ea.charray element in the
following program
DO 10 I : 1, 3
DO10J:1,3
IF(rLr4,5T
1o
ELSETF (r.EQ.J) THEN
BAT(1,J) : :- 4'0
ELSE
B A T ( I , J: )- 1 ' 0
ENDIF
10 CONTINUE
CS-OB 2
all students is
(g) In a McA class, the average marks of
is 58 and the
60. The average marks o{ boys
68' Find the
average marks of girl students is
percentage of male and female students.
line) of y on x
(h) Find the linear regression (regression
for the data
x -Z -1 0
y ( 6x 3) 2 2
second
(i) A bag contains4white and 5 blackballs'A
One bag is
bag contains 2 white and 4 black balls'
bag one ball is
chosen at random. From the selected
ball drawn is
drawn. Find the probability that the
white
that
0) If X is a Poisson random variate such
- -- 4)'
P(X : 1) = P(X 2), then find P(X
given.Write a
2. (a) A data (xi, f(x)), i : 1, 2, ..., N is
standard
FORTRAN Program . to compute the
has been
deviation of the data. Assume N
prescribed.Use dimension statement for reading
xi, f(xJ.
The
(b) Let A and B be two independent events'
probabilitythat both A and B happen is i and the
1
Find
probabilitythat neither A nor B happens is ;
P(A) and P(B).
P.T.O.
CS-OB
(c) Write a subroutine subprogram to multiply
two
matricesA and B eachof order 2 x 2 using
common
statement.
3. (a) Out of the following two regressio'n lines,

find the
regressionline of y on x.
I
x + 4 y = 3 , y + 3 x : 15
(b) Define an EeUIVALENCE statement.
What are its
advantages?
3
(c) Define Sequential and Direct files.
Discuss their
advantages and disadvantages.
4.
coefficient of correlation
vvr r vr(/
between x and y for the foilowing
;;r" , B
x 2 10 8 6 8
y 4 g g 1 0 6
(b) write a FORTRAN program to calcurate
and print
the number of A's in the foilowing
name
RAMASUBRAMANYAM. Assumethe
totarrength
of the field as 20.
5. (a) Explain the executionof the followingstatements

:
COMPLEX X
DIMENSIONB(3), E(- 6 , 6)
READ(S,10, ERR=30)t,A,B, (E(l),I - -
Z, Z), X
Give the sequenceof valuesafter the read
statement
is executed.
CS-OB
(b) A college purchasesthe following materials every
year. The prices in the years 1990 and 2000 are
tabulated.
Item consumption ot;Jffitn

"f[rft'
Black-boards 20 500 800
Pens 600 1 1'50
Registers 1200 12 16
white PaPer 110
looo 7s
(in rearns)
Envelopes 6000 0'50 0'75
Find the index number for the year 2000, with

1990 as base year, using the weighted aggregate
method.
(c) What are EXTERNAL statements and their
purpose ? Give their syntax.
CS.OB 11 , 0 0 0
ADCA'/ MCA (II Yr)
December, 2006
CS-09 : DATA COMMUNIGATIONAND

NETWORKS
Time : 3 hours Mqximum Marks : 75
Note r Qu estion number I is compulsory. Answer any

l. I(a) Under what conditions will satellite communication

be prefened over fibre optics ?
(b) Sixteen bit messages are transmitted using Hamming

Code. How many check bits are needed to ensure
that the receiver can detect and correct single bit
errors ? Show the bit pattern transmitted for the
m e s s a g e1 0 1 0 1 1 0 0 1 1 0 0 1 0 11 .
(q) Frames of 1500 bits are sent over 1 mbps channel

using geostationary satellite whose propagation time
from earth is 27 0 msec. Acknowledgements are
always piggybacked onto data frames. Three bit
sequence numbers are used. What is the maximum
channel utilisation for Go-Back-n protocol ?
CS-09 P.T.O.
(d) Show the relationshipbetweenASes, backbonesand
area routersin OSPF through a diagramand explain
the operationof OSPF algorithms.
(e) An organization is granted the IP address

130.34.12.64/26. The organizationneedsto have
4 subnets.What are the subnet addressesand the
range of addressesfor each subnet?
(f) Distinguish between bit rate and baud rate. Give an
example each, where both of them are same and
different.
(g) Calculate the maximum bit rate for a noiseless

channel with a bandwidth of 3000 Hz, transmitting a
signal with 4 signal,levels
2- (a) Why does the maximum packet lifetime, T, have to

be large enough to ensure that not only the packet
but also its acknowledgement have reached ? 2
(b) A large token ring has 100 stations and token

rotating time of 40 msec. The token holding time is
10 ms ec. What is the maximum achievable efliclency
of the ring ?
(c) Explain the operation of Internet congestion

algorithm through appropriate diagram. Also explain
the purpose of the following parameters : B
(i) Congestion window
(ii) Slow start
(iii) Threshold
CS-09
3. (a) Derive an expression for throughput of pure
ALOHA and slottedALOHA. Why is this value of
throughput less for pure ALOHA and how is it
improvedin slottedALOHA ? I
(b) A stop and wait protocol uses a 100 kbps satellite

link. It employs a round-trip propagation delay of
520 msec approximately.Find out the percentageof
time the sender is blocked to wait for
acknowledgement, if the frame sizeis
(i) 1000 bits
(ii) 2000 bits
(iii) 10,000 bits
4" (a) Is it possiblefor an applicationto enjoy reliabledata

transfer evenif the applicationruns over UDP rather
than TCP ? If so, how ?
(b) What is the relationshipbetweenthe number of slots

in frame and the number of input lines for
synchronousTDM ? Repeat it for asynchronous
TDM.
(c) What is the primary differencebetweenN-ISDN and

B-ISDN ? In B-ISDN, what is the differencebetween
a distributiveserviceand an interactiveservice?
(d) what is count to infinity problem ? Explain it

through an examPle.
CS-09 P.T.O.
5- (a) Why is Frame Relay unsuitable for real-time
communication such as teleconfeiencing ? '
2
(b) Draw the constellation diagrams for the following : 4
(c)
l, llilll
You have a leaky bucket. What should be its capacity
if the output rate is 5 gallons per minute, and there
is an input burst of 100 gallons per minute for
12 seconds and there is no input for 48 seconds ? s
(d) Define the following QoS parameters in the context
of ATM with appropriate examples : 4
(i) Constant bit rate
(ii) Real time yariable bit rate
(iii) Non real time variable bit rate
(iv) Available bit rate
CS-09 17,000
ADCA / McA (II Yr)
December, 2006
CS-10 : SOFTWAREENGINEERING
Note 3 Question number 1 is compulsory. Answer sny

three quesfions from the rest.
l. (a) Stores Department of ABC Organisation would like

to have a software for maintaining the Inventory.
The main objectives of this s/w are to rnaintain the
following : 20
(1) Detailsof the items in stock.
(2) Alert for the InventoryReorder level.
(3) Updation of the Inventory.
(4) List of the suppliersof the Inventory items-
CS-1O P.T.O.
Make assumptions,if necessaryand specifythem.
For the above mentionedsystem
(i) Develop a SystemRequirementSpecification.
(ii) DesignDFD upto two levels.
(iii) Derive a structurechart from the DFD
(iv) Give detaileddesignfor any two modules.
(b) Explain the CapabilityMaturity Model and its various

levels.
(c) What are Use Cases? Design a Use Case diagram

for a Library ManagementSystem
2- (a) Explain the Spiral Model and compare it with the

Linear Sequential, Rapid Prototyping and
(b) Differentiate between Process and ProrCuct.List any

two characteristics each for a product and a proc€ss 5
3. (a) Draw the ERD for a University Registration System. I
(b) Discuss the Basic, Intermediate and Advanced

COCOMO model
4. Write short notes on the following : 15

(i) CASE Tools
(ii) Software contiguration Management
(iii) Object Oriented Analysis
CS-1O
5. (a) What is RequirementsVerification? Discussany two
techniquesfor verifying requirements
(b) What is System Testing ? Explain, with example

RecoveryTesting and StressTesting.
(c) Differentiate between Top-Down and Bottom-Up

design
CS-1O 15,000
t cs-1rl
December, 2006
CS-12 : COUIPUTERARCHTTECTURE
1. (a) State the Bernstein'sconditions,basedon which two

processescan execute in parallel. For the following
example detect parallelism using Bernstein's
conditions : g
1 1: A - D x E
lZ:D: B + C
1 3 : A : B + D
1 4 :C : L + M
I b : E = X - Y
(b) Discuss the significance of Amdahl's law for a
multiprocessor system. Derive ' an expression for
speedupfor the same 6
(c) Explain the VLIW architecture.Demonstrate how
pipeliningis incorporatedin VLIW architecturefor a
degreem: 3. 7
CS.12 P.T.O.
(d) 'A 50 MHz processorwas used for executionof the
following program :
Instruction Instruction Clock cycle

''count
type count
Arithmetic 1000 1
Data transfer 2000 2
Control 2000 1
(i) The eflectiveCPI

(ii) MIPS rate
: (iii) Execution time
2. (a) Discussthe reasonsfor cachecoherenceproblemsin

a multiprocessorsystem.
(b) Discussthe snoopy bus protocols for bus connected
, computer systems.
3. (a) Describe any two memory models for building

scalable multiprocessors with distributed shared
memory.
(b) What arq the rationales for depeloping the
Fine-Grain multicomputers ? Comp are the
characteristics like communication latency,
synchronization overhead, Grain . size and
concurrency for the Fine-Grain, I\4edium-Grainand
Coarse-Grainmachines.
CS-12
4. (a) "The verg first multithreaded multiprocessor
Denelcor HEP failed to survive'due to inadequate
's/w and compiler support. The TERA
is its
descendantbut is implemented with rnodern VLSI
" Explain the
circuits and packaging technologies.
TERA designgoalsand its architecture:with the help
of appropriate diagrams.
(b) Explain the store-and-forward and wormhole
message routing schemes.And also, analyze their
communicationlatencies.
5. (a) "Pipelining techniquescan be applied to speed up

numerical arithmetic computations." Design a
pipeline systemto multiply two integers. 9
(b) Write short notes comparing 6
(i) CISC scalar processors vs. RISC scalar
processors.
(ii) PRAM vs. VLSI Models.
(iii) Shared variable model vs. Message passing
parallelprogrammingmodel.
CS-12 2 1, 0 0 0
ADCA / MCA (III Year)
December, 2006
CS-13 : OPERATINGSYSTEMS
Note r Qu estion number 1 is compulsory. Answer sny

1. (a) What is spooling? Explainhow this conceptaffects

the system performance 4
(b) List and explain at least four criteria that the
schedulers use for optimization and performance
improvement. Discuss the role of schedulers in
implementation of multiple-levei queues (MLQ)
scheduling. 7
(c) For the following page ref erence string
0 , g , o , 1 , 8 , 1 , 8 , 7 , 8 ,7 , 1 , 2 , 8 , 2 , 7 , 8 , 2 , 3 ,
8,3
" gve
J:
:ilJffiJHT:11,,"J#11Jt'11*
(i) FIFO
(ii) LRU
(iii) OPT (optimal) 6
CS-13 P.T.O
(d) Classify all types of multiprocessorsystems. Also
explainwhy sharedbus multiprocessorsare generally
regardedas having limited scalability.
(e) What is the importance of ordering of events in
distributed systems ? Is ordering of events important
in centralized systerns as well ? Explain.
2. (a) Consider the following three processes with the

Iength of the CPu-burst time given in milliseconds :
Process Burst Time

P1 8
P2 1
P 3 2
(i) Draw Gantt charts showing the execution of
these processes for the following scheduling
policies :
(1) FCFS
(2) SJF
(3) Round-Robin (quantum : 1)
(ii) Assuming that processes arrived in the order
P' P, P3 at time 0, determine waiting time
forthe
:nff::':##: *;:'process
(b) Define program relocatability. Compare and contrast
static and dynamic relocation. With the help of
diagram, illustrate dynamic relocation. Describe the
role of memory compaction in dynamic partitioning.
CS-13
critical section
3. (a) Define the terms mutual exclusion,
producQf - consumer
and Semaphores. Write the
I
code using semaphores'
resources with
(b) Differentiate reusable and consumable
algorithm and
example. write deadlock detection
mention its time comPlexitY'
the first-fit, best-fit

4. (a) with example for each, describe
free holes for
and worst-fit strategies for determining
and internal
allocation. Discuss the external
problems in multiple partition
fragmentation
allocation.
paging scheme'
(b) with the help of a diagram, describe
buffer helps in
Describe how translation look-aside
improvement of this strategY'
time is 200 ns'
(c) In a paging system,if memory access
hit ratio is 90o/o,
time to searchTLB is z0 ns and
time' Give
calculate the effective memory access
of page frames
relationship between page slze,flo'
and memory caPacitY'
and
5. (a) What do You mean bY device indePendence
with its
asynchronousl/O ? ExPlain disk caching
advantages.
protection' Also
(b) Explain Access-Matrix Model of
model is
discuss, how Bell-LaPadulaflow control
basedon it.
17,000
CS-13
MCA (Iil Year)
December, 2006
CS-14 : INTELLIGENTSYSTEMS
Note r Qu estion number 1 is compulsory. Attempt any

1. (a) What are the key features of a fifth generation

computer that will rnake it different from traditional
computers? Explainwith examples, 3
(b) What do you mean by "knowledge" ? Explain the
difference between "procedural" and "declarative"
knowledge 2+3:5
(c) Starting with two listsA : '(a b c) and
B : '(1 2 3 4) what will be the output of the
following operatibns? Justifyyour answer. 7x5:5
(i) (setfD (consA B))
."
(ii) (setfE (cdr D))
(iii) (setfF (list A B))
(iv) (setf G (cdr F))
(vl (setfH '(list A B))
cs-14 1 P.T.O.
(d) How does object oriented programming differ from
conventional programming ? Explain the concepts of
''method"
"class", "object", "mgssage" and with
respect to object oriented programming. 2+4:6
(e) What are the five different ontological building blocks

of Conceptual Dependency Theory ? Explain with
examples. 5
(f) Write an algorithm to search a tr:eeusing depth-first

strategy. Explain how this algorithm works on' the
following tree 6
2. Suppose you have a collection of objects which may be of

two types : circle or squ are. For a circle you need to store
its radius, and fbr a square you need to store the length of
its side. Suppose the number of objects i; n, and the
objects aret Oi On.
(i) Write a LISP code to store/represent the above

knowledge.
CS-14
(ii) Write a LISP function that takes as input any of the
above n objects,and returns its area as its output by
accessingthe above knowledge.
(iii) Write a Prolog code to do the same as items (i) and

(ii). SxS:75
3. (i) Distinguish 'Frame' 'Associative

between and
Network' as Knowledge Representation schemes. 5
(ii) Describe the following knowledge using an

associative network. Explain your scheme using
diagrams. 10
(a) Mohun Bagan is a club.
(b) A club consists of at least 100 members.
(c) Each club encourages sports and games.
(d) Football, Cricket and Hockey are types of

games and sports.
(e) Each sport and game is played by players.
(f) Football and Cricket are played by e\even

players. Volleyball is played by six players.
(g) The jersey of Mohun Bagan is maroon-&-green.
(h) All players other than Cricket players wear club

jersey.
CS-14 3 P.T.O.
4. (i) Considerth.e game of tic-tac-toe, where two players
put a 'X' or 'O' alternatively on the following nine
places:
7 8 9
Draw the search space for the next move starting
from
(ii) Use Truth Table method to prove De Morgan's

Laws.
(iii) What is hashing ? Explain with examplesthe terms
"symonym"and "collision" with respectto hashing.
6+4+5:75
5, (i) What is a rule-basedsystem ? Why is it called as

production system ? Explain in detail the forward
chainingprocessof inferencein productionsystem.
(ii) How does the RETE algorithm improve the
performanceof a pro.ductionsystem?
(iii) What is a General Problem Solver ? Explain the
technique of Means-End Analysis as a problem
solving strategy.
CS-14 15,000
MCA (III Year)
December, 2006
CS-l5 : RELATIONALDATABASE
MANAGEMENTSYSTEM
'Maximum
Time : 3 hours Marks: 75
Nofe r Qu estion number 1 is compulsory. Answer any

three questions from the rest.
1, (a) Considerthe followingrelations:

Emp(EmpNo,Ename,DNo, Sal)
Dept(DeptNo,Dnarne,DMgrNo)
Proj(ProjNo,ProjName,DNum)
Works-on(EmpNo,PNo, Hrs)
Write appropriate queries in SQL and relational
algebrafor the following : 2x5:7a
til Retrieve the names of all employees in a

departmentwho work for more than 10 h{s per
, week on 'Proj X' project.
(ii) Find the names and addressesof all emplo yees
who work for ResearchDepartment.
CS-15 P.T.O.
(iii) Find all the employees who do not work on any
project.
(iv) Find all the employeeswho work on all projects

of DepartmentNo. 5.
.
(v) For everyproject, list Project No, Dept No and
the Department Manager'sname, number and
salary.
(b) Why is the concurrency control needed ? Discuss with

examples.
(c) What is two phase locking protocol ? How does it

guarantee serializability ?
(d) Explain the architecture of DBMS with the help of a

diagram. 4
(e) Access methods are measured by access and storage

efficiencies. Define each term and its major objectives.
Which is the most important consideration in a batch
environment ? Give reasons.
2. (a) What is log ? How can log be used to recover from

failure ? How is log based recovery different frorn
checkpoint recovery ?
(b) What are the different security policies ? Discussany

two of them
CS-15
3. (a) Draw an ER diagram for a bank. Each bank can
have multiple branches and each branch can have
multiple accounts and loans. List all the entities and
relationships between them. Also list all the
constraints. State all the assumptions made. B
(b) What is a functional dependency ? When are the two
4. (a) Discuss the advantages and disadvantages of

OODBMS in comparisonwith RDBMS.
(b) Explain the different access strategies. State how the

availability of such access aids influences query
processing.
'
5. (a) What is a , timestamp ? How does the system
generate timestamps ? Discuss the timestamp
ordering protocol for concurrency control.
(b) Discuss the term Normalization. What are the

BcNF and sNF
rorms? ExPrain
*f;':::#,:"'
CS-15 2 1, 0 0 0
ADCA / MCA (III Yr)
E
December, 2006
CS-16 : OBJECTORIENTEDSYSTEMS
Note r Question number 1 is compulsory. Answer any
1. (a) An Environmental controller monitors the climate for

gardening. A gardening plan is executed to monitor
the climate for a crop. The controller has heater,
cooler and light. These parts of the controller are
started and shut down by an Actuator protocol
depending on the temperature measured. Draw a
class diagram for this gardening system
(b) Justify that the abstraction and encapsulation are

complementary to each other.
(c) List and explain any three purposes served by the

models.
(d) How does object oriented analysis differ from object

oriented design ? Give at least three differences.
C S - 16 P.T.O.
(e) How can the three models of object oriented system
be combined ? I ist the mapping between, these
models.
2. (a) Prepare an object diagram for dining philosopher

problem. There are five philosophers and five forks
around a circular table. Each philosopher has access
to two forks on either side. Each fork is shared by
two philosophers. Each fork may be either on the
table or in use by a philosopher. A philosopher must
have two forks to eat.
(b) Draw an instance diagram for evaluating the

expression (X/2 + Y /3) / (X/2 + Y), where an
expression is a combination of two variables (X, Y)
. f . t ,
and/or constant .o*b,.,ed by a binary operator in

the middle. An expression along with variables and
constants is called a term. 7
3. (a) Draw a state diagram for process that can be either

running, or waiting for its turn or performing an l/O,
or waiting for an interrupt from the operating system. 6
(b) Differentiate between activity and action with the help

of an example.
(c) How does the Nested state diagram differ from Flat
state diagram ? Give an example'of Nested state
I
diagram.
CS-16 2
How does Data flow differ from Control flow ? Give
three differences
Using,quadraticformula as a starting point, prepare

a Data flow diagram for computing roots of
quadraticequation u*2 + bx + c : 0. Real nurnbers
a, b, c are inputs. Outputs are x : R1 and x : R2
which satisfy the equation. The quadratic formula
|
t , /l .b2 ' - 4 .a c \I
r, sl -i b
% |
\ )
What do you understand by functional constraints ?

Give an example to explain it.
Explain the following terms, with an example of

each :
(i) Multiple Inheritance
(ii) Generalization
(iii) Overriding
(b) What is a scenario ? Explain it with the help of an

example.
(c) What is an abstract class ? How is it different from a

concrete class ? 3
CS.16 17,000
December, 2006
CS-51 : OPERATIONSRESEARCH

three more quesfions from quesfionsnumbered
2to5.
l. (a) A factory engaged in the manufacturing of pistons,

rings and valves, for which the profits per unit are
Rs. 10, 6 and 4 respectively, wants to decide the
most profitable mix. It takes one hour of preparatory
work, ten hours of machining and two hours of
packing and allied formalities for a piston.
Corresponding time requirements for rings and
valves are 1, 4, 2 hours and 1, 5, 6 hours
respectively. The total number of hours available for
preparatory work, machining and packing & allied
formalities are 100, 600 and 300 respectively.
Determine the most profitable mix, assuming that
what all is produced can be sold. Formulate the LPP.
(b) What are the applications of O.R. ? Give any four

applications.
CS-5i P.T.O.
(c) What are the four factors that influence inventory
control ? 4
(d) List any four limitations of simulation. 4
(e) A department head has four tasks to be performed
and three subordinates; the subordinates differ in
efficiency. The estirnates of the time, each
subordinate would take to perform, is given below in
the matrix.
How should he allocate the tasks, one to each man,

so as to minimize the total man-hours ?
Men
Task
I 9 26 15
il 13 27 6
ilI 35 20 15
IV 18 30 20
(f) An airlines organisationhas one reservationclerk on
duty in its local branch at any given time. The clerk
handlesinformation regardingpassengerreservation
and flight timings. Assume that the number of
customersarriving during any given period is Poisson
distributedwith an arrival rate of eight per hour and
that the reservationclerk can servea customerin six
minutes on an average, with an exponentially
distributedservicetime
(i) What is the probabilitythat the systernis busy ?
CS-s1
(ii) What is the average time a customer spends in
the system ?
(iii) What is the average length of the queue and

what is the number of customers in the
sysr"f ?
2. (a) Find the optimum integer solution to the given LPP

by cutting plane method. 10
Max z = 4*, + 3*,

A t 1
i
s.t.
*1 + 2*,
2*, + *z
*r., x'2
(b) Define Queueingmodel. Give any four characteristics

of the Queueingmodel
3. (a) Determine*1, *2,*3 so as to maximize
z- *', + 4*,+ 6*,

"? "?
s.t.
xl+*2
Zxt + 3*,
*1' *2
CS-51 3" P.T.O.

(b) Solve the following problem using dynamic
programming problem :
M i nz : V ? * v3+ y 5 2
s .t .
y1 + g2 + gS 2 15
91, V2, V3
4. (a) A firm has three factorieslocatedin City A, city B

and City C and suppliesgoodsto four dealersspread
all over the country. The production capacities of
these factoriesare 1000,700 and 900 units per
month respectively.The return per unit product
varies for different combinations of dealers and
factorieswhich is given below :
Dealers Factory
Factory
l Z 3 4 c a p a c i t y
City A 6 6 6 4 1000
City B 4 2 4 5 700
City C 5 6 7 8 900
Dealer
9oo 800 500 400 2600
requirement
(i) Determine a suitablealiocationto maximisethe

total net return using Vogel Approximation
Method.
(ii) Is this solution optimal ? If not, what will be
optimal ? B
CS-s1
(b) Solve the game whose payoff matrix is given by
Player A
A1 A2 A3
B1 t - 1 3 1 l
t l
Player B 82 o -4 -3 I
B3
I 1 5 -1 l
L_
(i) What is the optimum strategyfor Player A and
Player B ?
(ii) What is the value of game ?
(iii) Give nature of game.
5. (a) Define the following terms and give one example of

each (any two\ : 6
(i) SaddlePoint
(ii) Safep Stock
(iii) Convex Polygon
(b) Obtain the dual problem of the following primal
problern : 7+2:9
Min z: x1 3*, 2*,
s.t.
CS-s1 17,000
December, 2006
CS -54: FINANGE& ACCOUNTINGON

COMPUTERS
Time : 3 hours Msximum Mqrks : 75
Nore' anY
A'ftemP'f
7;:::";,:,i::?,:": :::::tscirv
'Accounting
1. (a) What is meant by concepts' ? Examine
the role of accounting concepts in the preparation of
financial statements.
(b) What is a Balance Sheet and what information does

it convey to an outsider ?
2. (a) A firm purchases a plant for a sum of Rs. 10,000

on 1tt January 2000. Installation charges are
Rs. 2,000. Plant is estimated to have a scrap value
of Rs. 1000 at the end of its useful life of five years.
'Plant
You are required to prepare the Account' for
three years charging depreciation according to
(i) Straight Line Method, and
(ii) Written Down Value Method.
CS-54 P.T.O.
(b) Discussthe concept of working capital.Are the gross
and net concepts of working capital exclusive ?
Explain.
3. (a) What is meant by Cost Accounting ? State its

objectives.
(b) From the following particularscalculate
(i) Contribution per unit
(ii) P/V Ratio
(iii) Break Even Point in units
(iv) Break Even Point in rupees
(v) What will be the Selling Price per unit if the

Break Even Point is brought down to 25,000
units ? ' 70
Rs.
Fixed Expenses 1,50,000
VariableCost p.u. 10
Selling Price per unit 15
4. What is leverage? Explain the types of leveragewith the

help of a suitableexample. 15
CS-54
5. (a) A company has just purchased a new plant for
Rs. 75:000. The effective life of the plant is three
years and it has no salvage value. The estimated
cash flows after tax are as follows :
Year Cash Flow After Tax

Rs.
1 30,000
2 35,000
3 40,000
Compute Net Present Value at 10o/orate of
discount. The present value of Re. 1 at 10o/o
discountrate is
Year 1 0'g0g
Year 2 A'826
Year 3 0'751 10
(b) Write short notes on the following : 20
(i) Trading on Equity
(ii) Zero BasedBudgeting
(iii) Flexbilityin capital structure
(iv) Difference between Schedule of Changes in
Working Capital and FundsFlow Statement
CS-54 17,000
MCA (Revised)
December, 2006
MCS-011: PROBLEMSOLVINGAND
PROGRAMMING
Time : 3 hours Maximum Marks ; 100

(Weightage750/o)
Note t Qu estion number 1 is compulsory. Attempt any

three questions from the rest,
l. (a) Write an algorithm and draw a correspondingflow

chart to print the sum of all integersstartingfrom 2
to the given positiveintegerx where x > 2. 10
(b) 'C'
Write a recursiveprogram in to find the L.C.M.
(LeastCommon Multiple)of two given numbers. 10
(c) 'C' to print the following
Write a program in
format : 70
C :
C C C
C C C C C
C C C C C C C
C C C C C C C C C
MCS-01 P.T.O.
(d) 'C'
Write a non-recursive procedure in for calculating
power of a number 'm' 'n'
raised by another number
. n
r.e.m 10
2. (a) Design an algorithm and draw corresponding flow

chart to print the value of the number in words when
the number entered is in the range of 1 to 299. 10
(b) 'C'
Using pointers, write a program in to count the
occurr ence of each character in a given string 70
3. (a) Write a program in

'C'
that accepts 10 words of
varying length and arranges the words in the
descending order of word length. [Jse arrays. 10
(b) Write a program in

'C'
for the multiplicationof two
matrices. 70
4. (a) 'C'
Write a program in to check whether a given
string is palindrome. (Jse pointers 10
(b) 'C'
Write a program in for the addition of two
polynomials. (Jse Arrays and Structures 10
5. (a) 'C'
Write a program in that accepts two files as input
and creates a new file whose contents include the
contents of two input files. 10
MCS-011
(b) Consider a data file containing some records of type
sruDENT: 5+5:70
Struct STUDENT
{
char Name[z}];
int Roll-No;
float marks;
l;
(i) Write a function, which takes file name as an
argument and returns the number of records in
that file.
(ii) Write a function, which takes two arguments :

filename and Roll-No(s) and deletes the
corresponding records with these Roll-Nos from
that file.
MCS-011 11 , 0 0 0
MCA (Revised)
Tbrm-End Examination
December, 2006
MCS-012: COMPUTERORGANISATION&
ASSEMBLY LANGUAGE PROGRAMMING
Time : 3 hours Maximum Mqrks : 700

(Weightage75o/o)
Nofe 3 Question no. 7 is compulsory and csrries 40

mqrks. Attempt qny three questions from the
rest.
(a) Constructthe Karnaughmap for the function

F(A, B, C, D) : I(0 , 2, 4, 5, 7, 10, 13, 15) and
find the function in SOP form. Also, draw the logic
diagram using NOR gates only.
(b) What is the difference between direct and indirect

address instruction ? Show how many memory
references are required for each type of instruction
to bring an operand into processor register.
MCS-012 P.T.O.
(c) Use a 8-bit binary representationfor integers using
signed 2's complement notation. Perform the
following operations and also indicate the
overflow/underflowif it.occurs :
(i)
(ii)
(iii) 65 + (- 61) \
(iv) 98+ 30
(v) 20 90
(d) Design and draw the combinational circuit that

convertsa hexadecimalinput to an equivalentBCD . 5
(e) Discussthe use of parip bits for error detection.How

is Hamming code useful for error detection and
correction ? Demonstratethe use of Hamming code
for a 4-bit word sequencetransmitted as 1010
whereasreceivedas 1000 10
(fl Write an assembly program to find whether two

strings, stored in memory, match or not. 5
k) Give two reasons why a RISC processor is better

,than a CISC processor.
MCS-012 2
level 2 '
2. (a) what is RAID ? List three featuresof RAID
In RAID technology, what are the important
performanceconsiderations? Explain briefly
a 4-bit
(b) Using a 4-bit counter with parallel load and
to
adder, draw a block diagram that shows how
implement the following statements:
X'RreR1 +Rz
X ' Y , R t e R 1+ 1
RZ is a
where R1 is a counterwith parallelload and
4-bit register.
(c) Write an assemblyprogram for adding two five-byte

numbers using arraYs
(d) What is interrupt ? Briefly explain the four interrupt

conditions
Explain
3. (a) what do you mean by associativememory ?
briefly the concept of Match-logic'
briefly'
(b) what is FAT ? Explain the structureof FAT
FAT
Calculatethe number of entries requiredin the
table using the following parametersfor an MS-DOS
system :
Disk caPacitY: 30 MB
Block size: 5I2 bYtes
Blocks/Clusters: 4
P.T.O.
MCS.O12
(c) Give characteristicsof unencoded and highly
encoded microinstructions.
5
(d) Write a program to evaluate the following
expression
using one address machine :
X : y + Z * W * S t ,
4' (a) Explain the working of CD-ROM and DVD-ROM

with the help of block diagram.
s
(b) What is master-slaveflip-flop ? Construct a master
slaveflip-flop usins D flip-flop and explain its
working
over other flip_flops.
s
(c) Design a logic circuit capableof performing
both the
paralleladditionand subtractionof numbers.
s
(d) Define the basic characteristicsof the following
I/O
(i) LCD Monitors

(ii) Laser Printer
(iii) Mouse
(iv) Scanner
(v) Modems
MCS-OX2
5. (a) What are the advantagesof using SRAM ? Why do
we use L1 and L2 cache memories? How is a main
memory address mapped to a cache address ?
Assume the main memory size of 1 K words,
1 cache block size : 32 bits, number of cache
slots : 16 and cache mapping : 2 way set
associative.
(b) Write an assembly program to add two 4-digit

packed BCD numbers.
(c) What is the difference between floating point and

fixed point number formats ? Explain the floating
point format briefly with the help of an example.
What is the precisionw.r.t. floating point numbers?
MCS-012 11 , 0 0 0
MCA (Revised)
December, 2006
MCS-013 : DISCRETEMATHEMATICS
Note r Qu estion number 1 is compulsory. Attempt sny

l. (a) Find a formula for f-l when f(x) : 2x 3, x € R.

Also tell the domain and codomain of f-1.
(b) If A, B, C are pairwise intersecting sets, draw a Venn

diagram to represent A U (B n C).
(c) Use a Truth Table to show that p n q n (-p) is a

contradiction
(d) If 11 shoes areto be selectedfrom 10 pairs of shoes,

prove that there must be a pair of rnatching shoes
amongst the selection.
(e) Find the number of permutations that can be formed

from all the letters of the word MISSISSIPPI. 2
MCS-013 P.T.O.
(f) Write down all the partitions of 7. Also find Pf and
P5
'7
(g) Find the logic circuit corresponding to the Boolean

expression
(xtv*zIn*3
2. (a) Consider the functions f(x) : *2 + 1 and g(x) : 2x.

Find formulae for the composite functions gof and
fog. Do we have gof : fog ? 2
(b) By constructing Truth Tables, show that the two

propositions
( p n q )v ( p n r )
and
(p v (q n i))
are negation of each other. (Read F : -p)
(c) Prove by induction that for n
n(n+1)(n+2)
1 . 2 + 2 . 3 + . . .+ n ( n + 1 ) :
3
3. (a) of all the terms

What is the sum of the coefficient"s
in the expansionof (x + y + z)7 ?
MCS-013
(b) Define Generalised Pigeon Hole Principle. Show
that in a group of 35 PeoPle' one can always find
6 people who were home on the same day of the
week.
(c) How many numbers from 0 to 999 are not

divisible by either 5 or 7 ?
'
4. (a) Out of 200 students, 50 of them take the course

Discrete Mathematics, 140 of them take the course
Economics, and 24 of them take both the courses.
Use Venn diagram to find the number of students
who are not in either one of these courses. 2
(b) An urn contains ls.balls, 8 of which are red and

7 are blue. In how rnany ways can (i) 5 balls be
chosen so that all 5 are red, and (ii) 7 balls be
chosen so that at least 5 are red ?
(c) L e t A : { a ,b , c , d } , B - { 1 , 2 , 3 } , a n d
R = {(a, 2), (b, 1), (c, 2), (d, 3)}. Show that R is a
function from A to B. Is R one-one ? Is R onto ?
(d) Suppose 25 people have exactly the same
briefcases,which they leave at a counter. The

cases are handed back to the people randomlY.
What is the probabilitYthat no one gets the right
case ?
MCS-013 P . TO
5. (a) Find the Booleanexpressionin DNF for the function
defined in tabular form below :
*1 *2 *3 f(x' xz, *3)
1 0 1 0
0 1 0 1
1 1 0 0
0 0 1 1
0 1 1 0
1 0 0 1
0 0 0 0
1 1 1 1
(b) Simplify the following Boolean expression :

( f r n x 2 n x r )v ( x r n x r )
(c) Find the Boolean expression represented by the

following circuit : 4
x1
x2
x1
x3
h
x3
MCS-013 11 , 0 0 0
MCA (Revised)
T€rtn-End Examination
December, 2006
MCS-014: SYSTEMSANALYSISAND
D E S IGN

(Weightase75%)
Nofe ' Quesfion number 1 fs compulsory. Attempt any

three quesfionsfrom the rest,
1. (a) Explain the phasesof SDLC in detail. Also explain

the role of feasibilityanalysiswith an example. 10
(b) PrepareERD for a library managementsystem.Also

explain the details related to keys, f,relds,
relationships etc. 10
(c) List and explainthe basicskillsof a systemanalyst. 5
(d) Explain all types of couplingand cohesionin detail.

Which type of couplingand cohesionis best ? Justify
your answer. 10
(e) Build a context and first level DFD for a student

registrationsystemof a college.
MCS]014 P.T.O.
2. (a) Give various types of documentation required in
systemdevelopment.Explain in detail with the help
of suitableexamples. I
(b) Explain the following terms with an example : 4x3:72

(i) System Testing
(ii) StructureChart
(iii) InheritanceDiagram
3. (a) Explain the following with the help of an example :

3x2:6
(i) Primary key
(ii) Secondarykey
(iii) Referentialintegrity
(b) Prepare a database schema for a hospital
managementsystemand elaborateits components. 10
(c) Explain the role of a DBA 4
4. (a) List and explainvariouscomponentsof a CASE tool.

Draw suitablediagram to elaborateyour answer. 6
(b) List any four basic requirementsfor designing a

project report 2
(c) Explain the use and function of the following with

suitablediagramfor each : 4x3:72
(i) TPS
(ii) Expert system
(iii) DSS
MCS-014
5. (a) Explain any four types of testing techniques with an
example of each 10
(b) Explain the differences between reverse and forward

engineering. Give a suitable example for each'
(c) Explain how the infere nce engine provides the

reasoning capability to the expert system.
MCS-014 11 , 0 0 0
MCA (Revised)
December, 2006
MCS-015: COMMUNICATIONSKILLS
Nofe 3 Ans wer oll questions.
L. Read the following passage and answer the questions given

after it :
Reports
A report is a factual piece of writing based on
evidence. The evidence may have been gathered at first

hand by the writer, which is sometimes but not always
the case with newspaper reports. Often it is the result of
research into data provided by someone else. The data in
a shipping report comes from the weather stations where

recording instruments are located. In the case of a
campaigning report, the data will have come from a

variety of sources : interviews, press cuttings, and
information taken from research done by academics and
others.
MCS-015 P"T.O"
Information that can be checked
The information in a report has to be reliable. Newspapers

claim to publish true information and good reporters can
normally vouch for their stories. They r-nay refuse to reveal
their sources of information, but these are good and
reliable. Official reports normally contain the evidence upon
which they are based or provide detailed references to their
sources of information.
Presentation and StYle
The whole purpose of a report is to communicate

information and ideas effectively, so presentation is very
important. Different types of reports have different
conventions. The shipping report presents just the bald data
in a form and order which is easy to understand and
interpret. The most important information in a newspaper
report is contained in the first two or three paragraphs so
that busy readers may get the gist of the report without
having to read thousands of words. Business reports often
'executive summary' for the same reason.
begin with an
Audience
Reports are often prepared for a specialist audience. It

allows the writer to assume that the audience understand
a certain amount of information and are familiar with the
style of presentation.
On the other hand, the audience are to a greater or lesser

degree'experts' and may be critical of the writing or may
feelthat it is not upto the expected standard. So there dffQ
tvlcs-O15
advantages and disadvantages for the writer addressing a
specialist audience
John Seely
(i) Mention two ways of gathering data that may go into
a report 2
(ii) What is that one condition that governs all reports ?
whv ? 2
(iii) How does the report writer show consideration for
the readeris time ? 2
(iv) Given below are two statements. Say whether they
are true or false.
(a) An executive summary contains the gist of the

report and occurs in the beginning of the
report
(b) Official reports rnay refuse to revealtheir source
for their data.
(v) Who comprises a specialist audience ? Why is it

difficult to write for a specialist audience ? 2
2- Choose the word or phrase that best completes each

sentence from the options given below :
(i) The two companies are planning to merge. They

shall begin a round of tomorrow.
(a) arguments
(b) notifications
(c) negotiations
(d) accusations
MCS.O15 P.T.O.
(ii) You should try to be more in the
meetings or they will pass their own agenda.
(a) aggressive
(b) assertive
(c) ambiguous
(d) anomalous
(iii) An emergency meeting was inevitable. So a
was quickly circulated in all the

departments.
(a) order
'
(b) memoir
(c) requisition
(d) memo
(iv) The Chairperson tried to the different

ideas and viewpoints that emerged during the
discussion.
(a) synth eslze
(b) sum up
(c) synchronlze
(d) symbolize
MCS-015
(v) The last batch of defective goods caused a big blow
to the company's
(a) credulity
(b) credibility
(c) credentials
(d) creativity
3. Here is an excerpt from a discussiorbCornpletethe part of

the interviewerin tfre followingdialogue. 2x5:70
Interviewer : Good Morning, Ms. Seth.
Ms. Seth : Good Morning,Sir.
Interviewer :
Ms. Seth : I am a marketing person and have been

always thinking of improving the visibility of
my company. I have prepared many
presentations on the same. Now I hope to
have a team to lead
Intervi ewer :
Ms. Seth : I feel the co-curricular and extra-curricular

activitiesat school and college helped me to
develop confid ence and improve my
decision-making capability.
Intervi ewer : You have mentioned co-curricular activities.
MCS-015 P.T,O.
Ms. Seth : Organizing exhibitions, compering the
cultural programmes and taking part in
poster campaigns.
Intervi ewer : Good. You wish to have a team to lead,

right ?
Ms. Seth : A team is like a machine in which all parts

are interdependent on each other. A good
team is dernocratic and is based on trust and
mutual respect.
Intervi ewer :
Ms. Seth : I can help your organisation to build a team

to enhance its visibility through personal
contacts and the media.
Intervi ewer : Thank gou, Ms. Seth.
4. Rewrite each.sentence in the PassiveVoice.
(i) Your resum€ pleases me.
(ii) We enclose the quotation along with our letter.
(iii) Everyone considered this company to be trustworthy.
(iv) Anyone can follow the manual easily.
(v) Getting modern equipment can increase production.
MCS-015
5 . The Annual Day of your organisation is at hand
(16 November).You need to preparea programmefor the
celebrations.Imagine that a meeting has been held to
discussthe matter on the basisof the Agendagiven below.
Preparethe minutesof the meetingbasedon the Agenda. 20
AGENDA
1. Programme for Celebrations (Welcome Speech,
Report, Cultural items, time and duration etc.)
2. Venue of the Function (Booking of the hall etc.)
3. Chief Guest (lnvitation)
4. Preparation of Cultural items
5. . Reception Comm ittee
6. Hall, decoration and seating arrangements
7. Refreshments
8. Transport incharge
9. Store incharge
10. Rapporteur, Press Release
MCS-015 11 , 0 0 0
a
;l
q
MCA (Revised)
December, 2006
MCS-021 : DATA AND FILE STRUCTURES
Time : 3 hours Maximum Mqrks : 700

(Weishtage 750/o)
qnY
Note : Question number 1 is compulsory. AttemPt
. three questions f rom the rest. All algorithms
'C
should be written nearer to language.
1, (a) Define Abstract Data Type. Give any four examples

of Abstract Data Type. Also, write the
implementationof stack using link list. 10
(b) Define time complexity and space complexity of an
algorithm. Calculatethe complexity of the following
'O' notation : 10
code by using Big
1. print Multiplication Table (int max) {
2. for (int i:1; i(:Ixdx; i++) {
3. for (int j=1; i(=max; j++)
4. cout<<(ioj)<<"
";
5. cout<<endl;) )
Also, calculatethe overall complexity of the given
code
MCS-021 P.T.O.
(c) What "is a Dequeue ? Write a program to insert
and delete the node in a dequeue. 10
(d) Differentiate among @ Notation (Tisht Notation),
Big o notation (Upper Bound) and o Notation
(Lower Bound). AIso, show that 10
f(n) + g(n) = Max(O(f(n)),O(g(n)))
2. (a) Define a sparse matrix and its 3-tuple

representation. Also write an algorithm that
accepts 5 x 4 sparsematrix and outputs its 3-tuple
representation. rc
(b) Construct the binary tree using the following

pre-order and in-order sequenC€S: 10
Pre-order: 35, 31, 15; 7 , 3 3 , 3 2 , 4 3 , 3 g , 4 0 ,4 9
In-order: 7, 15, 31, 32,33, 35, 3g, 40, 43,49
3. (a) What is a binary tree ? Write algorithm for its

implementation. Also . write an algorithm for post
order traversal. 10
(b) Differentiate between the Kruskal's and prirn's
algorithm based on their principle,- operation and
running time. Also, write any two applications of
minimum cost spanning tree 10
MCS-021
4. (a) If a matrix A(i, j) is representedin a linear array B(k),
suchthat, rc
B(0)= A(0,0), B(1)= A(0,1) ... B(,)= A(2,0),
in a (10 x 15) matrix, compute the addressof B(k)
for the following vatuesof A(i, j) : A(3, S), A(7, 3),
where addressof B(0) is 14g.
(b) Write an algorithm for All-pair shortest path

algorithm. rc
5. (a) Sort the following numbersusing Z-waymerge sort :

g, 4!, g0,2,55, 70,39
Write all the steps involvedin sorting. 10

(b) Write an algorithmfor splay tree operations. 10
MCS-021 7,000
MCA (Revised)
Term-End F,rramination
December, 2006
MCS -022 : OPERATINGSYSTEM

CONCEPTSAND NETWORKING
MANAGEMENT
Time : 3 hours MaximLtmMsrks : 704
Note r Qu estion number 1 is compulsory. Answer qny

l. (a) A computer has a monitor that consumes60 W of '

power. The CPU requires 100 W. What should be
the minimum power rating of a UPS used for
supplyingpower to this computer ? 5
(b) What is the basic difference between Network

operating system and Distributed operating system ? 5
(c) I carry a CD containing600 MB (megabytes)of data
from my houseto yours. If it takesme 30 minutesto
drive down to your house, what is the data
transmissionrate ? 5
(d) What are the different states of Linux Operating

System ? 5
MCS-022 1 P.T.O.
(e) Write a shell script to accept upto 5 numbers as
argumentsand print out their arithmetic mean. 5
(f) List some of the duties of a systemadministrator. 5
(g) How does a domain differ from a workgroup ? 5
(h) What are the goals of Computer Security ? 5
2. (a) What is Computer-Securityclassification? Explain. 8

(b) Describe the strategy for hardening your Windows
2000 operatingsystem. I
(c) What is a computer virus ? Describe the different
types of viruses. 4
3. (a) Distinguish between virtual and physical addresses.

List the various data structuresrequired for address
mapping from virtual to physical addresses and
describethe process. 10
(b) Draw the logical netwo-rklayout of a Windows 2000
\ctive Directory and describeits components, 10
4. (a) Name various authenticationsavailablein Windows

operating systemand describeany one of them. 5
(b) E*pand the following :
(i) RADTUS
(ii) NAT
(iii) rcs
(iV) RRAS
(v) EFS
MCS-022
(c) ' DiscussIPSec implementationin the Windows 2000
operatingsystem.
(d) What are input and output restrictions,filtering and
pipelining of instructionsin Linux ?
5. Describethe following : 20
(i) Policy Inheritance
(ii) Fault Tolerant System
(iii) Kerberos
(iv) Confidentialityand Integrity
MCS-022 7,000
MCA (Revised)
Decembern 2006
MCS -O2g: DATABASEMANAGEMENT

SYSTEMS
(Weightage 7}o/o)
Note : Question number 1 is compulsory. Attempt
any
three quesffonsfrom the rest.
l. (a) Give details of three level architecture of DBMS.

Details should contain all the software components
used at diff erent levels.
rc
(b) Draw an ER-Diagramfor an educationalinstitution

affiliated to some universitywhich offer$ coursesin
management,law and engineering.Each department
has a Head of the Departrhent,faculty (permanent,
temporary, adhoc, contract). Limited number of
students are taken for each course. Make suitable
assumptions,if any. Fxplain alt the relationshipsin
your ER-diagram with respect to relationship
cardinality and participation constraints. Also
transform it to relationaldatabase.
10
MCS-023
P.T.O.
(c) Consider the relation PERSON :
Person_id Name Age Address
2 Sharad 33 Pocket 2, Green Park
1 Sanjay 35 B-4, Modi Nagar
3 Vibhu 38 C-2, New Delhi
Do the following operations ' 5

(i) Write the SELECT operation to display details
of personshaving age lessthan or equal to 30'
(ii) Write the PROJECT operation to display only
the names of Persons.
(d) Consider following relational database schema
Supplier (S-no., S-name, S-citY)
Parts (P-no., P-name, P-color, P-weight)
Projects(Proj-no., Proj-name, Proj-status,Proj-city)
Sub-parts-proj(S-no., P-no., Proj-no', City)
Express following queries using SQL and relational
algebra: 3x5:7 5
(i) Find parts suppliedby supplier number 51 in
Delhi.
(ii) Find the name of parts used in project number
proj.1
(iii) Find the name of projectsexecutedin Delhi.
(iy) Find colour and weight of parts supplied by
supplier number 52.
(v) Find name and number of part whose colour is
'Red'
MCS.O23
2. (a) What is functional dependency? Removal of which
functionaldependencyleadsto which normal form ?
Discuss with example. Briefly discuss lossless
decomposition and dependency preserving
decomposition
. 10
(b) Prove the statement "Every relation which is in

BCNF is in 3NF but converse is not true".
(c) Describe the architecturefor a 3-tier client-server

computing. Also mention the advantages of
client-servercomputing
3. (a) What do you mean by transaction in a database ?

What are the properties of transactions ? Explain.
(b) What are the techniques used to handle concurrent

transactions in a database ? Discuss in detail any two
of such techniques. 10
(c) Describe the term deadlock in concurrent
environment. How do we detect deadlock ? Briefly
discuss protocol for deadlock prevention.
4. (a) What is database recoveng? What are the teehniques

used for database recovery ? Discuss any two
techniques in detail. 10
(b) Write short notes on Distributed database

managementsystem. Give two advantagesand two
disadvantagesof DistributedDBMS.
MCS-023 P.T.O.
(c) Differentiatebetween : 2|xZ:S
(i) File basedsystem'andDBMS

(ii) 2-phase locking and Z-phasecommit
5. Write short notes on the following : 5x4:20

(a) Seriali zablescheduleand its uses
(b) Integrity constraintsand its types
(c) Data fragmentation
(d) Shadow paging
(e) Locks and its types
MCS-023 7,000
MCA (Revised)
December, 2006
MCS -024: OBJECTORIENTED

TECHNOLOGIES AND JAVA
PROGRAMMING
Time : 3 hours Maximum Msrks : 700

Note : Quesfion number 1 is compulsory. Attempt qny
three questionsfrom the re:st.
1- (a) What is the Java Virtual Machine ? How does it

make Java machine independent?
(b) What is Garbage Collection ? Can the programmer
explicitly invoke the garbage collector ? List the
method with the help of an example which invokes
the garbagecollector.
(c)Explainthefollowingkeywordswithexamples:
(i) this
(ii) abstract
(iiil final
(iv) super
MCS-024 P T.O.
(d) What is object serialization? Write a Java program
that writes the state of an object to a file which
includes user name and password. Also ensure that
the passwordis not stored in the file.
(e) What is an applet ? What are its life cycle methods ?
(0 What is an interface ? What is the nature of methods

and variables defined in an interface ? How is an
interface different from an abstract class?
(g) What is JDBC ? List the classes in Java'SQL

package which are used to execute any SQL Quer9,
with an explanation.
2. (a) Explain Event Delegation Model with Event Classes

and Listener Interfacescommonly used.
(b) Create a Java Applet with two text boxes and a

button. Write a program so that on entering two
numbers in the text box and'clicking of a button it
displaysthe greater of the two numbers.
(c) What is a l-ayout Manager ? Createa frame that has

four buttons on all four sides,i.e. north, east, south
and west.
3. (a) What are a class and object ? How is an object

related to and different from a class?
(b) write a program that displaysall the prime numbers

between 2 and 100.
MCS-024
(c) Explain the concept of polymorphism. Create an
Exception class that is thrown whenever the string
entered is not a palindrome. Write a program that
accepts the command line argument and uses the
custom defined exception.
4. (a) What is a thread ? Explain the life cycle of a thread. 4
(b) Create an applet with a rectangle that is gradually

'the sleep method of
colored after a second, using
thread. 6
(c) What will be the result of attempting to compile and

run the following code | 4
(i) public classlffbst{
public static void main (string args I D{
if (true)
if (false)
system..out.println( " a " );
else
, system.out.println (" b " );
l
l
(ii) classMyClass {
public static void main (string args I D{
boolean b:false;
int i:1 ;
dot
i++;
b:!b;
l while (b);
system.out.println(i);
l
l
MCS-024 3 P.T.O.
(d) Explain the hierarchy of stream classesin the IO
package. What is the difference between Binary
streams and Text streams?
5. (a) What is a Servlet ? Create a servlet that accepts the

usernamefromtheclientandprints..Hello''
followed by the actual user narne to the client. 8
(b) Write short notes on : 6
(i). uRL
(ii) Proxy Seruer
(iii) Internet Address
(c) Explain RMI Architecturein detail. 6
MCS-024 7,000
MCA (Revised)
December,2006
MCS-031 : DESIGNAND ANALYSIS OF

ALGORITHMS
Note : Que.sfionnumber 1 is compulsory. Attempt any

three quesfions from the rest. All algorithms
should be written nearer to C/C++ language.
1. (a) (i) Give an array of 8 elementswhich is the best

case for Insertion Sort.
(ii) Give an affay of 8 elementswhich is the worst
case for InsertionSort.
fhe best/worst case(s)should be according to the
number of insertions into the array that require a
(b) Arrange the following in order of best to worst

efflciency :
o D
o(r,2 log n), o(r,2), o(r,3), o(r,2 log '.6-)
MCS-031 P.T.O.
(c) Give an analysis of worst case running tirne
of
quicksort. When does it occur ? How
can we
improve the worst caseperformance of quicksort
? 10
(d) Discusshow depth first search can be used to find
cyclesin an undirectedgraph.
(e) what do we understandby the "optimal substructure

property'' in a dynamic programming problem
?
(0 Describe "semidecidability"of a Turing Machine.
(g) How do we establish that a problem is

NP-Complete?
2. (a) write a recursivealgorithm to reversea singly linked

list.
(b) Prove that the lower bound for the number

of
comparisonsin any comparison sort (e.g. Heapsort
or QuickSort or MergeSort)is A (n n).
b
[where lg means 1eg2I 10
(c) what is the diflerence between a pure recursive
solution and a dynamic prograrnming solution to
a
problem ?
3- (a) what is the importance of generatingalpha or beta

value for a node alpha-beta procedure ? which
player among MIN and MAX uses alpha
value and
which player usesbeta value, and, how ?
MCS-031
(b) Describe the sequence of steps involved in the
designing of a greedy algorithm.
(c) Write'the context iree grammar for a non-null even

palindrome.
4. (a) (i) Construct a non-deterministicFinite Automata

(NDFA) representingthe language: s
(ab)- (ba)*+ aan
(ii) Construct a Finite Automata for the language : S
an (ab + ba) bn
(b) Design a Turing machine that shifts a string on the
tape, one place to the right, i.e., it transforms#w#
to **wwfwhere 'w'
is a string with no blanks,
# represents a blank square and the underlined
symbol repre.sents
the current position of the head. I
(c) Define "Pumping Lemma" for Context Free
Grammars. 2
5. (a) Find whether the following two boolean expressions

are satisfiableor not :
(t P n (lP v a v B
(ii) a v (lq n P n (a v p))
(b) Among i'best first search" and "depth first search",
which technique is used in inorder traversal of a
Binary Tree and how ?
MCS-031 P.T.O.
(c) Show how Breadth First Search algorithm works on
the graph below. Assume that the vertices are
consid ered in an alphabetical order and that the
graph is represented using adjacency list
representation in which each adjacency list is ordered
alphabetically. Show that the queue operations for
each step and the distance calculated for each vertex
'A'. 10
startfrom the vertex
MCS-031 6,000
MCA (Revised)
December, 2006
MCS-032 : OBJECTORIENTEDANALYSIS
A N D D E S IGN
Nofe : Quesfion number 1 is compulsory. Attempt any
1. (a) What is object oriented modelling ? Give detailed

description of the processes involved in object
, oriented modelling. 3+7:70
(b) How is object oriented diagram different from ER
diagram ? 5
(c) Differentiate between the terms Generalization and
Specialization. Explain with an example the close
association between Generalization and Inheritance
3+5:8
(d) Give brief description of characteristicsof object
oriented modelling. 5
(e) What are integrity constraints? Briefly discussthe
types of integrityconstraints. 2+3-5
(f) What is UML ? What are the methodologies
associatedwith UML ? Discussany five features of
UML. 2+2+3:7
MCS-032 P.T.O.
2. (a) Draw classdiagram for the situation given below. 10
A directory may contain many other directoriesan,C

may optionally be contained in other directory.
Each directory has exactly one user who is the
owner and many users are authorized to use that
directory. Respective classes must have their
concernedattributesand operations.Make necessary
assumptions,if any.
(b) What is association ? Differentiate between 1-way
and Z-wayassociationwith example for each. 1+4:5
(c) Comp are Object Oriented analysis for software

devetopmentwith Structuredanalysis. 5
3. (a) How does UML help in software development ?

What softwares are availablein the market to work
with UML ? 3+2:5
(b) Write a short note on Structural and Behavioural

diagrams.What arethe constituentdiagramsof these
two broad categories ? Discuss in brief, any two
constituentdiagramsof each type. 4+2+4:70
(c) How do we implement the concept of associationi1
C+ +/Java ? 5
4. (a) Give three differences ,betwe€rr' Object model,

Dynamic model and Functionalmodel. Out of these
models, which model is most important and why ?
7+3:70
(b) Draw and explain State diagram of gear transmission
system of a car. 5
MCS-032
1
(c) Differentiate (any two\ : 2; x2:5
(i) Aggregation and Generalization
(ii) Aggregation and Association
(iii) Good design and Bad design
5. (a) What is use case diagram ? Explain different

componentsof use casediagram. 2+2:4
(b) Write short notes on any four : 4x4:76

(i) DFD and its features
(ii) Multiple Inheritance
(iii) Multiplicity and its type
(iv) 4+I view of softwarearchitecture
(v) Mapping object classesand associationto tables
MCS-032 6,000
MCA (Revised)
December, 2006
MCS-033 : ADVANCED DISCRETE

MATHEMATIGS
Note 3 Question no, 1 is compulsory. Attempt any

l. (a) Define the following.Also give an example.

(i) Bipartite graph
(ii) Complete graph
(iii) Subgraph
(iv) Multigraph
(b) For the graph G given below, compute the number

of edgesin G and draw the closureof Graph G.
C
Graph G
MCS-033 1 P.T.O.
(c) Apply Euler's formula for planar graph and show
that the following graph is planar.
C D
(d) Solve dn : Ddn_1for n 3
(e) Solve ?r, + San_, + 6un_r: 0 for n

a,^,:landar:2.
U I
4
(f) Define the following in case of recurr ence relation : 3

I
(i) Degree
(ii) Order
(iii) Non homogeneous,/homogeneous
2. (a) Check the graphs Gl and Gzfor isomorphism.
G1
G2
(b) Solve a - a + dr_Z for r given a l : 1 a n d

r r-r
a z : 1.
MCS-033
(c) Draw Ku graph. Differentiate between walk and cycle
with the help of an example. 3
3 . (a) Find the chrornatic number of the following graph : 3
(b) Solve.: : 5 u3_, for n 2

(c) Drawthe diagramof Konigsberg's7 bridgesproblem
and explainthe solutionproposed
by Eulerfor it.
4. (a) Solve d, : 3a
r_1 + 1 for r > 1 usinggenerating
function. Given u o = 1 ' 4
(b) Find particular solutionof
a
r
4 a
r- 1
+ ur-r: (r + r) 2' 4
(c) Draw any four spanningtreesof following graph. 2

v1 v2
MCS-033 P.T.O.
'
5. (a) Find the generatingfunction for the numeric function
dn : 2n*3' n
(b) Does the graph G shown below possess a

Hamiltonian circuit ? Also enlist all the conditions for
a graph to possess a Hamiltonian circuit.
A B
E
C Graph G D
(c) Describe merge-sort as the divide and conquer

problem.
MCS-033 , 4 6,000
' i t : , , ' ) ' .: i , ,
. r , , i ' . ,
. . , : ' , . , 1 , '
,MCA,(Revised), , , ,,
Terrn-End
I IEI ltt-LllLl Examination
lzra'Cllltll
. : , , ' ' . ; . 1 - r - . . : , ' . . r .

Decernber, 2006
MCS-034 r SOFTWAREENGINEERING

, , . r . , .
' . , i
. .
I , i , , . ' i: l: ,, r: r .':'.:', , i, ' .. , !,..;
Note : Quesfion number,l is comPulsory. A,tte,mp,tqny

three questions from the rest,.
'?
1. (a) What is SRS List and
SRS. Develop an SRS
System, ', , , ,. : u
(b) What do you mean by managernent of risk
Describea risk table with u*u*plu.'
'Webmaster:;
in
(c) Mention any five reiponsibilitiesof a
a Web application team. , Also explai'n' the
characteristicsof any,thrge,spftware,,tools/packageg
u s g d f o r W g b d g v g l o p m e n t i , , r , , :, i , 11
; , , ..,,i . . ., i , , , ,,::
(d) Explain the Spiral model,for softwatre'"'d€v€lopment,

Mention its advantagesand disadvantages.Also
compare this with the Prototyping model. 10
Mcs-034
2. (a) What is a DFD ? Explain the rules for designing
DFD. What are the various tools used for designirlg:'
it ? How does it differ fiom'an ERD ? 18
(b) 'Data Dictionary' ? Explain
What is the,,purpose of
the symbolsused therein with an example. 8
3'(a)
;ffi#Hffi,"1;',iJil"[J",:ffi;ff
disagree ? Justify your answer. 6
(b) How do version control systems ensure that two
software developersdo not attempt the same change
(c) Discussthe three levels of testing. Also explain the

term CyclomaticC*nplexity. I
4. (a) List at least five featureseach of CDMA and J2ME. 70
(b) , ,What is RequirementsGathering ? Explain any four

10
5. Write short notes on the,following 20
(a) Quality Assurance

(b),i''r'Configurbtion
Management
(c) Project Management
(d) CouplingVS.'Cohesion
MCS-034 6,000
MCA (Revised)
December, 2006
MCS-035 : ACCOUNTINGAND FINANCIAL

MANAGEMENT
Nofe : Qute.stionnumber t is compulsory and carries

40 msrks. Attempt sny three que:stionsfrom the
rest, which carrY20 marks each.
l. (a) From the following Trial Balance prepare Trading

and Profit and Loss Account for the year ended
31tt'December2005 and BalanceSheet as on that
date :
Dr. Cr.
Particulars (Rs.) (Rs.)
Drawings 10,000
S t o c ko n 0 1 . 0 1 . 0 5 +6,000
Purchaseand PurchaseReturn 1,50,200
Cash in hand 3,460
Bank Balance 22,600
MCS-035 P.T.O.
Particulars Dr. Cr.
(Rs,) (Rs.)
Freehold Premises 38,600
Trade expenses 840
Printing stationery and advertising L,640
Professional charges 280
Commission Received - 3,300
Investment as on 1tt January @ IO% 4,000
Interest on above 200
Sundry Debtors and Creditors 36,000 29,000
Wages 25,000 -
Salaries L4,000
Capital 1,14,000
Income tax 1,600
Discount allowed and received 6,300 4,60A
Sales return and Sales 550 2,09,950
Bills Receivablesand Payables 3,200 10,000
Office Furniture 3,050
Rent, Rates & Insurance 4,000
Bad Debt Provision 670
Total 3,77,320 3 , 7 L , 3 2 0
MCS-035
Adjustments ;
(i) WagesoutstandingRs. 5,000.
(ii) Charge depreciationon freehold premises @
5% and on office furniture @ I0o/o.
(iii) Insurangeto the extent of Rs. 2OOrelated to
the year 2006.
(iv) Stock on 31. L2.2005 is valuedat
Rs. 5,20,000
(v) Charge interest on capital @ 5o/o and on
drawingsRs. 300.
(vi) Bad debts for the year Rs. 1,000 (not
" recorded).
(vii) Provide for doubtful debts @ 5o/o on sundry
debtors.
(viii) Make provision for discount on debtors and
resewe for discount on creditors @ 2o/o
(b) The comparativestatementsof income and financial
position of KailashEnterprisesLtd. are given below :
2005 2006
Particulars
Rs. Rs.
Sales (Net) 1 , 5 0 , 0 0 0 r,84,000
Less : Cost of Sales 1 , 0 0 , 0 0 0 1,39,000
50,000 46,000
Less : . Operating Expenses(lncluding
44,000 42,000
Rs. 6,000 p.a. for depreciation)
Net Profit 6,000 4,000
MCS-035 P.T.O
2005 2006
Particulars
Rs. Rs.
Assets
Cash in hand 12,000 L4,000
Debtors 60,000 36,000
Stock at cost 24,000 18,000
Fixed Assets (net) 7,Q2,000 1,06,000
Total 1 , 9 8 , 0 0 0 7 , 74 , 0 0 0
Liabilities
Creditors 38,000 20,000
Debentures 40,000 30,000
Share Capital 1,00,000 1,16,000
Reserves& Surpluses 20.000 8,000
1 , 9 8 , 0 0 0 r , 74 , 0 0 0
Compute the following ratios r
(i) Current ratio for two years.
ason
(ii)'iJ";H,o;'J;'J:J#"rffi';f"'u
(iii) Average collectionperiod for two years (all sales
are creditsales).
(iv) Debt Equity Ratio for two years.
2. Explain the following .accountingconcepts giving suitable
examples:
(a) Accrual
(b) Conservatism
(c) Materiality
(d) Consistency
MCS-035 4
3. Explain the concepts of working capital cycle and cash
conversion cycle. Why are these concepts important in
working capital management?
4. Write short notes on the following :

(a) Baumol'smodel
(b) Investmentopportunities for surplus cash
(c) Economic Order Quantity
(d) Factoring
5. What are the important dimensionsof a firm's credit

policy ?
6. "Ultimate objective of financial management should be

maximisation of wealth." Discuss this statement and
managerin a firm.
MCS-035 6,000
MCA (Revised)
' Term-End Examination
, December, hOOG
MCS-041 : OPERATINGSYSTEMS

(Weishtase75%)
sny
Note : Question number 1 is compulsory. AttemPt
three questionsfrom the rest,
l. (a) Draw the Gantt chart for the First Come First Serve
(FCFS) scheduling policy and calculate the
turnaround time, average waiting time, throughput
and processor utilization for the following set of
time shown
tDrocessesthat arrive at a giuen arriual
in the table 10
Processing time
Process Arrival time (Millisecs)
Pr 0 2
P2 2 2
P3 3 1
P4 5 3
PD- 6 4
P . TO
MCS-041
(b),?:'TilllJ:
:Ti::
"rLi:1,*''J[,ffT,:,
about the hardware support for paging. 10
(c) the designissuesinvorvedin
:ff;:."#*r:" 10
:(d) Define the Deadlock state. How do we prevent a
deadlockusing the Havender'sAlgorithm ? Explain. 1 0
2. (a) "The generations of the operating systems are

characterisedby hardware component technology,
-of
software development and mode of delivery
computer services.
" Explain all tnte generations of
the operating systems w.r.t. the above said
parameters. 10
(b) What is the role of the operatingsystemin providing
the security and protection ? Explain any t*;
multilevelmodels of security. 10
3. (a) Explain the structure of UNIX operating system.

Also, discussthe CPU schedulingin UNIX operating
system. 1U
(b) Write and explain the Dekker's solution for Mutual
Exclusion. 10
4. (a) Explain the concept of Thrashing.what are the two

availabletechniquesto prevent thrashing ? Explain
any one of them. 10
(b) Explain the Non-continuous(lndexingand chaining)
disk space managernentmethods. L0
MCS-041
5. (a) Write and explain the Dining PhilosophersProblem.
Also, provide the solution for the problem using
semaphores. 10
(b) Explain the concepts of Processesand Threads in
WINDOWS 2000 Operatingsystem. 10
MCS-041 6,000
MCA (Revised)
December,2006
MCS ,:042: DATA COMMUNICATIONAND

COMPUTERNETWORKS
any
Nofe , Qu estion number 7 is compulsory. Attempt
three questionsfrom the rest'
1. (i) Why can CSMA /CD not be used in wireless

networks ? How does the problem of hidden and
exposed station get resolved ? Explain the above
with the help of diagrams.can there be any collision
70
further ?
(ii)
group 1
Draw a spanning tree, a multicast ttee for
3
and for group 2 of the abovenetwork.
P.T.O.
MCS-042
(iii) Draw a three stageswitch. There are 18 inputs and
20 outputs. Stage t has three switches,stage z has
-two switches and stage 3 has four switches. How
many cross points are needed ? Compare it with a
systemusing just one crossbarswitch s
(iv) Consider the following network with the indicated
link cost. Use Dijkstra's shortest-pathalgorithm to
compute the shortestpaths from A to C and F. rc
(v) Suppose pure Aloha protocol is used to share a

56 kbps satellitechannel. Assume that packets are
1000 bits long. Find the maximumthroughputof the
systemin packets,/second.
(vi) Using the RSA public key cryptosystem,if p :
5,
q : 13, list five legal valuesfor d.
(i) state the concept of channel, capacity. state the

Nyquist and shannon theorems and their uses with
appropriateexamples. rc
MCS-042
(ii) What is count to infinity problem ? Explain your
answer with the help of an example.
(iii) Witn reference to the transport layer, outline the

connection set-up operation of 3-way handshaking
through a diagram. What are its advantages ? s
3. (i) Explain the operation of OSPF with the help of a

diagram showing appropriate routers. 10
(ii) What is the Silly window syndrome ? What is the
Clark's solution to overcomeit ? s
(iii) Obtain an expression for averag€ number of the

unsuccessfultransmissionattempts/frame for slotted
ALOHA.
4. (i) What are the problems with the following

algorithm ? Explain with the hrelpof examples. 10
o DoubleDES
o Diffie - Hellman kny exchangealgorithm
(ii) Sketch the Manchester, Differential Manchester,

Binary encoding,RZ and NRZ-I for the bit stream : 5
11111000101010
(iii) Differentiate between upward and downward

nultiplexingwith the help of a diagram. s
MCS-042 P.T.O.
5. (i) Explain with the help of a diagram operation of the
flow control mechanism in TCP. 10
(ii) What are the reasons for a minimum length frame in

IEEE802.3?
(iii) What arethe two conditions for the polynomials used

by CRC generators ? Explain.
MCS-042 6,000
MCA (Revised)
December, 20A6
MCS-043 : ADVANCED DATABASE DESIGN
Time : 3 hours Max'mum Mqrks : 700
Note r Question number I is compulsory, Answer any

three questionsfrom the rest,
- t
1..(i)Definemulti-valueddependencies.Which
multi-valued dependencies (MVDs) hold for the
following relation ? Explain. 5
P_No Colour Size
P1 Red Large
P1 Green Large
P1 Red Medium
P1 Green Medium
P1 Red Small
P1 Green Small
P2 Black Large
P2 Black Small
In this relation each product comes in a range of
colours and sizes.
MCS-043 P.T.O.
(ii) How is the checkpoint information used in the
recovery operation following a system crash ? 5
(iii) Show the cost calculation for a simple Hash-join

operation. Make the necessaryassumptions,if any. 6
M A company database needs to store information

about employees, departments and children of
employees. Employees work in departments, each
department is managed by an employee, we are not
interested in information about a child once the
parent leaves the company. Draw an E-R diagram
that capturesthis information. 5
(v) How is UML related to E-R diagram ? 4
- (vi) In timestamp-basedconcurrencycontrol, transactions

are assigneda timestamp at startup; how is it used to
ensure serializability? How does the Thomas Write
Rule improve concurrency? 6
(vii) What is. XML and how does XML compare to

HTML ? 4
(viiil What is an integrity constraint ? How are integrity

constraintssupported by Oracle ? Briefly describe. 5
? 2. (i) Briefly describe the architecture of distributed

databaseswith the help of a diagram. 10
(ii) How does the architectureof DDBMS differ from

that of centralizedDBMS ?
MCS-043
(iii) Identify the functional dependencies which hold for
the following relation :
PNo Factory Warehouse
P1 F1 WH1
P1 F2 WH1
P2 F2 WH1
P3 F2 WH2
P4 F2 WH2
The above relation indicates where each product is
#"l:ffiH:?:;1.
;:1:, illl:;
:::i"ff::::
only be stored at one warehouse.
3. (i) Make a comparison between OODBMS and object

relational database. 10
(ii) Describe an application scenario (in brief) for which
' you would choose an ORDBMS and explain why. 6
(iii) Consider the following relations :
Society (S-id, S-name, S-cause, S date, S-address)
Member (M-id, M-name, M-phone, M-address)
Event (E-id, E-desc, S-id, M-id, E-date)
Write the relational algebraic queries for the

following : 4
(a) List the event details by the societies for the

cause of "AIDS".
MCS-043 P . TO .
(b) Show the detailsof all the memberswho have
been involved in any event organized by the
societywhose name is "XYZ".
4. (i) What is clustering in data mining and how is it

different from* classification? Briefly describe the
NearestNbighbourclusteringalgorithm. ls
(ii) What is a mechanism for deadlock detection ?
Explain with the help of a diagram. s
5. Explain the following terms : 20

(i) Object identity
(ii) Serializability
(iii) oDBC
(iv) OLAP
(v) Deductivedatabase
MCS-043 4 6,000

MCN A

Uploaded by

Copyright:

Available Formats

MCN A

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

MCN A

Uploaded by

Copyright:

Available Formats

PGDCA / MCA (I Year) / BCA

Time : 3 hours Maximum Marks : 75

Note t - Question number 1 fs coJrr,pulsory. Answer any

l. (a) Simplifu the following expression using Karnaughls

MOV AX, 3CD1 H

(ii) DATN( DW OOO5H

MOV CX, DATN(

3. (a) What is a ripple counter ? Explain its working with

5- comp areand contrastthe following : sxs:i5

Time : 2 hours Maximum Mal ks : 60

Note : Question number 1 is compulsory. Attempt any

L. (a) Design an algorithm and draw a corresponding

(b) Write a shell program to generate the first "n"

(c) Explain the different, categories of people involved

2. (a) Write context free grammar (CFG) for if-then-else

(b) Explain the following loader schemes: 5

(b) What is a Virtual Memory ? Explain its advantages

4. (a) Explain the file system used in UNIX. Also explain

(b) What is a feasibilitystudy ? Explain any three types

(b) How do we implement the macro facility within an

.CS-03: FILE STRUCTUREAND

Time : 2 hours Maximurn Marks : 60

Nofe ; Qu estion number 1 is compulsory. Answer sny

l. (a) How can SORTING of data in a data file be done

(b) Why do you needsynchronisedclausein COBOL ?

(c) A me,Cicalshop has two branches which maintain

Customer file : (Not sorted)

2. (a) What is the differencebetweena literal and figurative

3- Write a program in COBOL to cremtean indexed master

Employee master file :

Employee code 10 NUMBERS(Uniqueno.)

No te : Make suitable assumptions,if any.

4. (a) Why are files used to perform input-output

5. Explain the use and syntax'formatof each of the following

CS-04: DATA STRUCTURES THROUGH

Time : 2 hours Maximum Marks : 60

Note r Qu estion number 1 is cotar.pulsory.Answer any

l. (a) Write an algorithm and program code to implement

(b) Define solar systernas two dime-nsionalarray whose

(c) Write a C-function to insert an element into a AVL

(i) abs(trunc (- 36.9))

(ii) round (+ 14.6)

(iii) trunc (sqrt (round(3.+yy1

(iv) abs(round(13.46:' round (18.6Tt)

(v) ord ('p' )

(b) Write a program to exchange values of two variables

3. (a) Write an algorithm to compute the height of a given

(b) Explain the indexed sequential file organization. Write

(i) Adam Bede, 47, Engin eer

(ii) Silas Marner, 50, Doctor

Use a name field of siz,e20, age field of size 2 and

(b) Explain the purpose of MACRO with the help of

5 . Write short notes on the following :

(a) Dynamic Memory Allocation 5

CS-05 : ELEMENTSOF SYSTEMS

Time : 3 hours , Maximum Marks : 75

1- (a) what is feasibility ? Describe any five types of

(b) Discussthe different types of systems g

(c) Explain the role of a SystemAnalyst. What are the