Computer Science Paper
Time allowed: Three hours Maximum Marks: 300
The figures in the margins indicate full marks for the questions. Candidates should answer Question No. I and 5 which are compulsory and three of the remaining questions, selecting at least one from each section. SECTION-A

1. a. Define TumingMachine. Construct a TurningMachine for the proper subtraction i.e. max where m-n ism-n if and 0ifm<n
b.
Define Deterministic Automata. Draw DFA for divisibility of 3 over an alphabet set }sigma{0.1,2 ....9}

c.
What is addressing mode? Explain the working of direct and indirect addressing mode with example.

d.
What is an instruction cycle? Explain the register organization of 8086 microprocessor in detail.

b.
A computer uses a memory unit with 256K words of32 bit each. A binary instruction code is stored in one word of memory. The instruction has four pa11s: an indirect bit, an operation code. a register code part to specify one of64 bit register, and an address part.


2. a. Define Push Down Automata. Give Push Down Automata to accept the following Language

b. 1. Explain the difference between internal and external fragmentation.
n. Explain the organization of DMA.
3. a. I. Explain the working of cache memory.
11. What are the different types ofROM and RAM?

1. How many bits are there in the operation code, the register code part. and the address part?

11. Draw the instruction word format and .indicate the number of bits in each part.
lll. How many bits are there in the data and address inputs of the memory.
4. a. 1. State Pumping Lemma for Context Free Language.5
ll. Define a Non-Deterministic Finite Automata. Draw a NDFA for the language that have
a 1either two or three position from the end. The alphabet set is
111. Define Context Free Grammar. What is Ambiguous Grammar? Is the given grammar
ambiguous
S->AIB
A->OAI E
B->OBIIB|E
b. 1. What is an indirect measure and why such measures common in software metrics
work?
11. Describe the role of risk analysis in an evolutionary process model like the spiral
model
• Elaborate the test strategies for object oriented software
• Why is a highly coupled module difficult to unit test?
SECTION
5. a. 1. Consider a logical address 0 space of 8 pages of 1024 words mapped onto a physical
memory of32 frames
• How many bits are there in the logical address?
• How many bits are there in the physical address?
11. Explain the necessity for mutual exclusion. What is the minimum level of mutual
exclusion that is necessary for the implementation of useful mutual exclusion in
operating systems? What other fOffilS are useful?
b. 1. Describe the difference between "known risk" and "unpredictable risks" in context of
software development.
11. What is the difference between thread based and use -based strategies for integration
testing? How does cluster testing fit in?
2


6 a. 1. Write short notes on mealy machine. Draw a mealy machine for finding complement ofa given binary number.
11. Consider the E NFA


<img src='./qimages/3399-6a-1.jpg'>
Compute the E-closure of each state.

•
Convert the E-NDFA to NDFA


b. 1. What is the difference between a direct and indirect address instruction? How many reference to memory are needed for each type of instruction to bring an operand into a process register? 15
II. What are interrupts? Draw the block diagram of instruction cycle with interrupts. 15
7 a. i. Assume a stack-oriented processor that includes the stack operations PUSH and POP. Arithmetic operations automatically involve the top one or two stack elements. Begin with an empty tack, what stack elements remain after following instructions are executed?

PUSH4
PUSH7
PUSH8
ADD
PUSH 10
SUB
MUL
ii. Differentiate between RISC and CISe.
iii. What are the four main components of general purpose computers? Show it with a block diagram.
b.
Transform P and V operations on a semaphore S into equivalent critical regions without busy-waiting.

c.
Explain the following with suitable example
•
Size oriented metrics

•
Function oriented Metrics


8. a. l. Describe the difference between short term, medium term and long term scheduling.
11. Explain the organization and working of following types of Turning Machine
•
Multi-tape Turning Machine

•
Turning machine with Semi-Infinite Tape


b.
Which is more valuable to object oriented testing, white box or black box testing? Justify your answer. 15

c.
A computer has a cache, main memory, and a disk used for virtual memory. If a referenced word is in the cache, 20ns are required to access it. If it is in main memory but not in cache, 60ns are needed to load it into the cache, and then the reference is started again. If the word is not in main memory, 12ns are required to fetch the word from disk, followed by 60ns to copy it to the cache, and then the reference started again. The cache hit ratio is 0.9 and the main memory hit ratio is 0.6. What is the average time in ns required to access a referenced word on this system? 15