CS2251 -DESIGN AND ANALYSIS OF ALGORITHMS UNIT III QUESTIONS

UNIT III

1)Define Dynamic Programming

Dynamic programming is a technique for solving problems with overlapping problems. Typically, these subproblems arise from a recurrence relating a solution to a given problem with solutions to its smaller subproblems of the same type. Rather than solving overlapping subproblems again and again, dynamic programming suggests solving each of the smaller sub problems only once and recording the results in a table from which we can then obtain a solution to the original problem.

2) Define Binomial Coefficient

                                                                                         n

The Binomial Coefficient, denoted C(n,k) or   k     is the number of Combinations(subsets) of k elements from an n-element set(0<k<n). The name "binomial coefficients" comes from the participation of these numbers in the so called binomial formula

(a+b)ⁿ =(n,0)aⁿ+..........+C(n,i)a^n-ibⁱ+.......+C(n,n)bⁿ

3) Define Transitive closure

The transitive closure of a directed graph with n vertices can be defined as the n by n Boolean matrix T = {ti,}, in which the element in the i^th row (1<i<n) and the j^th column (l<j<n) is 1 if there exists a non trivial directed path from the i^th vertex to j^th vertex ; otherwise , t_ij is 0.

4) Explain Warshalls algorithm

Warshall's algorithm constructs the transitive closure of a given digraph with n vertices through a series of n by n Boolean matrices  R⁽⁰⁾, ………, R^(k-l)R^(k),…….., R⁽ⁿ⁾

Each of these matrices provides certain information about directed paths in the digraph.

4) Explain All-pair shortest-paths problem

Given a weighted connected graph (undirected or directed), the all pairs shortest paths problem asks to find the distances(the lengths of the shortest path) from each vertex to all other vertices.

5) Explain Floyd's algorithm

It is convenient to record the lengths of shortest paths in an n by n matrix D called the distance matrix: the element d_ij in the i^th row and the jth column of this matrix indicates the length of the shortest path from the i^th vertex to the j^th vertex . We can generate the distance matrix with an algorithm that is very similar to warshall's algorithm. It is called Floyd's algorithm.

6) What does Floyd’s algorithm do?

It is used to find the distances (the lengths of the shortest paths) from each vertex to all other vertices of a weighted connected graph.

7) Explain principle of Optimality

It says that an optimal solution to any instance of an optimization problem is composed of optimal solutions to its subinstances.

8) Explain Optimal Binary Search Trees

One of the principal application of Binary Search Tree is to implement the operation of searching. If probabilities of searching for elements of a set are known, it is natural to pose a question about an optimal binary search tree for which the average number of comparisons in a search is the smallest possible.

9) Explain Knapsack problem

Given n items of known weights w₁,w₂...........w_n and values v₁,v₂............v_n and a knapsack of capacity W, find the most valuable subset of the items that fit into the knapsack.(Assuming all the weights and the knapsack's capacity are positive integers the item values do not have to be integers.)

10) Explain the Memory Function technique

The Memory Function technique seeks to combine strengths of the  top down and bottom-up approaches to solving problems with overlapping subproblems. It does this by solving, in the top-down fashion but only once, just necessary sub problems of a given problem and recording their solutions in a table.

11) Explain ²Traveling salesman problem”?

                A salesman has to travel n cities starting from any one of the cities and visit the remaining cities exactly once and come back to the city where he started his journey in such a manner that either the distance is minimum or cost is minimum.         This is known as traveling salesman problem.