COMPUTER SCIENCE- CS(O) CS-1/18

PAPER-I

Full Marks : 200

If the questions attempted are in excess of the prescribed number, only the questions attempted
first up to the prescribed number shall be valued and the remaining ones ignored.

Answers may be given either in English or in Bengali but all answers must be
in one and the same language.

Answer any five questions

1. (a) Minimi e the sum of products (SOP) expression tor the following
.function:-
F(A,B,C,D) • 2m (1,3,8,9,15) +!"d(6,7,12)
(b) Design a combinational. circuit that accept• a 3-bit number as
input and generates an output binary number equal to square of
the input number.
(c) Find the decimal equivalent ot the following IEEE 754 32-bit
floating-point number:-
0 10000000 110 0000 0000 0000 0000 0000
(d) Implement
OR gates:-the following Boolean functions using a decoder and
(A,B,C) ., z.
mCo,3,4)
(A,B,C) "' m(l,2,7)
(A,B,C) • !_ m(0, 1, 2, 4)

(e) Convert to its equivalent gray code. 1 o+1o+5+10♦5

1. (a) What is the maximum and minimum height of a tree of n nodes 7

(b) Given the i norder and pre-order traversal of a binary tree :-
.
Inorder • D B E A F C G
Pre-Order .. A B D E C F G

(i) Construct the binary tree.

(ii) Find the post order traversal of the binary tree.
(c) Draw a binary search tree (BST) for the input 8,13,27,16,39,
44,55,82,70. Trace the algorithm to insert the node 20 into
the'BST.
(d) Design a recursive algorithm to compute 2n ror any non-negative
integer using the formula :-
2n. 2n-1+ 2n-1
Draw a tree of recursive calls for 24 generated by the algorithm.
8+12+10+10
2. (a) Draw the directed graph that corresponds to the following
adjacency matrix:-

l.9o "91 "'2. \>3

"'· 1 0 1 0
'-'t 1 0 0 0
\)2,_ 0 0 0 1
u.,_ 1 0 1 0
P.T.O.
 CS(O)CS-I/18

-: 2 ·.-
( b) State the quick sort algorithm and compute its worst case and
best case time complexity. Illustrate the working principle
of the quick sort algorithm using the following array:-
[5 , 3, 1 , 9, 8, 2, 4, 7]
( c) Distinguish between spanning tree and minimum spanning tree.
Find minimum spanning free for the following weighted graph:-

(d) Explain how one can identify connected and strongly connected
component;_ of a graph using DFS and BFS. 10 x 4
3. (a) Evaluate} 1d x2 using Simpson's 1/3rd rule taking 6 intervals.
0
Hence, obtain the approximate value of TT .
(b) Using the following data find the value ot ,{2 correct upto five
significant figures.
X 1.9 2.1 2.3 2.5 2.7
tli 1.3784 1.4491 l.5166 1.5811 1.6432

(b) Use Runge-Kutta method of fourth order to find y(Oo2) and y(0.4)
where
2
• 1 + y and y -= 0 when x -= 0 15+15+10

3. (a) Solve the following LP problem:-

Maximize Zs 5x1 + 7x2
Subject to: x1 + x2 -6: 4
3x1 + 8x2'=.24
10x1 + 7x2 b35
x1, x2 0

(b) ABC.Ltd. has two products: 1X' and 1Y1• To produce one Uhit of
'X', 2 units of materil P and 4 units of material Qare required
artd to produce one uru.t of 'Y' 3 units of material P and 2 units
of material Qare required. At least 16 units of each material
must be used in order to meet the committed sales of the two
products. Cost per unit of paterial P and material Qare .2.50
and Rs.0.25 respectively, Formulate the problem as LPP and solve
it graphically to minimize the total cost. 20 + 20
4. (a) State the Maximum Power Transfer Theorem.
(b) Calculate the value of the load resistance Ai, which will transfer
maximum power to the load for the circuit shown in Fig, below.
Also calculate the value of the maximum power thus transferred
to the load.

Contd.••P/3.
 CS(O)CS-I/18
-: 3 ;-
( c) Find the short-circuit current i8c between the terminals A
and B of the circuit given below:- A

?-- -t -::--f-S"o-o ---.1: ,,

(d) Find the voltage drop and current across 3.3K of the circuit
given below using Superposition theorem

sv sv

8+12+1o+10
5. ( a) Explain schemes of Parity and CRC as used for error detection.
(b) Distinguish between adaptive and non-adaptive routing algorithm.
( c) Consider a 2.5 Mbps token ring LAN end frame size of 180 bytes.
If the ring latency' is 210f4s, then calculate th effective data
rate of the LAN.
(c) Implement the function f (A,B,C,D) • m(l,2,5,7,9,l.4) using MUX.
(d) Calculate the minimum number of gates required to implement the
Boolean function XY + Z using 2-input NOR gates. 10 x 4
6. Write short notes on any four o!' the following:-
(a) Carry Look-ahead Adder
(b) Merge sort algorithm and its time complexity
(c) Kruskal Algorith
(d) Synchronous counter
( e) Pushdown Automata
(f) Sliding Window Protocol. 10 X 4

§§§§§§§§§§§§§§
 CS(O) CS-11/18
2018
COMPUTER SCIENCE- PAPER-II
Time Allowed : 3 Hours Full Marks : 200

If the questions attempted are In excess of the prescribed number, only the questions attempted
first up to the prescribed number shall be valued and the remaining ones Ignored.

Answers may be given either in English or ln Bengali but all answers must be
In one and the same language.
Answer any Five Questions 1

1. a) What are the differences among DDL, a,fI, andLCL in SQL ?

