##### Short Questions

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:

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:

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