Illlm111/IIIIIIIIIII IIIII IIII IIII

~ I y'; () 1 ? I .$~ 70803

l{• 'I' • Nn, [j '[ifiKCCCto

I Sl'UH'skr 1\1.S,·. lkgn·,· l•: ~nminnOou, .J111u,f.July - 20ZZ
COMPllTl!'. H S< 'll( N( ' Ii'.
Prohlt•nt Solvin~ T,·,·hniq11c~
(CBCS Scheme)
Paper : MSC 103T

Time : 3 Hours Maximum Marks : 70

Note: Answer any FIVE. Each carries 14 marks.

•
~
1. What is complexity of an algorithm? What is best, worst and average case complexity
~ of an algorithm. Define Big Oh notation.
b) Write an algorithm, and flowch~p to find the sum of the following
. 2 32 2 2 ; ·
senes: I + - 5 + ......... +n (7+7)

Va) Given a string m, write an algorithm to find the length of the string, and finding a
substring oflength k (which is less than m) in the string.
~ What is well defined recursion? Write a recursive algorithm to find GCD of m, n
f' V Trace your algorithm to find GCD of numbers 1124 and 22. o/ (7+7)

3. ~ Write an algorithm to multiply two matrices of order m X n and n X p. /

~
~
Write an algorithm to find the square root~ a num~Find square rooy6'~ ~.(7+7)
·
4. ~ Write a flowchart and an algorithm !9 reverse an integer number. Trace your algc,rithm
r ,~G~
I''<:.) for integer n=674. ~~ ~ 1 't
~ What is 2 way merge s_ort? With suitable example discuss two merge sort. (7 +7)

S. @ /sort the elements {8, 6, 3, 4, 2, 7, 5, 0, 1, 9} using merge sort algorithm. Write the
/ algorithm. What is the complexity (time) of your algorithm.
}S» Write an algorithm to find the k th smallest element in ~ay. (7 +7)

[P.T.O.
 -.. u , c . . , t'JO Ur.s
l11w
'
r,I C,1IOI/\'
• fo ,. ,. . . , . ,
n

(2) 708 03
11111111111111111111111111111111111

n.
Trace your algo rithm to remove duplicates
6. " '1ite an aJg01i tlu11 to remo ve duplicritcs from a list.
from the foJiowing list {I , 3, 3, 4, 5, 6, 6, 6, 7, 8,
8} /1 (1 4)

Write an algoritlun to find pseudo random number.

, __ v- ,v /
into othe r base (u to 36) . Trac e
Write an algoritlun to convert the decimal number 1
your algorithm to conv ert (1234) 10 to binary number.
c:,;~ ~ g 7+7
\1,., J ~
', \ ''
\\
ments avai lable in Pyth on with
8. a) Illus trate the diffe rent types of control flow state
flowcharts .
• b) Write Pyth onic code to solv e the quadratic equa tion
ax** 2 + bx+c=O by getting
(7+7 )
inpu t for coef ficie nts from the user.

-~ / I
I) ~
J
/ I; ~J
\.)
I
\ r
\ ll '
0
~ 4
I
}
/
.?
1'i'
'. ( 2..

l ·\ ' r' l- \ ., .,
2 2,

', i -{ C. \j b ', \'-

•1- ? ·f I ~c ,J ':" bl
'1 ~.:J
;, .-l
4ti ) bf )
I

31 ' ':. t/
\ ~ tf
( i 1J (
)
~

·-
\

.,.. r
 11111/IWllllliUl~I111111 70804

I ·" ''llll''"'' i\t.Sr. 1,:,11111i11a1i1111 1 1\1:! ) - 2023

llr)!l 't'('

COi\ 1Pl ITl •~I{ scn:NC E

Dab, ~t1ud11 n.·s
(( 'B('S Scheme ) (Y2K2 I)
Pupcr: MSC10 4T
Time : J Hours Maximu m Mtt rk s : 70
lustructh ms to candidates:
Answer any Five full questions.
l. a) What isADT? Explain with a neat figure.

b) Explain the asymtotic notations used to denote complexity of algorithm.

c) Calculate the number of comparisons required to match the given pattern using Boyer
Moore algorithm

Text: 00010001010001

Pattern: 0001 (4+5+5)

2. a) What is the advantage oflinked test over Array?

b) Write C functions to implement the push and pop operations on stack

c) Evaluate the postfix expression using stack.

6 2 3 + - 3 82/ + *2 /\ 3+
(2+6+6)
3. a) Solve Tower of Hanoi problem where munber of disks n=3. Also write algorith m for
the same.

