Que4 Que3 Que2 Quel

QNo.

What
In Class: Sub.:
What
generalizatioIi,
is is
the data 5thSernSE
DBMS
need
modi.
of t.e
key Explain
difference
What
in
ferentiate
ali
is
three mnodel
between
schema with
example
suitable
with
teason
valid
with
membersadvant
between
architecture Sessional-1,
Qctober
2023
ages
of
andsadvantages an
didatekey,
.Explain e
tity
is
maximized
in or
alternatedetail
.

key minimized.
Explain Marks:
Total 15
and

primary Time:1lhr

key

Marks
4 4 2

CO1 CO1 CÓ1 CO1 CO

 COMPUTER ORGANIZATION AND ARCHITECTURE
PC-CS-307

M.M. 5
Time 3 Hrs

questions from
Note: AIl questions in Part-A and Part-B are compulsory. Attempt any four
Part-C selecting at least one question from each unit.

PART-A (15 Marks)

15x1=15
Q. No. - 1Answer the following questions.
() What are the three categories of computer architecture.

(ii) What is virtual memory on a computer.

(ii) What is instruction register.

(iv) What is a RAID system.

(v) What are the different types of fields that are part of instruction.

(vi) Define DMA.

(vii) What is pipelining.

(viii) What is difference between MAR and MDR.

(ix) What is an interrupt.

Differentiate RIS and CISC.

(x)
What is a two address instruction.
(xi)
What are the few commonly used flags.
(xii)
(xii) What are assembler directives.

(xiv) Define memory mapped I/O.

(xv) What is serial communication.

 PART-B (20 Marks)

UNIT-I
Describethe Von-Newman architecture. 2.5
fi)_What is use of Auxiliary memory. How it differ from virtual memory. 2.5
UNIT-II
3Explain interrupt cycle with diagram. 5
UNIT-III
Describe in brief Flynn's taxonomy., 5,
UNIT-IV
Differentiate between programmed input/output and interrupt driven input/output.

PART-C (40 Marks)

UNIT-I
What is booth's algorithm. Solve the following numerical using booth's algorithm:
7multiply -3. 10
7 Define fixed point representation and solve following numerical :
Represent decimal number (-7.85) using 16-bit fixed binaryrepresentation with 8integer
bits and 8fraction bits. 10
UNIT-II
8 Distinguish between micro-programmed control unit and hardwired control unit with
diagram. 10
9
Deseribe the common bus architecture and various computer registers with diagram. 10

UNIT-III
10 Describe various addressing mode with suitable examples. 10

11: i) What is vector processing. Explain array processorswith suitable examples. 5

im) Explain the instruction pipeline with suiteble example and diagram. 5
UNIT-IV

12:i) What is DMA controller. Elaborate it with diagram.

ii) Describe various types of asynchronous data transfer techniques.
13 Write short notes on following:
i) Parallel priority interrupt.
ii) Daisy chaining.
 Roll No. -

THEORT EXAMINATION - DEC 2022 TIME - 3 Hrs

&TECH -CSE SEMESTER - M.M. -73

PAPER - PE-CST SURJECT- Adanxd Algorithms

Nete: AlQuestiens in Part-A and Part-B are ompulsory.Attempt any four questions from
Part-C seteting at least one from each unit.

PART-A (15 Marks)

Q. Na- l Aaswer the following questions. 15x1=15

Detne Iame and Snae Conplexity.

Lixpropertis of Binary Search Trees
Toagical ot is imrlementei using BFS r DES?
hich Nof vahue is retumed by Bellman Fod Algonthm:
Aruskals Algonthm comes under Gre or Dynamic prgramming apprach?
(1) Liss wo algnthms used for pattem matching
( Defie the tem Asvmptotic Notations.

(v)Liss two algonthms used for finding single sourre shortest path.

Match the following:

1. Matrix Chain Multiplication (a)Divide and conquer
2 Huffman Code (b)Greedy approach
3. Binary search tree (c) Dynamic Programming

[Time complexity of topological sort is

(b) V) (c) eE) (d) VE)
Whsch of the foilowing is a correct ordenng?
(b)N N <3N
3 (d)3N <N
(xasBIS uses whichn data structure?
a) Stak (b)Qucuc
(A)Which of the data strcture is generally uscd to implement hacktrackng?
Graph (b)Qucue (C) Tree (ad) Stack
(RrV) KGiventwo sequetices Xand Y. X- A, B,C, B, ), A, B and Y - B, D, C, A, B, A Fnd the
Bongest common subsequece of X and Y
Name tte algorthm used for finding ali pait srtest path.
 PART-B (20 Marks)
