Sub Code: BEET 101 ROLL NO……………..……………..

END SEMESTER EXAMINATION, 2022 – 23

I Year, II Semster B.Tech.
Basic Electrical Engg.

Duration: 3:00 hrs Max Marks: 100

Note: - Attempt all questions. All Questions carry equal marks. In case of any ambiguity or missing
data, the same may be assumed and state the assumption made in the answer.

Q 1. Answer any four parts of the following. 5x4=20

a) Explain voltage and current source. Also define ideal voltage and ideal current
source.
b) Determine the value of the resistance R ohm Shown below if potential drop
across it is 25 volts

c) State maximum power transfer theorem. Derive condition for maximum power
transfer to a purely resistive load
d) Determine current in 10ohm resistance using Mesh analysis.

e) Establish a relationship between Line voltage, Phase voltage and Line current,
Phase current for a star connected three phase A C system.
f) Explain BH Curve in detail with suitable diagram.
Q 2. Answer any four parts of the following. 5x4=20
a) Derive the expression for RMS value of a sinusoidal waveform. Define Form
factor and peak factor.
b) Define apparent power, active power, reactive power and power factor.
c) A resistance of 100 ohm is connected in series with a 56 microfarad capacitor to a
supply at 230 V, 50Hz .Calculate (i) impedance (ii) current (iii) power factor (iv)
voltage across the resistor and across the capacitor.
d) Explain resonance for series AC circuit in detail. Also define quality factor.
 e) Three similar coils are connected in a star system and take a total power of
1.5KW at a power factor of 0.2 Lagging from a 3 phase 400V, 50 Hz, supply
Calculate Resistance and Inductance of each coil.
f) Derive the expression for total power measurement of 3 phase system with two
wattmeter method with suitable diagram.
Q 3. Answer any two parts of the following. 10x2= 20
a) Write down the similarities and dissimilarities between electric and magnetic
circuit.
A steel ring 30 cm mean diameter and of circular section 2cm diameter has an air
gap of 1mm long. It is wound uniformly with 600 turns of wires carrying current of
2.5 A. Find (1) total MMF (2) total Reluctance (3) Magnetic flux. Neglect magnetic
leakage. The iron path takes 40% of the total MMF.
b) Define working principle of single phase transformer. Drive expression for EMF
equation of single phase Transformer. Also enlist various losses occur in a
transformer and deduce condition for maximum efficiency.
c) The following reading were obtained from OC and SC tests on 8kVA, 400/100V,
50 Hz single phase transformer:
Open circuit test (LV side): 100Volt 4Amp. 60watt
Short circuit test (HV side): 10 volts 20Amp. 100watt
Calculate (i) Calculate the transformer parameter from above test result.
(ii) Efficiency at full load and 0.8 power factor
(iii) Calculate the load at which maximum efficiency occurs and also find
Maximum efficiency at 0.8 power factor lagging

Q 4. Answer any two parts of the following. 10x2= 20

a) What is rotating magnetic field? Explain the construction and working principle
of 3-phase induction motor.
b) What is the importance of back emf in DC Motor? Also explain different types of
DC motor with neat diagram.
c) Explain why single phase induction motor is not self-starting motor. List the
various starting method use for single phase induction motor it and also explain any
one method in detail.
Q 5. Answer any two parts of the following. 10x2= 20
a) Define the following
(i) Switch fuse unit
(ii) Types of wire use in electrical installation
b) What is Battery? Explain different type of Batteries. Also mention important
characteristics of batteries
c) 4 tube lights of 40w each, 2 fans of 60w each, a television of 100w and an air
conditioner of 1kw are used for 6hrs daily .Find the cost of electrical energy for 30
days. If 1 unit of energy costs Rs2.50.if operating time of each reduce to half then
how much saving is possible.

**********
 Sub Code: EET 001/BEET-101 ROLL NO……………..……………..

ODD SEMESTER EXAMINATION, 2023 – 24

Ist Year, B.Tech.
BASIC ELECTRCIAL ENGINEERING

Duration: 3:00 hrs Max Marks: 100