b) Write algorithms for insert and delete operatio ns in linear queue.

(8+6)
4. a) Write a C progrrun to search on element in a circular linked list.

b) Write an algorith m for Breadth First search (BFS)

(7+7)
5. a) Define the followin g tenns.

i) Binary tree

[P.T.O.
 ( ' nn1p11fcr· A •""tli't
' l'c:f II r·c
(CIJCS "dH•nu• \ ' 2K21)
Pnp,•r • l\tL' r "
·, ·;,.,,, : l ''•HI,.
ark!

()}
70804
llrn 11111 111111111111111 11111111
I
11) lk1pht 11t ;1 tier

111) ( \rn1pktc 1\111,11\ ltl'C

I\) , \11\H)~( l'Olllpll'll' Bltl.llY (I CL:

,) Binnry search tree

b) Construct anAVL tree by inserting the following clements in the given r,rdcr
(5 + '))
63, 9, 19, 27, 18, 108, 99, 81
6. a) Write the algoritlun for selection sort and trace it for the following values:

29, 70, 15, 10, 18, 22, 19, 14

(8-6)
b) B1iefly explain the different techniques of collision resolution.

7. a) Create a BST for the numbers 8, 3, 10, 1, 6, 14, 4, 7, 13. Also transfer the BST lnorder.
Preorder and postorder.
b) Find the shortest distance from source vertex 'S' to remaining vertices in the following
graph using Dijkstra's algorithm. ( 6+8)

8. a) Write a program to determine whether the given string is palindrome or not.

Explain Topological sorting with an example. (7+7)

b)
 7080 1
11111MIQ Ill/Ill /II /fl/ MIi
l {c')\ Nn . [ 1=1 {_1 D
f ,'H' n1<·~h '1 1\1,S,·. llq~• ,.,, 1, x111111Jrn lion
, M ~Y - 202J
COl\ 11'll ll•: I{ S( ' I Jo:N ( E
( ' omp1 1h'1 · A1d1 lh'du 1c·
(< 'll( 'S Sd1t.'mt· V2k. 2 l)
Pnpt•r· : MSC
Max imum Mar ks : 70
Time- : J lloun ,
I11stnu:tio11.~ to C(l11r/idates:
es 14 mark'>
Answ er any Five fuJJ ques tions. Each ques tion carri
(4)
1. a) Perfo nn the follo wing :
al
i) Conv ert the decimal nwnb er (278) into octal and hexa decim
y and Octa l
ii) Conv ert the hexa decim al nwnb er (4A5) into binar
don' t care cond ition s in SOP
b) Simp lify the follo wing boole an funct ion toget her with
. (5)
form. Draw the logic circu it for the simp lified expre ssion

F(A, B,C, D) =1:(0 ,1,2,3 , 7,8,10)

d(A,B , C,D) = 1:(5,6 ,11,1 5)
(5)
c) Design full Adder.
(8)
2. a) What are decoders and encoders? Explain 3-to - 8 decoder.
(6)
b) Explain Booth multiplication algorithm with an example.

t. (7)
3. a) Discuss the phas es of instruction cycle with a neat flow char
(7)
b) Explain mem ory reference instructions

uss hard wired timing

4. a) What is the function of control and timing unit in computer Disc
(8)
and control unit in detail.
(6)
b) Explain any five addressing modes with examples.

(8)
5. a) Write a note on arithmetic and shift instructions.
(6)
b) Differentiate between RISC and CISC.
{P.T.O.
 - ,., ' Yl o
Urtccn lllark .
s.

Illll/ 11111111111111 lllll llll /111 (2)

6. a)
Compare isolated 1/0 with memory mapped l/0
70801
b) (4)
Explafo DMA controller with a neat diagram.
c) Write a note on SIMD architecture. (6)
(4)
7. a)
Discuss pipeline execution in scalar and vector processors.
b) (8)
With a neat diagram, explain hierarchiaI memory technology.
(6)
8. a)
Explain the three shared-memory multiprocessor models with neat diagrams.
(9)
b)
Write a note on distributed memory multicomputer model.
(6)
 IfW1/WI 111111,m11111 1m 1111 70803

I s,, m,•id,,,, M .S,·. l> q! t ,,,, l•. ~11 tnin:11 ion . 1\b,y - 2'12 \
f OMl'l l' l lf, H '-t ( 11•, f'. f L
PJ nhlt•na ~ol vlug r._,, huiq,u·
(<'B( 'S Sc-hnn,•) (Y 2 1<2 1)
Pnpt·t· : MSC '- I OlT
Tim<-' : J 1lo1u-s M,rximu m M~rks: 7()
Instructions to c,uulidares:
I) Answer any Five full questi ons.
2) All quest.i ons carry fou1ieen marks.