UNIT-I
2 E}aborate the term Pseudocode conventions with the help of example.
INIT-II
3 Discuss Hiring Problem with the belp of Algorithm.
NIT-III
4 Write Depth First Search Algorithm ard analy::e its
complexity.
tNIT-IV
5 Write algorithm for Naive String matching. 5

PART-C(40 Marks)
UNIT-I
10
6 Explain the term Asymptotic Notations and explain all the notations.
10
7 Write Algoritim for nsertion sort and analyze its complexity.
(JNIT-I
Find Longest common subsequence by using algorithm for the strings: BACDBand BDCB. 10

10
Solve 0-1 knapsack problem using adynamic programming approach.
You have the following conditions:
Ka) The number of elements, n = 5
b) Maximum weight to pack, W=6
follows:
Kc) Each item (element i) has weight (wi)and benefit (bi), (wi, bi), as
K1, 2),(2, 3),(3, 4), (4, 5), (5, 6)
UNIT-III

how DFS is used for finding topological sort. 10

10 Differentiate between BFS and DFS andexplkin
and analyze its complexity. 10
11 Write Kruskal's Algorithm for finding Minimum spanning tree
U!IT-IV
10
algorithm for string matching.
12 Write Algorithm for Rabin-Karp "bcaab:aaabac" on it.
inpiev:ent the string
13 Given the Finite autcmata in the figure,

q0 q1 q2 D
U
 University Institute of Engineering & Technology
(Besogniscd Under Sectton2@. and J28 of UG)
Kurukshetra University, Kurukshetra RollNo. -
THEORY EXAMINATION - DEC 2022 TIME -3 Hrs.
B.TECH- CSE SEMESTER - V
M.M. - 75

PAPER- PC-CS-303 SUBJECT Formal Language & Automata Theory

Note: AIlquestions in Part-A and Part-B are compulsory. Attempt any four questions from
Part-C selecting at least one from each unit.

PART-A (15 Marks)

Q.No. - 1Answer the following questions. 15MarkS

(1) The number of states in the minimum sized DFA that accepts the language defined by the
regular
expression (0+1)*(0+1Y(0+1)*
(1 mark)
(i:) The C language is a: (l mark)
a. Regular language
b. Context free language
C. Language parsable fully by a Turing machine only
d. Context sensitive language
(ii) If Lrefers to the language that is generated byS-OSO/00, then which of these is true? (l mark)
PL
a. L is not O but regular
b. L is regular but not context-free
fc. L isnot context-free
d. L =O

(iv) In mealy machine, the O/P depends upon?

a) State (l mark)
b) Previous State
c) State and Input
Ud) Only Input
(v) State true or false:
Statement: Every context free grammar can be transformed into an equivalent non (l mark)
push down automata. deterministic
(vi) ATuring machine that is able to simulate other Turing machines:
(l mark)
a) Nested Turing machines
b) Universal Turing machine
c)Counter machine
d)None of the mentioned
 expression. Des

ny regular (3 mark
n*b nd ) in
to
10

(v) Prove that P+ PQQ*bQ* whee P: (3 markaj

Ianyg"
(vi) Explain the Closurv propetics of Reyular (3 marks) 11

Discuss in detail about P and N poblom.

PART-B (20Murks)

UNIT-I
the lollowing lunguages:
ConstrIct the regular expression tor odd over alphabet (0,1}. 2
should be
a) The length of' string come together over alphubet {a,b}.
b) Instring no two a's will UNIT-II
language with
lemma and show a"b'c" is not context free
Explain the concept ofpumping
the help ofit.
UNIT-III 5 ?
Mealey
Moore machine for the following problem and convert it into equivalent
Designthe
and produces residue modulo 3 as output.
machinc.
L"languange that takes binary number as inputUNIT-IV
5
Discuss the extensions of Turing nachine in detail.

PART-C (40 Marks)

UNIT-I

Design NFAwith nullmove for the following expression and convert it into equivalent 10
minimized DFA by showing proper steps.
(aa + b)* (bb + a)*
Find the regular expression for the following machine using Arden's Theorem. 10