Note: - Attempt all questions. All Questions carry equal marks. In case of any ambiguity or missing data,
the same may be assumed and state the assumption made in the answer.

Q 1. Answer any four parts of the following. 5x4=20

a) With respect to DC circuit, state and explain Kirchhoff’s law.
b) A sinusoidally varying alternating voltage is given by, 𝑣(𝑡) = 𝑉𝑚𝑠𝑖𝑛𝜔𝑡, obtain
its RMS value of voltage in terms of maximum value.
c) A pure inductor excited by sinusoidally varying AC voltage, show that the
average power consumed by inductor is zero.
d) Two resistors are connected in parallel and a voltage of 200V is applied to the
terminals. The total current taken is 2.5 A, and the power dissipated in one of the
resistors is 1500 W. What is the resistance of each element?
e) A load resistance 𝑅𝐿Ω is connected across the source 𝑉𝑆 with internal resistance
𝑅𝑖𝑛𝑡 in series with source; obtain the condition that the power transferred to load
from source is maximum.
f) Three phase power consumed by the balanced load is given by 𝑃 = √3𝑉𝐿 𝐼𝐿cos(∅)
watts, then show that two wattmeter sufficient to measure three phase power P
Q 2. Answer any four parts of the following. 5x4=20
a) For the single-phase transformer, obtain an expression for EMF induced in either
primary side or secondary side.
b) A dc motor running with a speed of N rpm, obtain an expression for EMF induced
in the armature winding.
c) To operate the transformer in maximum efficiency always, derive at what
condition, this can be achieved.
d) An alternator running at N rpm, induces an emf in the armature conductors of the
machine and obtain an expression of induced emf.
e) In a domestic consumers end, discuss how two-part electricity tariff imposed to
calculate electricity bills.
f) A three single phase balanced load connected in three phase three wires star form,
with the help of phasor diagram, obtain the relationship between line and phase
quantities of voltage and current.
Q 3. Answer any two parts of the following. 10x2= 20
a) Find the Thevenin equivalent to the left of XY. Also calculate the maximum
power to be transferred from source to load if variable resistive load is connected
between XY.
 b) Using Thevenin theorem, find current across load of (4+j6).

c) Find the resonance frequency in Hz of given circuit:

Q 4. Answer any two parts of the following. 10x2= 20

a) With Diagram, Explain Armature Reaction in DC machine and how to improve
armature reaction. An 8-pole wave connected armature has 600 conductors and
is driven at 525 rev/min. If the flux is 20 mWb. Determine the generated e.m.f.

b) A 100 KVA, 1000/10000 V, 50 Hz transformer has an iron loss of 1200 W. The

copper loss with 6A in high voltage winding is 500 W. Calculate efficiency:
(i) 25% (ii) 100% nominal load at 0.8 pf. The output terminal is being maintained
at 10000V. Also calculate maximum efficiency at 0.8 pf.

c) Explain the construction of Induction motor. The efficiency of a 400 V, 3 phase,

6 pole Induction motor draw a libe current of 80 A at 0.75 pf at 4% slip is 85%.
Calculate the shaft output and shaft torque.
Q 5. Answer any two parts of the following. 10x2= 20
a) With a neat circuit diagram, explain the operation of MCB, MCCB and RCCB.

b) What is the necessity of earthing? Give detailed explanation of types of earthing.

c) Explain the general layout of Power System in India with their KV rating at
different levels. In a house, there are 5 lamps 25 Watt used 14 hours per day, a 200
Watt refrigerator used 24 hours per day, and a 125 Watt water pump used 8 hours
per day. How much electrical energy is used for a month (30 days)
**********
 SPECIAL BACK PAPER
Sub Code: BEET101/201, TEE-101/201 ROLL NO……………..……………..

FIRST/SECOND SEMESTER EXAMINATION, 2022 – 23

Ist/2nd yr B.Tech.
BASIC ELECTRICAL ENGINEERING

Duration: 3:00 hrs Max Marks: 100

