•

ARUNACHAL PRADESH PUBLIC SERVICE COMMISSION ITANAGAR
SUBJECT: COMpUTER ENGINEERING: PAPER
Time: 3 hours Full Marks: 200
Note: Answer Question No. i and any four from the rest. All questions carry equal marks.
Q. No.1. Attempt any 10 10 X 4 =40
a.
Discuss the micro-instruction execution cycle.

b.
Explain the replacement algorithms used in Cache memory design?

c.
What are the issues related to resource sharing of an operating system? Discuss.

d.
Write different ways of deadlock resolution process.

e.
How segmentation is used to implement virtual memory? Explain.

f.
Explain role of the lexical analyzer in designing a compiler.

g.
Why is backtracking discussed with top-down parsing? Explain.

h.
Briefly discuss the Self-Organizing Symbol Table mechanism.

i.
What are the three levels of database architecture? Briefly explain.

j.
Briefly discuss about the tuple calculus and domain calculus. How they are different from each other.

k.
What is "Lossless decomposition" and "Functional dependency" in a database system? Give appropriate example.

I.
Explain the terms "translation distance" and "translation vector" related to 2D transformation.


.Q. No.2. Attempt any 8 (eight) 8 X 5 =40
a.
Why the virtual memory is used in a computer system? Discuss the two resulting
processes: 'page fault' and 'thrashing'.


b.
What are the different ways of resource sharing in Operating System? Discuss.

c.
Define deadlock. Explain this process with proper example.

d.
What is bottom-up parsing? Discuss with a suitable example.

e.
Where is recursive-descent parser used? What can be done to remove recursion from this parsing?

f.
Draw the DAG for the following basic blocks:
B*C



A T B
B
E-D
g.
Union, intersection, product and natural join are all both commutative and associative. Verify these claims.

h.
Define Boyce Codd Normal Form. Give an example to show functional dependencies among the tables and apply BCNF to remove it.

i.
Give a comparison among CGA, EGA and VGA display adapters.

j.
Write the five steps required for a general 3D rotation if the specification for the rotation axis and the rotation angle is given.


Q. No.3. Attempt any 5 (five) 5 X 8 40
a.
What is direct encoding and indirect encoding of micro-instructions? Explain.

b.
Explain the swapping technique of memory management for time-sharing system. Write the categories of a program while existing in the memory in this system.

c.
How demand paging is used for better memory utilization? Explain the page-in and page-out operations.

d.
What is Context-Free grammar? Give example. How does it different from Regular Expression? Explain.

e.
Discuss the lexical-phase errors and syntactic-phase errors in error detection process with suitable example.

f.
Explain briefly the ACID properties of transaction in a database.

g.
What is hidden line? Explain the hidden-line detection method.


1
A.E.(EleCI)·ZOlZ/Computer Engineering p·z

•
•

Q. No.4. Attempt any 4 (four) 4 X 10 40
a.
Discuss the following functions of batch monitor

i. Scheduling
ii. Memory management
iii. Sharing and protection

b.
What is access path in file system? Explain relative access paths and relative access paths.

c.
Draw the transition diagram for keywords used in designing a lexical analyzer. Explain the diagram.

d.
State two-phase locking theorem. Explain exactly how two-phase locking deals with RW, WR and .WW conflicts.

e.
A UNIX process can be in anyone of three modes. What are these modes? Explain each of them for their process priority scheme.


Q. No.5. Attempt any 2 2 X 20 40
a. Discuss the branch control logic for the three general categories of microinstructions based on the format of the address information.
r b. What criteria are important in choosing a file organization? List and briefly discuss the five file organizations.
c. Why normalization is important for a better database design? Define 1NF, 2NF and 3NF. State an example and apply these normal forms and show them in steps.
Q. No.6. ·Attempt any 4 (four) 4X 10= 40
a.
Discuss the three mapping functions used in cache memory design.

b.
What are the sub-functions in process scheduling? Discuss.

c.
Draw and explain the parse tree(s) for the following conditional statement:


if C1 then if C2 then 51 else 52.
Use the grammar below:

stat cond then stat
if cond then stat else stat
I other-stat
d.
What is integrity constraint? Explain it in terms of database, relation, attribute and type constraints. Give example.

e.
What is projection in 3D viewing? Explain parallel projections and perspective projections.


Q. No.7. Attempt any 2 2 X 20 40
a. Constructan NFAfortheregularexpression R=(aIb)*abb. Belowfigure shows thedecomposition of Rinto its primitive components.


eR8
I
R7 b
b
I
I
a

(IJ
1
R2
I
ab
.
b.
Why Disk scheduling is important? Explain the linked allocation and indexed allocation process for noncontiguous disk space allocation.

c.
Write the Bresenham/s Line-Drawing algorithm for Im I 1. State an example to explain this algorithm.


2
A.E.(Elecl)·20l2{Computer Engineering P·2