pages.

J
8 printed
[This question paper contains

Roll No.220155o06O
Your
H
Sr. No. of Question
Paper : 4057

Unique Paper Code : 2342012401

and Analysis of
Name of the Paper : Design
Algorithms

Name of the Course : B.Sc. (H) Computer Science

Semester : IV

Duration:3 Hours Maximum Marks : 90

Instructions for Candidates

1. Write your Roll No. on the

top immediately on
receipt
of this question paper.

2. The paper hastwo sections.

Section A is
Each question is of 5 marks. compulsory.

3. Attempt any four

questions from
Section B. Each
question is of 15 marks.
 4057 2
3
Section - A 4057 the product
to compute
algorithm (5)
Strassen's
Ne)Use
( Arrange the following sorting
techniques in of the following
matrices
:

increasing order of the number the

of
4
that

17,
they wouldi

3, 9, 12, 11}.
do in

Justify your answer.

order to
comparisons
sort the
data :
Insertion' sort,
Merge sort,
Improved Bubble on a
Sort is performed
n operations
)A sequence of costs i if i is
an
(5) The ith operation
data structure. Use aggregate
() What is
exact power
of 2, and 1 otherwise.
cost per
(5) the amortized
determine
analysis to (5)
() greedy-choice property?
operation.

(ii) optimal substructure

property?
Section- B Ay
)Write the recurrence equation for solving 0-L
knapsack problem using problem be solved optimally
dynamic programming. 2X (a) Can 0-1 knapsack
How is memoization technique used in solving the using greedy strategy? Justify your answer. (7)
problem? (5)

(b)*Suppose Y s,X. If X can be solved in polynomial

\(d) Consider a directed graph G with one component. time, then Y can be solved in polynomial time."

Can a vertex u of G end up in a depth-first tree

Based on the above statement, which of the
containing only u, even thoughu has both incoming
following statements are
and out-going edges in G? Justify your answer correct? If any statement
is incorrect, write its
(5) correct version.
with an example. (8)
4057 4 5 last,
first,
Index
(i) If Y cannot be
4057 A, Index
solved in
polynomial search(Array
then X
cannot be ternary_
solved in time,
t)
polynomial time. Element
3 equal parts.
(ii) Y is at least as into
divided that
hard as X. Array A is
the elements
of
be the index
(iii) If X Let p and q
belongs to NP, then X is that p <
q
such
problem. NP-complete divide A
p
(8)
if t = A[p]return p-1, t).
first,
ternary search(A,
What is an in-place sorting t < A[p]then
else if
algorithm? Is heap
sort an in-place = A[q] return q
sorting algo-rithm? Sort the else if t

following t).
data using heap sort. p+l, q-1,
else if t
< A[g] then ternary_search(A,
4, 3, 7, 1, 8, 5, 9
(7) q+1, last, t)
else ternary_search(A,

(b)Suppose there exists an O(n) time algorithm to equation for computing the
Write a recurrence
of the above algorithm and
find the 5th smallest element in an array of size n. Justify
time complexity
Sort the following data using quick sort assuming the equation obtained by you and also solve it.

5th smallest element as the pivot.

(b) An implementation of radix sort uses heap sort

7, 3, 5, 1, 2, 4, 6
instead of count sort as the intermediate sorting
the time complexity of the
Also, determine technique. Is radix sort still stable? Justify your
(8)
answer with an example.
algorithm. (8)

algorithm for finding an (a) For the given directed

(a)Consider the following acyclic graph, determine
(7)
A of size n: the topological
element t in a sorted array ordering.
(7)
 4057
4057
()c(e)'
(i) 1 - c(e)

Justify your answer.

write an algorithm to

a set of n numbers,
(a) Given
74 element using
find the maximum and minimum
the
strategy. AIso, determine
divide and conquer
(7)
time complexity.
5) Write an efficient algorithm to check
if a given
undirected graph has a cycle. Discuss the time (b) Consider a of the university with 60
department

complexity of your algorithm. teachers and 20 courses. The 8 administration

(8)
maintains the records such that each
department

record contains the name of a teacher and the

6. (ay Solve the subset sum problem using dynamic course he/she is teaching. A teacher name can be
programming for the set {4, 2, 9, 6} and intended maximum 32 characters long and courses are
sum 17. (7)
coded as BCS101, MCS101, MCA101, etc. Each
teacher may be teaching more than one course
(b)Let T be the Minimum Spanning Tree (MST)
with
and one course may be taught by more than one
C corresponding
to a graph G(V, E). Suppose teacher. Give a linear time algorithm
cost to sort the
edge cost for an teachers course
deno tes the non-negative wise, in alphabetical
c(e) order.
following cases, Courses should also
edge e in E. In each of the be reported in chronological
if the edge order. For
indicate whether T andCwill change example, the sorted records
must look
(8)
are replaced with :
like the
following : (8)
costs
057 8
BCS101 SNEHA
BCS101 SWAPNIL

BCS102 ANIL
BCS102 BEENA
BCS102 SNEHA

MCA101 AJAY
MCA101 AMARJEET

and, so on