Note: - Attempt all questions. All Questions carry equal marks. In case of any ambiguity or missing data,
the same may be assumed and state the assumption made in the answer.

Q 1. Answer any four parts of the following. 5x4=20

a) What are the significances and limitations of series resonance phenomena in
R-L-C circuit? Explain in brief.
b) State and explain the “Double Resolving Field Theory” in single phase
Induction Motors with neat sketch and relevant expressions.
c) Enlist any ten domestic applications of single phase Induction Motors.
d) What are the applications and drawbacks of three phase synchronous machines?
e) State and explain the “Norton’s Theorem”. Explain why this theorem is dual of
“Thevenin’s Theorem”.
f) Explain why “Super Position Theorem” is not applicable for Power and Energy
verifications.
Q 2. Answer any four parts of the following. 5x4=20
a) What are the advantages and disadvantages of single phase single value capacitor
start type Induction Motor and single phase two value capacitor start and run type
Induction Motor? Explain in brief.
b) Differentiate between series and parallel resonance phenomena in R-L-C circuits.
c) Write any five industrial applications of three phase synchronous machines.
d) Discuss the any ten applications of “Maximum Power Transfer Theorem”.
e) Discuss the constructional features and working of different types of measuring
instruments for measurement of voltage, current and power.
f) Consider the circuit shown in Fig. 1.
 5Ω 10Ω

G
G IG

10Ω 20Ω

5Ω
100V
Fig. 1
Find the value of IG in Fig. 1 by Norton’s Theorem. Also verify your result by
conventional approach like KVL or KCL.
Q 3. Answer any two parts of the following. 10x2= 20
a) Discuss the working principle of single phase shaded pole type Induction Motor
with a neat sketch and relevant expressions. Also mention their domestic
applications and limitations.
b) State and proof “Thevenin’s Theorem” for DC circuits. Also mention its
limitations.
c) Consider the circuit shown in Fig. 2.

5Ω
5Ω
A (+)

10V 5Ω 5Ω 5Ω

1V
B (-)
5Ω

Fig. 2
Find the Thevenin’s equivalent circuit (across AB terminals) of above Fig. 2.
Q 4. Answer any two parts of the following. 10x2= 20
a) Discuss the constructional feature and working principle of “STEPPER
MOTORS”. Show that the motion step angle (  ) is given by:

3600
 , the symbols having their usual meanings.
mP
 b) Consider the circuit shown in Fig. 3.
5A

5Ω 5Ω A (+)

5V 5Ω
5Ω B (-)

5A
Fig. 3
Find the value of maximum power transfer from sources to load {since load
resistance (RL= 10 ohms) is connected across AB terminals} in Fig. 3.
c) Consider the circuit as shown in Fig. 4.
5

A



5 
5
DC 5 VOC

10V
B


Fig. 4
Determine the Thevenin’s and Norton’s Equivalent circuit across the AB terminals.
Q 5. Answer any two parts of the following. 10x2= 20
a) Explain why three phase induction motors can’t runs at synchronous speed
(Ns=120f/P), the symbols having their usual meaning? A 3-phase 454V, 47.50 Hz
induction motor has 4% slip. Find the frequency of the rotor e. m. f.
b) State and explain the merits and demerits of single phase Induction Motors over
three phase Induction Motors?
c) Write a short notes on the following:
(i) Star-Delta Transformation with help of suitable example
(ii) Delta-Star Transformation with help of suitable example

**********
 Sub Code: EET-001 ROLL NO……………..……………..

FIRST SEMESTER EXAMINATION, 2022 – 23

Ist Year, B.Tech. – Common to All Branch
BASIC ELECTRICAL ENGINEERING

Duration: 3:00 hrs Max Marks: 100

Note: - Attempt all questions. All Questions carry equal marks. In case of any ambiguity or missing data,
the same may be assumed and state the assumption made in the answer.

Q 1. Answer any four parts of the following. 5x4=20