ql q2

1
q3

UNIT-II
Construct the granmar for the following
form. language and then convert it into Greibach normal
L (a"b" n0) 10
a) What is ambiguous
or not. grammar and show
whether following grammar is
S->
b) WriteSS|S) null
a CFG for the ambiguous 5+5
are balanced Language
parenthesis,
l over the alphabet
=)} where the words
 UNIT-III
10 Design the PDAfor the following language andalso show the acceptance of a string belonging 16
to that language.
L-(a" b'm'e"dn,m>-1}
11 Convert the following PDA into equivalent CFG 19
((g0.ql}. (a.b). (a,z0}, õ, q0,z0, )
Where õis defined by:
5 (g0,a,z0)=(q0,azO)
5 (g0.a.,a) =(g0,aa)
õ (q0,b,a)=(q1,a)
5 (g1,b,a)=(q1,a)
O (g1,a,a)=(q1,null)
S(g1,nul,z0)=(g1,nul)
UNIT-IV

12 Design a Turing machine for the multiplication of two unary numbers over alphabet -{1}. r 10
eg: 11 multiply by 11l gives 111111.
13 Discuss the following concepts in detail: 4+6
a) Halting Problem of Turing machine.
b) Post correspondence problem along with an example.
 University Lustitute of EnginceriuR &IechnoleRY
(Becexnised LInder Section2and L28at UGO
Kurukshetra University, Kurukshetra Roll No.

DEC 2022 "TIME -3 Hrs.

THEORY EXAMINATION
SEMESTER- sh M.M. - 75
B.TECH -CSE

Database Management Systems

PAPER- PC-CS-301 SUBJECT
from
Part-B are compulsory. Attempt any four questions
Note: All questions in Part-A and
each unit.
Part-C selecting at least one from

PART-A (15 Marks)

15x1=15
Q. No. -1 Answer the following questions.
columns ofa table.
() ..operation is used if we are interested in only certain
(m) Count function in SQL returns the number of
(iii) The set of possible data values is called
when there are
(iv) It is better to use files than a DBMS application
the data from the database that the
(v) The way a particular application views
uses is a
Relational algebra is a. language
(vi) of......children.
Btree oforder m has maximum
(vii) If R has m tuples and S has n
tuples,
of a relation R with relation S.
(vii) |Consider the join
then the maximum size of join is.......
(ix) The natural join is equal to of R1 and R2
produces the relation that has attributes
(X) is....
organization that provides very fast access to any arbitrary record of file
b(xi) The file
definition of a table is
The statement in SQL which allow changing the
(xii)
store in the database.
are used to identify which type of data we are going to
(xii)
attributes to form a primary key is a
(xiv)An entity set that does not have sufficient
(xv) 'AS' clause is used in SOL for
 PART-B(20 Marks)

UNIT-I
example,
gencralizato) with
avd UNIT-II
DisCuNs Cardinality
dependencics in DBMS.
andnon-trivial
soaeeaA

|Ditteret iatetrivial UNIT-III write rule. 5

operations in Thomas's
rulo? Discuss various
write
What is homas's UNIT-IV 5

contlict serializability with example.

Ditlerentiate view nd

PART-C (40 Marks)

UNIT-I architecture of| 10

ofmapping in 3 Layer
latu mapping? Discuss the role
What do youmean by by ANSI-SPARC, How does this architecture achieve data
DBMS as proposed
independence. 10
statements used in QUEL.
7 How aquery is processed, Discuss variousdata definition
UNIT-II
& lAnalyse various DCL and TCL commands. 10
Explain theta join, projection,cross product, left outer join and intersect with example. 10
UNIT-ii1
10 Write short notes on : i) Cost based optimization ii) Two phase locking 10
11 Explain Normalization. Distinguish 4NE, SNF and BCNF with example. 10
UNIT-IV
12 Examinc how deadlock can be resolved in Distributed Databases.
10
13 Differentiate deferred and immediate database modification with example. Analyse 10
ARIES algorithm.
 (ii) () . selecting