5
b) What is a view in SOL ? Give an example of creating a view.
5+5
c) What is a Trigger ? What is the difference between Trigger
and Stored Procedure ?
5+5
d) What are the differences between INNER JOIN and FULL JOIN
in SQL using illustrative examples.
10
e) What is the purpose of a cormnit statement in SQL?
5

2. a) What does functional! dependent mean ? What is trivial fun-

ctional.. dependency ? Explain v.lth examples.
4+4
b) Consider a relation R(A, B, c, D) having tw:, sets of

FD,FD1 = t A B, B C, A.B Dj and FD == {A B, B C, A C,

2

A DJ • Establish whether these two FD sets aresemantically

equivalent or not.
12
c) Create using SOL a new table called CUSTOM:KRS and add five
columns ID (Integer - 10 digits), NAME ( 20 characters), AGE
,integer - 3 digits), ADDRJ:SS (25 characters) and SALARY
(in the format xxxxxx.xx), three of which (ID, NAME, AGE)
shall not accept NULI.,s.
10
d) Write SQL statements for the following queries on CUSTOMSRs
(assuming it has been created v.lth several tuples) a
i) Display all the records from CUSTOMERS table where SALARY
starts with.200.
ii) Delete complete data from C'USTOMERS without d leting the
table.
5+5
3. a} What do you understand by process and process table ? What
are the different states of a process?
8+6
b) What is a thread ? What are the differences betwe process
and thread ? '
8+8
c) What is a semaphore '? Explain with an illustrative example
the role of a semaphore.
10

4. a) What is spooling? Explain. What are the advantages of

spooling?
6+4

P.T.O.
 CS(O)CS-II/18
2

b) Four processes are scheduled with shortest job first

scheduling as follows ,

Process Arrival Execution Service

Time Time Time

PO 0 5 3

Pl 1 3 0

P2 2 8 16
P3 3 6 8

Find the wait time of each process and the average wait time.
4+4
c) What is a virtual memo.ry 7 What are the advantages of such
a n-emo.ry ?
6+6
d) suppose the time to service a page fault is on the average
10 milliseconds and a memory access takes 1 microsecond.

Find the average memory access time with a 99.99" hit ratio.
10
s. a} State the differences among Internet, Intranet, and Extranet.

8
b) What are IP classes andhowcan youidentify the IP class of
a given IP address ? What do you understand by Static IP and
Dynamic IP ?
6+4
c) What is the pu.i:pose of line coding? Discuss bipolar encoding
with an appropriate illustration.
4+8
d) Compare and contrast , 'l'CP and UDP.
10
6. a) Explain different types of Inheritance associated with Object
Oriented P.rogramning. l0
b) What are the differences between an Abstract Class and an
Interface ?
8
b) What are the dif£erences between Method Overloa ng and
Method Overriding?
10
c) Write a Ctt Program to reverse an integer, e.g., if ·the input
is 12345 thecorresponding output will be 54321.
12
7. a) State the characteristics of the RISC Architecture. Cont>are
it with CIS:.
8
b) What are tri-state devices and why they are essential in a
bus oriented system?
10
c) Compare between SRAM and DRAM. Describe the memory hierarchy
of a Computes System.
d) A
d) List and explain the different types C'f micro-operations. d
d
i
8. Write short notes on • t
i
a) Use of Finite State Machines in the design of Lexical v
Analyzers. e
b) Video streaming through Intemet. a
n
c) Assemblers and Interpreters. d
subtractive colors. 4+8

10

l0x