a) A 200 Ω resistance is connected across a 10 V supply. Calculate (i) the current through
the resistor, and (ii) the power loss.
b) The current changes at 0.5 A/s in 1 H inductor. Determine (i) voltage across it and (ii)
energy stored in the inductor after 2 s.
c) A capacitor of 10 μF is connected across 200 V dc voltage. Calculate the energy stored
in it. If the same capacitor stores one mJ of energy, obtain the amount of charge stored.
d) Enumerate the types of batteries.
e) Considering a sine voltage wave, what is the difference between peak voltage,
RMS voltage, and average voltage?
f) With the help of neat circuits, find the series and parallel resonance conditions
for the RLC circuit.
Q 2. Answer any four parts of the following. 5x4=20
a) Draw and differentiate between salient pole and cylindrical pole synchronous
machine rotors.
b) With the help of various examples, differentiate wires and cables used in
electrical applications.
c) Derive the equivalent resistance equations during star-delta and delta-star
conversions.
d) In Figure 1, find the power loss in the 4 Ω resistor

2Ω 2Ω

3Ω
4Ω

2Ω 2Ω

10 V

Figure 1
e) In a balanced three-phase load, what will be the reading of wattmeter-1 (P1) and
wattmeter-2 (P2) for the following cases? (Given that the line voltage and line current is
equal to 1 unit)
Case 1: unity power factor
Case 2: zero power factor
f) Describe active, reactive, and apparent powers. Also, derive the power factor equation
using the power triangle method.
Q 3. Answer any two parts of the following. 10x2= 20
a) A magnetic circuit with a single air gap is shown in Figure 2. The core dimensions are
as follows. Core cross-sectional area (Ac) = 1.8×10-3 m2, mean core length (lc) = 0.6 m, gap
length (g) = 2.3×10-3 m, N = 83 turns. Assume that the core is of infinite permeability and
neglect the effects of the fringing field at the air gap and leakage flux. Calculate (i) the
reluctance of the core and (ii) the reluctance of the air gap. For a current of I = 1.5 A,
calculate (iii) the total flux, (iv) the flux linkages of the coil, and (v) the coil inductance.

Core

Air gap g

Figure 2
b) In Figure 3, (i) find the load current through a 2 Ω resistor utilizing Norton’s theorem.
(ii) prove that the current through a 2 Ω resistor is equal when utilizing Thevenin’s theorem.
i0

6Ω
3Ω 2Ω
12 V 3i0

Figure 3
c) Explain the following in brief.
(i) B-H characteristic
(ii) PMMC
Q 4. Answer any two parts of the following. 10x2= 20
a) With the help of proper examples, describe the major difference between static
and rotating machines. With the help of a neat sketch, explain the construction and
working principle of a DC Machine.
b) A DC generator has an armature emf of 100 V when the useful flux per pole if 20 mWb
and the speed is 800 rpm. Calculate the generated emf (i) with the same flux and a speed of
1000 rpm, (ii) with a flux per pole of 24 mWb, and a speed of 900 rpm.
c) The following data are obtained on a 200 kVA, 50 Hz 2000/200 V distribution
transformer.

Transformer test Voltage (V) Current (A) Power (W)

Open circuit test with HV open- 200 4 120
circuited
Short circuit test with LV short- 60 10 300
circuited

Draw the approximate equivalent circuit of the transformer referred to the HV and LV sides,
respectively.
Q 5. Answer any two parts of the following. 10x2= 20
a) With the help of a neat sketch and equivalent circuits, explain the construction and
working principle of a three-phase Induction Machine. Also, explain the two types of
Induction Machine rotors. With a help of torque-slip characteristics of a three-phase
induction motor, explain the three modes of operation.
b) With the help of a neat sketch and diagram, explain the following briefly.
(i) Switchgear
(ii) MCB
(iii) ELCB
(iv) Generation, Transmission, and Distribution in Power Systems
c) Obtain the energy consumption for the following data.
One bulb (100 W running for 2 hr), One fan (75 W running for 4 hr), and One fridge
(50 W running for 6 hr).
If the running time of the above three appliances is reduced to by half, what will be
the energy saving? Also, find the money saved, if the unit price is Rs. 5.