art-Catote:
(v) (iv) (ii) No, ES-301
(V) (vi)
(x1) (X) (X) (vii) - All
(xiV)
(xv) (xiii)VWhat
(x1) Discuss Which 1 questions
connectinga When data? IfCarry 67
address?1feven WhatExplain Answer
convert When
used to can
What Explain What the
What Which be content (CY), and is signal
How are two used the the briefly
is is 225 the least in
many meant is the control the the
an numbers for Auxiliary problemconcept is Part-A B.TECH
-CSE University
Interrupt? basic flag of are about following
generated one THEORY
terrupt function by signalsmanipulation number this
to address CS loaded SUBJECT (Recogniscd
Kurukshetra
Kurukshetra
University,
steps 8K=7879H of
in pre-fetch from and
'key are carry accessingmemory lnstitute
of How involved decoding? 8x
added, into questions.
by each
Part-B
request"
debounce the the
of
the
PART-A
Marks)(15 EXAMINATION- Under
ne
ROM and fla g AL
interrupt activated 8086are form? the
ASCII segmentation queue 8086 unit.
MICROPROCESSOR
INTERFACING &
lines interupls instructions
in to the and and word
a are Section of
time'? an sum the Overflow
lP BL in to Engincering
has Vector 8086. access compulsory. 2)
D/A is 8086,
many
how = and with
the are 08, 4200H, SEMESTER -V and
(able'? conversion. of subtracted, an in
heral claSsified? and (0V) the 12B
80862 odd 8086
by it what DEC of &
the is odd Technology
UGO
address
flags, microprocessor? Attempt
IN in is bank 2022
errupt BL. address the after
what
instruction?
What physical compared of
is any
th e memory?
roller lines subtraction? Roll
No, -
is condition four
the address to
instruction of that questions
8259? the
processor of of with TIME
Hrs.-3
the 15x1=15
the an M.M.
-75
to from
be
 11
10
LOOPZ 8.LDS 1.
Explain
maximum
mode? Withrequired Generate 16K With
&8086?for pinDraw programWrite
(b) (a) explain m1n1mum
mode? With
the in Explain
the addressing
2000HandCalculate
3000H Define x the the down
help and are the 8 detail the
DIfollowing
2.CMP
V 9. g. MOVfAX, c. d. C. b. a. the heip relevant and codes
Explain
MOV MOV MOV MOV MOV MOV help the
DS all ofexplainaddressing to concepthighlighting of calculate the for operation
modes (SI] =the the a be a steps 1.
ofa
BP., CX, DX, 4000H, Draw block pi n the the
instrucions: AX, BX, AX, memory valid interfaced
the of involved instruction
following
block
LEA10. (SJ|200017777H(BP+DI] = diagram address
|BX [BX] [3000HJAX 6000H,
that and full for memory
diagram the
MovDX.
MovBX, of
AAS 3. addressing
SS= 8086 diagram S284
+ are address discussdecoding difterent
[BP]= with for PART-C of
when instructions:format
SI used 6000h, up banks draw Marks)(40 [BX] [BP] clock
ISR
100HÊ the UNIT-III th e 8O86 if 2
8086 discussthe PART-B
Marks)(20
by modes concept? control for an [SI] of generator
each1000Hfollowing read UNIT-II
DAA 4. [AX}] RAM inthe
Microprocessor UNIT-I interrupt
this UNIT-IV[4599]h 8086
microprocessor? 8086 UNIT-III UNIT-1I
for and Internal UNIT-I
instruction. 3000H,and chips signals interrupt microprocessor functioningof
8O86 write microprocessor? INT with
[DI]
instructions architecture
of
microprocessor in 40h the
5. cycle 16K
[BX]
= minimum and help
RCL 2100H. is
timing Draw x explain encountered 8086 of
= 8 and
6. 0l00H, will and block
TEST the of microprocessor in
Also accesslfCS= diagrams and Generate
2 8086 function
with interfacingEEPROM diagram?
give[CX}= maximum in
7. microprocessor
JNZ an the the
the example. of of main HEX
80S6 chips
cireuit mode each
in of
10
10
10 10 10
 13 12

reverseprogram?
Draw
Write analog
available
transferring
Interface

anthe input
direction
assembly
diagram for 8-bit
ADC. output
is
present ADC
with
language toDraw of
interface with
delay. ADC
at
the VP4 8086
program to
schematic
a the
ofusing
stepper the
CPU
to ADC UNIT-IV 8255
motor
run and and
and portports.
the write
with a
stepper ConfigureC
clock
8086 the for
requiredinput control
motor
microprocessor
of port
in
assembiy signal.
both suitabie A
f
forward A%2
freasy
arxd lat
ran A
a
a