1. a) What do you mean by best, worst and average case compJexjty of an algon•.brn? Find
the worst case complexity of linear search algorithm. (8)

b) Write an algorithm and flowchart to find the nth fibonacci number. (6)

2. a) Using suitable example, explain the relation between pointers and arrays. (5J

b) Trace and sort the following list of numbers using quick sort:

45,36, 15, 92, 35, 71 (6)

c) What are command line arguments? Explain with an example. (3)

3. a) Write an algorithm to find the kth smallest element in an array. (7)

b) Write the algorithm for text line editing. Explain with an example. (7)

4. a) Write an algorithm to find smallest divisor of an integer. Trace the algorithm to find
the smallest divisor of 45. (7)

b) Sort the list of elements 9, 16, 32, 8, 41 , 5, 80 using heap sort. (7)
I

5. a) Write an algorithm to compute prime factors of an integer. Trace the algorithm to find
the prime factors of 1092. (8)

b) Explain any four string operations with suitable examples. (6)

[P.T.O.
 • Cc h'-'

~)

b)
(2) 70803
111111111111 111,111111 rrirr 11111111
FxfJ loin the Ji11c111 pn1lcr n s c: 11 c hrr, g a Igor ilhm with an cx;11npl c. (7) 0
6. n)
vVnt c nn olgori1l1111 :ind llo wc hni l to f 111d th c , t·vc, -.co l ,in inti.;gcr. Trace the algorithm
h)
to find the reverse or 7lZ'"> . (7)

Write a C program us ing s~itch Slat crncnt lo calculate th e grade of a student, given
7. a) 1
·ks of 5 s ubjects as mput.
t I1e mar
GradeA
90-100
GradeB
70-89

40-69 GradeC

<40 Fail (7)

b) Write an algorithm to find pseudo random number. (7)

. a) Define dictionary. Write a python program to demonstrate working with dictionaries

8
~~- rn
b) Explain the various looping statements in python with suitable examples. (7)
 70802
1111 11 IU 11'11 WIii:1111
lhl' .. I 1 f l f II1l
1
1
I ::,,, ,.,,to•• \I~,• 0••1:1 ,,,, I• ,u 111i11:,lin11 , 1\ 11 ) • Zfll
11
< 0 1'1Pl l ll'I< :--; <II ', ( I
( )p,•l 1tf ill)~ S ,\'SI t' III ~

(( B( ~ \ 21\21 ~dH•lllt' nm,:1rds)

Papt'l : i\1~CI02T

riml' ; J Hours
1n,rmctio11,, ro ca1Hlidate.,:
,\ns\\ er any Fh c full questions. Cach question ca1 ries 14 marks.
(7}
Explain the different services provided by the operating 5y~tem .
l. a)
What do you mean by a system call? What are the different types of system calls1(7)
b)

What are semaphores? Explain the different methods of implementing semaphore::i

(6)
2. a)
(8)
b) Explain the Readers - Writers problem in detail.
(2)
3. a) What is demand paging?
(7)
Explain the FIFO page replacement algoritlun with an example.
b)
(5)
Explain the various process states with a neat and a labelled diagram.
c)
(7)
4. a) Describe the various file allocation methods.
(7)
b) Write short notes on the various access methods in a file system.
(6)
Explain the concept of an access matrix with neat and labelled diagrams.
5. a)

b) Write short notes on

1. Virus
(8)
11. Worms

{P.T.O.
 (CBCS Sc heme)
Paper: MSClO l T

-~~IM~~ <~ 70802

6
- a) Explain the Round Robin scheduling algorithm w ith an exam pl e. (8)

b) Explain the various methods which enable to reco ve r from dead locks. (6)
7
· a) What is a deadlock? Briefly describe the various methods of deadlock prevention(S)

b) What is a security attack? What are the different types of security attacks? (6 )
8. a) Write short notes on

1. Segmentation

ii. Paging (8)

b) Explain the shortest seek - time - first disk scheduling algorithm. (6)
r 70801
1111 fll lMl'II IWIIII1ll1
,, J ,t t i l l \ LJ
t ,:, 111111,11in11 . ,f 1111l / lli l\ 2022
I :-,,• 11 H ,It I '\ 1. ...., 1,. lkJ" 1, 1,