**********
 Sub Code: BCST602 ROLL NO……………..……………..

EVEN SEMESTER EXAMINATION, 2023 – 24

3rd
yr B.Tech. – Computer Science & Engineering
Compiler Design

Duration: 3:00 hrs Max Marks: 100

Note: - Attempt all questions. All Questions carry equal marks. In case of any ambiguity or missing
data, the same may be assumed and state the assumption made in the answer.

Q 1. Answer any four parts of the following. 5x4=20

a) What is difference between Compiler and Interpreter?
b) Discuss the action taken by every phase of compiler for the following statement.
Position:= initial+rate*60.
c) Design NFA by using Thompson’s construction algorithm for regular expression
(a|b)*abb.
d) Construct predictive parsing table for the grammar
S→iEtSeS|iEtS|a, E→ b.
e) Discuss Operator Precedence Parsing algorithm with example.
f) What is ambiguous grammar? identify whether following grammar is ambiguous or
not.
S→ aSbS | bSaS | λ.
Q 2. Answer any four parts of the following. 5x4=20
a) What are the various storage management techniques in symbol table?
b) Draw the syntax tree and DAG for the following expression: (a*b)+(c-d)*(a*b)+b
c) What is activation record? Write the various fields of Activation Record.
d) Classify the errors and discuss the errors in each phase of Compiler.
e) What are basic blocks? Write the algorithm for partitioning into Blocks.
f) What is control and data flow analysis? Explain with example.
Q 3. Answer any two parts of the following. 10x2= 20
a) Show the following grammar
S→Aa|bAc|Bc|bBa , A→d ,B→ d
Is LR(1) but not LALR(1)
b) Write the properties of LR parser with its structure. Also explain the techniques of LR
parser.
c) What is LALR parser? Construct the set of LR(1) items for this grammar: S→ CC, C→
aC , C→d
Q 4. Answer any two parts of the following. 10x2= 20
a) Write quadruples, triples and indirect triples for the expression: -(a*b)+(c+d)-(a+b+c+d)
b) Write the short note on: i. Abstract syntax tree ii. Polish notation iii. Three address code
iv. Backpatching
c) Write the definition of symbol table and procedure to store the names in symbol table.
Q 5. Answer any two parts of the following. 10x2= 20
a) Write the comparison among Static allocation, Stack allocation and Heap Allocation with
their merits and limitations
b) What is code optimization? Explain machine dependent and independent code
optimization.
c) Consider the following program code:
Prod=0;
I=1;
Do{
Prod=prod+a[i]*b[i];
I=i+1;
}while (i<=10);
i. Partition it into blocks
ii. Construct the flow graph

**********
 Sub Code: BCST-503 ROLL NO……………..……………..

ODD SEMESTER EXAMINATION, 2022 – 23

III year B.Tech. – Computer Science & Engineering
rd

Design and Analysis of Algorithms

Duration: 3:00 hrs Max Marks: 100
Note: - Attempt all questions. All Questions carry equal marks. In case of any ambiguity or missing data,
the same may be assumed and state the assumption made in the answer.

Q 1. Answer any four parts of the following. 5x4=20

