Design and Analysis of Algorithm 2016-17 Previous Year Paper Solution
Long Questions

Q3 a) Suppose we wish to create a binary heap containing the keys D A T A S T R U C T U R E (All comparisons use alphabetical order.)

Create a minimum heap tree using these keys. Analyse the time complexity. [Marks: 5]

Ans:

b) Solve the following recurrence relations.

i) T(n) = 2T(n/2)+nlogn

ii) T(n) = 2T(n/3) + T(2n/3) + Cn [Marks: 10]

Q4 a) Explain merge sort algorithm and find the complexity of the algorithm. [Marks: 8]

Ans: Merge sort is one of the most efficient sorting algorithms. It works on the principle of Divide and Conquer. Merge sort repeatedly breaks down a list into several sub-lists until each sub-list consists of a single element and merging those sub-lists in a manner that results into a sorted list.

Algorithm Steps:

  1. Divide the unsorted list into N sub-lists, each containing single element.
  2. Take adjacent pairs of two singleton lists and merge them to form a list of 2 elements. It will have N/2 lists of size 2. While comparing two sub-lists for merging, the first element of both lists is taken into consideration. If sorting in ascending order, the element that is of a lesser value becomes a new element of the sorted list. 
  3. Repeat the process till a single sorted list is obtained.

Let us consider the below example:

Merge Sorting

b) Explain the algorithm for finding maximum and minimum and analyze its time complexity. [Marks: 7]

Ans:

Q5 a) Explain Prim’s algorithm and its complexities. Analyze it with an example. [Marks:5]

Ans: Prim’s Algorithm is a famous greedy algorithm used to find minimum cost spanning tree of a graph. Prim’s Algorithm Example. Prim’s Algorithm Time Complexity is O(ElogV) using binary heap.

b) Explain how to solve travelling salesman problem by the method of dynamic programming and analyze complexity of the algorithm. [Marks:10]

Ans:

Q6 a) Suppose we use two string matching problems, consisting of a text T and a string P.

Problem 1 is as follows: T = aaabaadaabaaa P = aabaaa

Problem 2 is as follows: T = 000010001010001 P = 000101

Apply the Knuth-Moris-pratt pattern matching algorithm to the first pattern matching problem. [Marks: 8]

Ans:

b) Give the failure function (or prefix function) of the Knuth-Morris-pratt pattern matching algorithm for the pattern P from the first pattern matching [Marks: 7]

Ans:

Q7 a) Prove that any algorithm that works by comparing keys to find the second largest from as set of n keys must do at least n+log n-2 comparisons in the worst case. [Marks:5]

Ans:

b) Consider a version of the knapsack problem in which each object has a weight and a profit, and a specified knapsack capacity. Each object can be taken 0 and 1 time. Will any of the following (greedy) algorithms always produce an optimal solution? In each case, an order of the objects is specified. The algorithm includes the objects one at a time in that order and skips over the objects that will cause the weight of the knapsack to exceed the capacity. Prove or give c counter example:

(a) increasing order of weight.

(b) decreasing order of profit.

(c) decreasing order of profit to weight ratio [Marks: 10]

Ans: