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

Q1 Answer the following questions: Short answer type (2 X 10)

a) What are recursive algorithms? Explain with a simple example.

Ans: Recursive algorithm is a method of simplification that divides the problem into sub-problems of the same nature and then use the solution to that sub-problems to solve the original problem

Example: Factorial Calclation

As we know that,

n! = n × n-1 × n-2 × n-3 × … × 3 × 2 × 1

and 0! = 1

So, finding of factorial can be solved using recursive algorithm approach as follow:

int fact ( int n ) {
 if ( n == 0 )
      return 1; // base case
 return n * fact(n-1); // recursive step
}

So here we are trying to compute the factorial of a number n,  to compute n!, we first try to compute (n-1)! which will again try to compute (n-2)! and so on.  Sure, the numbers are getting smaller which is a smaller sub-problem of the same nature and finally factorial of the numbers we get.

b) Define Optimal Substructure Problem.

Ans: A problem has an optimal substructure if its optimal solution can be constructed from the optimal solutions of its sub-problems.

For example, the Shortest Path problem has following optimal substructure property:
If a node x lies in the shortest path from a source node u to destination node v then the shortest path from u to v is combination of shortest path from u to x and shortest path from x to v.

c) Differentiate between Greedy Algorithm and Dynamic Programming.

Ans:

Dynamic ProgrammingGreedy Algorithm
1. Dynamic Programming is used to obtain the optimal solution1. Greedy Method is also used to get the optimal solution.
2. In Dynamic Programming, we choose at each step, but the choice may depend on the solution to sub-problems.2. In a greedy Algorithm, we make whatever choice seems best at the moment and then solve the sub-problems arising after the choice is made.
3. Less efficient as compared to a greedy approach3. More efficient as compared to a greedy approach
4. Example: 0/1 Knapsack4. Example: Fractional Knapsack
5. It is guaranteed that Dynamic Programming will generate an optimal solution using Principle of Optimality.5. In Greedy Method, there is no such guarantee of getting Optimal Solution

d) What is minimum Cost Spanning Tree?

Ans: The cost of the spanning tree is the sum of the weights of all the edges in the tree. There can be many spanning trees. Minimum spanning tree is the spanning tree where the cost is minimum among all the spanning trees. There also can be many minimum spanning trees.

e) What is your idea behind Topological Sorting?

Ans: The topological sorting algorithm is basically linear ordering of the vertices of the graph in a way that for every edge ab from vertex a to b, the vertex a comes before the vertex b in the topological ordering. In other words, the topological sorting of a Directed Acyclic Graph is linear ordering of all of its vertices.

Topological Sort is also sometimes known as Topological Ordering. The topological sorting is possible only if the graph does not have any directed cycle. In other words, a topological ordering is possible only in acyclic graphs.

f) Describe potential method of amortized analysis?

Ans:

The potential method (also called the physicist’s method) works by assigning a potential function to the data structure and factoring in changes to that potential to the overall runtime

g) What is the notion behind divide and conquer method?

Ans: Divide-and-conquer is a technique to solve a problem which breaks a problem into subproblems that are similar to the original problem, recursively solves the subproblems, and finally combines the solutions to the subproblems to solve the original problem. 

Divide-and-conquer algorithm having three parts:

  1. Divide the problem into a number of sub-problems that are smaller instances of the same problem
  2. Conquer the sub-problems by solving them recursively. If they are small enough, solve the sub-problems as base cases.
  3. Combine the solutions to the sub-problems into the solution for the original problem.

h) Write a note on multistage graph problem

Ans: Multistage graph problem

  1. The multistage graph problem is to find a minimum cost from a source to a sink.
  2. A multistage graph is a directed graph having a number of multiple stages, where stages element should be connected consecutively.
  3. In this multiple stage graph, there is a vertex whose in degree is 0 that is known as the source. And the vertex with only one out degree is 0 is known as the destination vertex.
  4. The one end of the multiple stage graphs is at i thus the other reaching end is on i+1 stage.
  5. If we denote a graph G = (V, E) in which the vertices are partitioned into K >= 2 disjoints sets, Vi1 <= I <=K. So that, if there is an edge < u, v > from u to v in E, the u £Vi and v € v (i+1), for some I1 <= i <= K. And sets V1 and Vk are such that |V1| = |Vk| = 1.

i) Explain the control abstraction for back tracking technique.

Ans:

j) Differentiate between Deterministic and non-deterministic algorithm.

Ans:

Deterministic AlgorithmNon-deterministic Algorithm
1. The algorithms in which the result of every algorithm is uniquely defined are known as the Deterministic Algorithm.1. On other hand, the algorithms in which the result of every algorithm is not uniquely defined and result could be random are known as the Non-Deterministic Algorithm.
2. In Deterministic Algorithms execution, the target machine executes the same instruction and results same outcome which is not dependent on the way or process in which instruction get executed.2. On other hand in case of Non-Deterministic Algorithms, the machine executing each operation is allowed to choose any one of these outcomes subjects to a determination condition to be defined later
3. On the basis of execution and outcome in case of Deterministic algorithm, they are also classified as reliable algorithms as for a particular input instructions the machine will give always the same output.3. On other hand Non deterministic algorithm are classified as non-reliable algorithms for a particular input the machine will give different output on different executions.
4. As outcome is known and is consistent on different executions so Deterministic algorithm takes polynomial time for their execution.4. On other hand as outcome is not known and is non-consistent on different executions so Non-Deterministic algorithm could not get executed in polynomial time.
5. In deterministic algorithm the path of execution for algorithm is same in every execution.5. On other hand in case of Non-Deterministic algorithm the path of execution is not same for algorithm in every execution and could take any random path for its execution.

Q2 Answer the following questions:

a) The number of distinct minimum spanning trees for the weighted graph below is _____.

Ans : 6

b) Let A be a square matrix of size n x n. Consider the following program. What is the expected output?

C = 100
for i = 1 to n do
    for j = 1 to n do
    {
        Temp = A[i][j] + C
        A[i][j] = A[j][i]
        A[j][i] = Temp - C
    }
for i = 1 to n do
    for j = 1 to n do
        Output(A[i][j]);

Ans: The matrix A itself

c) The minimum number of comparisons required finding the minimum and the maximum of 100 numbers is __________________.

Ans: 148

d) A certain problem can be solved by an algorithm whose running time is in O(nlog2n) which of the following assertions is true?

a. The problem is tractable.

b. The problem is intractable.

c. Impossible to tell.

Ans : Impossible to tell

e) Suppose we run Dijkstra’s single source shortest-path algorithm on the following edge weighted directed graph with vertex P as the source. In what order do the nodes get included into the set of vertices for which the shortest path distances are finalized?

i) P, Q, R, S, T U

ii) P, Q, R, U, S, T

iii) P, Q, R, U, T, S

iv) P, Q, T, R, U, S

Ans: P, Q, R, U, S, T

f) The __________________ of an algorithm is the amount of computer time it needs to run to completion.

Ans: Time complexity

g) In the weighting rule of UNION(i,j), the height of tree is not greater than ______________________.

Ans:

h) The time complexity for Strassen’s matrix multiplication is __________________.

Ans: O(n3)

i) Krushkal’s algorithm takes a total time of __________________.

Ans: O(elog e) where e is the number of edges

j) Given a function to compute on ‘n’ inputs, the ______________ strategy suggests splitting the inputs into ‘k’ distinct subsets.

Ans: Divide and conquer