a) Multiply the following two matrices using Strassen’s Matrix Multiplication
Algorithm.
6 8 2 5
𝐴=[ ] 𝐵=[ ]
9 7 3 6
b) State Master’s Theorem. Find the solution to the following recurrence
equation using master’s theorem.
i) T (n) = 2T (n/2)+ n log n
ii) T (n) = 2nT (n/2) + nn
c) Find the minimum and maximum height of any AVL-tree with 11 nodes.
Assume that height of the root is 0.
d) What are greedy algorithms? What are their characteristics? Explain any
greedy algorithm with example.
e) Define Hamiltonian cycle. Check whether the Hamiltonian cycle exists for
the graph given below.
f) Explain Kruskal’s algorithm to compute the minimum cost spanning tree.
Q 2. Answer any four parts of the following. 5x4=20
a) Give a control abstraction for Divide and Conquer method. Explain with an
example.
b) Explain the Knapsack problem with an example?
c) Show that the following equalities are incorrect with suitable notations
i) 10n2+9 = O(n) ii) n2log n = Ɵ(n2)
d) Using Recursion Tree method, solve. Assume constant time for small values
of n.
T(n)= 2T(n/10)+ T(9n/10)+n
e) What is traveling salesman problem? Implement it for the following matrix.
0 8 16 15
14 0 9 12
7 10 0 6
11 13 10 0
f) Prove that P ⊆ NP.
Q 3. Answer any two parts of the following. 10x2= 20
a) Explain the concept of Backtracking. Explain how 4 Queen problem can be
solved using backtracking. Draw the state space tree corresponding to 4
Queen problem.
b) Write the algorithm for quick sort. Provide a complete analysis of quick sort
for the given set of numbers 12, 33, 23, 43, 44, 55, 64, 77, and 76.
c) Discuss the approximation algorithms for NP-hard problems.
Q 4. Answer any two parts of the following. 10x2= 20
a) Find the optimal solution using branch and bound for the following
assignment problem.
Job 1 Job 2 Job 3 Job 4
A 9 2 7 8
B 6 4 3 7
C 5 8 1 8
D 7 6 9 4
b) Explain how dynamic programming can be used to solve matrix chain
multiplication. Apply the algorithm to multiply the following:
3 Matrices, <M1, M2, M3> with dimensions <(15,3), (3, 10), (10, 2)>
c) Write short notes on.
i) Deterministic Algorithm and Non-Deterministic Algorithm
ii) Ford- Fulkerson method
Q 5. Answer any two parts of the following. 10x2= 20
a) Explain the term ‘polynomial time reduction’. Explain how the clique
problem can be transformed to the vertex cover problem.
b) Construct a red-black tree by inserting the keys 41, 38,31,12,19,8 into an
initially empty tree. Then show the red-black trees that result from the
successive deletion of the keys in the order 8, 12, 1, 41.
c) Differentiate between Kruskal’s and Prim’s algorithm. Apply the greedy
technique to find the minimum spanning tree using Prim’s algorithm for the
given graph.

**********
 Sub Code: BCST 602 ROLL NO……………..……………..

VI SEMESTER EXAMINATION, 2022 – 23

IIIrd year , B.Tech. Computer Science and Engineering Branch
COMPILER DESIGN

Duration: 3:00 hrs Max Marks: 100

Note: - Attempt all questions. All Questions carry equal marks. In case of any ambiguity or missing data,
the same may be assumed and state the assumption made in the answer.

Q 1. Answer any four parts of the following. 5x4=20

a) Construct the regular expression into NFA: (a/b)* a (a/b)
b) Give the comparative analysis of lexical and syntax analysis with suitable
examples.
c) Discuss the role of compiler writing tools. Describe various compiler-writing tools.
d) Explain infix to postfix translation with example through SDT scheme.
e) Construct LR(1) parsing table for given grammar:
S->AA, A->aA/b
f) Write three address code for given expression:
s= (a*-b) + (-b*c)
Also represent that three address code into Quadruples and Triples
Q 2. Answer any four parts of the following. 5x4=20
a) Give the comparison among SLR, CLR, and LALR Parsers in compiler design
b) Explain the importance of loop optimization in code optimization techniques;
explore all loop optimization techniques using suitable examples.
c) Represent the following in flow graph
i=1;sum=0;while (i<=10){sum+=i;i++}
d) What is operator precedence grammar? Compute the operator precedence table for the
given grammar: E-> E+T\T, T-> T+F\F, F-> (E) | id
e) Discuss the various error detection and their recovery techniques in compiler
design.
f) Define Syntax Directed Translation. Construct an annotated parse tree for the expression
(4 * 7 + 1) * 2
Q 3. Answer any two parts of the following. 10x2= 20
a) Consider the following grammar
S-AS|b
A-SA|a.
Construct the SLR parse table for the grammar. Show the actions of the parser for
the input string “abab”.
b) How would you convert the following into intermediate code? Give a suitable
example.
i) Assignment Statements. ii) Case Statements
c) Define a directed acyclic graph. Construct a DAG and write the sequence of
instructions for the expression a+a*(b-c)+(b-c)*d.
Q 4. Answer any two parts of the following. 10x2= 20
a) Explain stack implementation of shift reduce parser.
b) What is intermediate code? Explain different types of intermediate code
 representations. Also, discuss importance of intermediate code.