(' 01\ 11 •!! I I• H '< ILi'! ( I

( Olli)lllft' I' A11•llil1 •( lllll
(' I\( ·:; :--,c ht lt)I ' )

1':1p<·1·: M~,( 1011

'[' 110 ,, : ., II our-..

Jmtrncth111., lo ( 'am/it/ate., .
I) /\il!:-,\\'l'I' all) li ivc rull qu es tion !:-..
2) hach quc!; t1 rn1 carri es 14 marks.

I. u) l'er!orm the following number conversion.

i) ConvcrL 31411 01 Lo ( ) 2• ( ) 8, ( ) 16

b) Sirnpli I)' Lhe !'ollowing Boolean Ji.met.ions F (W.X.Y.,Z)= I (0, L 2. 4. 5, 7. 8. 10, 11. 15 ).
(5)
c) Whal are the differences between half adder and full adder. (5)

2. a) Subtract 85 ( 101 from 36 ( 10 1 using 2's complement method with an example. (8)

b) Explain arithmetil.'. and logical instruction. (6)

J. a) What is control unit? Explain in detail Hard wired and Micro prognnmed control
unit. (8)
b) What is Logic Microoperations? Write list and hardware implementation of Logic
shift Micrnoperaiions. (6)

4. a) What do you mean by register transfer language? Discuss with lhe help of suitable
example:, \ arious register transfer operation. (8)
b) Explain data l-hwucl s in ILP. (6)

(P.T.O.
 /!/1" rn Iii/I 1fU lllil Iii 1111 70801
s. :1 ) l)t.t\\ 111~- llu\\ 1·'1:111 iii i1 1s l1111.:ticrn L')rk :tlld cxpl:1i11 111 d1·1:iil . (k)
b) \\ 1 ,,~, ,1 JH'll' 1111 i11•,1111L'lin11 lorrn:il. ( (j)

(L :t ) \\ 'nk thL' diffL'fL'llL'~· hL'l\\ecn RISC and ClSC. (7)

b) \\ rile a nole on SI I\ ID and Ml lVID nrchitecturc. (7)

7. a) Perf<.)rm l~ncoding ul data bits 001 1 into 7-bit even parity hamming code. (8)
b) Explain DfvL\ L'<JlllrolJer vvi1h a neat diagram. (6)

8. a) What is PRAM'! E:\plain the four Memory updates or PRAM and variants. (7)
b) What i~ sequential and Weak Consistency model ? EAplain Sequential consistency
in detail \\·ilh neat diagram. (7)
 1111m 1111111111111111111111111111 70802

I SC'mcsh.•1· M.S(·. D••~fl'<' 11:xnmhanO,rn, .June/July - 2022

COM PlJTEH. sc11 1:Nf'J1:
Opcrnfin~ System
(C'BCS Scheme)
Paper : MSC - 102T

Time : 3 Hours Maximum Marks; 70

/11structio11s to candidates:
1) Answer any five full questions.
2) Each question carries 14 marks.

1. a) What is buffering and spooling?

b) Explain distributed system with its advantages?

c) What are threads? Explain single and multi-thread process with block diagram?
(2+5+7=14)

2. a) What is critical section problem? Explain with general structure and write its
requirements?

b) Explain resource allocation graph with example?

(7+7=14)

3. a) What is thrashing? Write causes of thrashing?

b) Explain SJF process scheduling algorithm with an example.

(7+7=14)

4. a) What is deadlock? Discuss necessary & sufficient condition for a dead lock to happen

b) Explain indexed method file accessing with block diagram?

(7+7=14

(P.T.
 ( 1.)
11111IIM 1111111111111111111111 70802
5. :i) \\ h,1( i.s .scc111 ,1, 111 n1w1 al i 11 g syi, 11•111 1/ \V, i1,· ~1ny f 0111 gq;ds rd prritcc tion'!

h) \\ '1,1t .11 c, 1111..,c,<,'l Fx pl:i i 11 11 s cl i f In <'Ill lyp,·s'/

6. ,l) I •,pl:1111 k:i.st I ccc111ly 11snl 111c11101 y p:i gc I c.:p lrKClllClll ,ilgr,ri th rn .

b) i\ kntion different responsibilities of memory 111am1gcmc.:nt'!

(7 '-7= 14)

7. a) Explain readers - writers problem?

b) A disk driv~ has 200 cylinders, numbered 0 to 199. The drive is currently ~erving a
request at cylinder 53. The queue of pending requests, in SSTF order, is
98,183,37,122,14,124,65,67. Starting from the current head position, what is the total
distance the disk ann moves to satisfy all pending request for the above algorithm?

(7+7=14)

8. a) What is a page, a frame? a page table? Discuss the difference between paged memory
& segmentation memory.

b) Write advantages of demand paging.

(7+7=14)