[This question paper contains 8 printed pages.

Your Roll No...

Sr. No. of Question Paper: 2796 GC-4

Unique Paper Code :32341401

Name of the Paper Design and Analysis of Algorithms

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

Semester IV

Duration: 3 Hours Maximum Marks : 75

nstructions for Candidates

1 Write your Roll No. on the top immediately on receipt of

this question paper.

2. Question No. 1 of 35 marks is compulsory.

3. Attempt any four questions from Q No. 2 to Q. No. 7.

1. (a) Arrange the following functions in the increasing order

of their rate of growth: 22*n, 2n2, n?log(n), n?*n (2)

(b) Consider the ternary search algorithm for searching an

element in a given array: divide the array into three
cqual parts by taking two mid points, viz., left mid and
right mid. If the search element is equal to the left mid,
output left mid; if it is equal to the right mid, output the

P.T.O.
 right mid; if it is smaller than the left mid
id, perform a
recursive search in the leftmost partition; if itt is.
is greato
than the right mid, perform a recursive search in
the
rightmost partition; else pertorm a recursive search
in
the middle partition. Thus, the algorithm performs
comparisons in each iteration and recurses on one-third
of the array. Write the recurrence relation for the running
time of the algorithm and solve it.
(4)
(c) Consider an instance of the subset sum problem
where bound W =
6, Items with weights w,= 2, w, = 2,
W 2.
(4)
With the help of the above example argue that the
memorized recursive algorithm
solves lesser number of
subproblems than the corresponding iterative algorithm.
(d) Consider a linear chain of 3 nodes shown below :
O or
Argue that such a chain cannot form a red-black tree.
For each possible coloring of the three nodes, mention
the property that is violated.
(4)
2796 3
(e) A shopkeeper has W marbles and n empty bottles.
Let C C2 9 Crespectively denote the number of
marbles the botties can contain. The shopkeeper wants
to store the marbies in the bottles.
(i) Describe a greedy algorithm which minimizes the
number of bottles used.
(ii) How would you modify your algorithm if bottle i
also has an associated cost price p; and the
goal is to minimize the total cost of the bottles
used. (3+4)
(1) Suppose an input to the bucket sort algorithm is
not uniformly distributed. Then: (i) will the sort still
give output? (1i) what will be the impact of
correct
relaxing this condition on the running time? Justify.
(3)
(g) Discuss the run time complexity of the naive string
matching algorithm. (2)
(h) Compare the space requirements of adjacency list and
adjacency matrix representations of a graph having n
edges and n vertices. (3)
to find the minimum element
(1) Give an efficient algorithm
running time of the
inmax-heap. Give the
a
exact
algorithm.
(3)
P.T.O.
 () Would you use BFS to find the shortest path .

two nodes in a weighted graph with arbitra tween

rary ge
your answer.
weights ? Justify
(3)
(a) Give an efficient algorithm to check if a given undireets
2
graph has a cycle. Discuss the time complexity of vou.

algorithmn. (5)
(b) For each of the following operations does a Red Black
Tree work faster than a Binary Search Tree? Elaborate
your answer.

1) Search

(i) Postorder traversal

5)

3. (a) A priority queue is implemented in two different ways

using a max heap and an array sorted in decreasing
order of key values (higher key value indicates higher
priority). Compare the time complexity of the following
operations when performed on the two different
implementations of the priority queue.

1) Finding the maximum element

(ii) Deleting the maximum element

a
(6)
111) Increase the priority of certain elemel
 2796 5

(b) Suppose a graph G has two edge-disjoint spanning trees

(two spanning trees that have no edges in common).
Argue that in this graph G, every pair of nodes forms
part of a cycle.
(4)

. (a) Consider the following recursive algorithm to find an

optimal schedule for weighted interval scheduling
problem

Compute_opt0)
If j = 0 then

Return 0

Else

Return max(v, + Compute_opt(pG)), Compute_opt(j-1)

(i) Explain why does this algorithm take exponential

time to run in the worst case.

ii) What changes should be made to the above

algorithm to make it run in polynomial time.
(6)

array A consists of
1's and 0's
(6) Suppose that an n x n

such that in any row of A all the 1's come before any
counting
O's in that row. Give an O(nlgn) algorithm for
(4)
the number of ' s in A.
 5. (a) Give an example graph having four nodes that does not
have a topological ordering. (3)
(b) Suppose a large array is maintained with the following
policy: the list is initially sorted. When new elements are
added, they are inserted at the end of the array and
counted. Whenever the number of new elements reaches
10, the array is resorted and the counter is cleared.
What strategy would be good to use for the resorting of
the array? Why ? (4)
(c) We use Randomized-Select to select the minimum
element of the array A =
<3, 2, 9, 0, 7>. Describe a
sequence of partitions that would result in the worst
case performance of the algorithm. (3)
6. (a) Which red-black tree properties may be violated when a
node is deleted ?
(2)
(b) Will Dijkstra's algorithm still give shortest path between
two vertices if the edge
weights are allowed to be
negative. If yes,
justify your answer with an argument.
If no give an
example. (4)
(c) An instructor has
given a test to her class of n students
The maximum marks for the test is 100. The instructor
 2796 7
t decided not to give fractional marks while grading the
test. The instructor wishes to sort the n
integer scores
in descending order. Design a linear time algorithm to
perform this task. Also list all assumptions (if any) that
you make to solve the problem. (4)
7. (a) Consider a k bit binary counter implemented using an
array A such that A[0] stores the lowest order bit and
A[k-1] stores the highest order bit. The only operation
that can be
performed on the counter is "increment'
Using the aggregate method of analysis, determine the
amortised cost per increment operation when a sequence
of n increments is performed. (3)
(b) A certain input to the merge sort algorithm is such that
the merging step always depicts the worst case behaviour.
Determine the running time of the merge sort algorithm
for this instance. 3)
(c) Consider the following algorithm that takes as input
an array of n integers and an integer T. It finds
whether there exist two elements in the array that
sum
sum up
up to T and returns 1 on success and 0 on
failure. (4)
2796 8

TargetSum (A, n, T)

Heapsort (A, 1, n)
for i = 1 to n

flag BinarySearch(A, i+1, n, |T-A[i]|)

if (flag)

return 1

endif

endfor
return 0

TargetSum uses the following algorithms:

Heapsort (Array, First, Last)
BinarySearch(Array, First, last, element)
Analyze the worst case running time of Target Sum.