c) Define the following terms and give suitable example for it.
i) Handle
ii) Handle pruning
iii) Left Factoring
Q 5. Answer any two parts of the following. 10x2= 20
a) What is back patching. Generate three address code for the following
Boolean expression using back patching:
a < b or c > d and e < f
b) Define Symbol table? Explain about the data structures used for symbol table.
c) What is top down parsing? What are the problems in top down parsing? Explain
each with suitable example.

**********
 Sub Code: BCST 503 ROLL NO……………..……………..

Vth SEMESTER EXAMINATION, 2023 – 24

IIIrd Year, B.Tech. – Computer Science & Engg/Information Technology
DESIGN AND ANALYSIS OF ALGORITHMS

Duration: 3:00 hrs Max Marks: 100

Note: - Attempt all questions. All Questions carry equal marks. In case of any ambiguity or missing
data, the same may be assumed and state the assumption made in the answer.

Q 1. Answer any four parts of the following. 5x4=20

a) Differentiate between backtracking & branch and bound technique.
b) Show that vertex cover problem is NP-Complete.
c) Use Prim’s algorithm to find the minimum cost of spanning tree of the following
graph.

d) Give the solution to the m-coloring of a graph using backtracking.

e) Explain Merge sort technique. Discuss the time complexity of merge sort.
f) Explain Strassen’s matrix multiplication and its time complexity.
Q 2. Answer any four parts of the following. 5x4=20
a) Write and explain the Cook’s theorem.
b) How can the output of the Floyd Warshall algorithm be used to detect the
presence of a negative weight cycle?
c) Compare and contrast between connected components and bi connected
components.
d) How 8-Queen’s problem can be solved using back tracking? Explain.
e) Solve the recurrence relation and find the time complexity of T(n)=7T(n/2)+18n2.
f) Explain AND/OR graphs.
Q 3. Answer any two parts of the following. 10x2= 20
a) Discuss in detail about the class P, NP, NP-hard and NP-complete problems. Give
examples for each class.
b) Define Greedy knapsack problem. Find the optimal solution of the Knapsack
instance n=7, M=15, (p1, p2,……,p7) = (10,5,15,7,6,18,3) and (w1,w2,.....,w7)=
(2,3,5,7,1,4,1).
c) Define Job sequencing with deadlines. What is the solution generated by the
function JS when n = 7, (p1, p2, ….., p7) = (3, 5, 20, 18, 1, 6, 30), and (d1, d2, …..,
d7) = (1, 3, 4, 3, 2, 1, 2)?
Q 4. Answer any two parts of the following. 10x2= 20
a) What is dynamic programming? Find the order of parenthesization for the optimal
chain multiplication of the following matrices:
A1 = 15*5 A2 = 5*10 A3 = 10*20 A4 = 20*25
 b) What is difference between Prim’s and Kruskal’s algorithm? How do you
construct a minimum Spanning tree using Kruskal’s algorithm? Explain. List any
two applications.
c) Using the procedure of quick-sort algorithm to sort the following elements:
2,8,7,1,3,5,6,4. Also define the complexity of quick-sort.
Q 5. Answer any two parts of the following. 10x2= 20
a) Apply branch and bound method to solve travelling salesman problem for the
graph whose cost matrix given below:
∞ 7 3 12 8
3 ∞ 6 14 9
Cost matrix = 5 8 ∞ 6 18
9 3 5 ∞ 11
18 14 9 8 ∞
b) Explain how solution will be provided for all pairs shortest path problem using
dynamic programming.
c) What is randomized algorithm? Write advantage and disadvantage of randomized
algorithm. Also explain the types of randomized algorithm.

**********