DESIGN AND ANALYSIS OF ALGORITHM QUESTION BANK
Algorithm design is a specific method to create a mathematical process in problem solving processes. ... In computer science, the analysis of algorithms is the determination of the of the computational complexity of algorithms, that is the amount of time, storage and/or other resources necessary to execute them.
Link for the algorithm :
Below are the few QA on design and analysis. At the bottom of this page, Links are provided for various algorithm used to optimize/find solution.
UNIT – I
PART-A
1. What is performance measurement?
Performance measurement is concerned with obtaining the space and the time requirements of a particular algorithm.
2. What is an algorithm?
An algorithm is a finite set of instructions that, if followed, accomplishes a particular task.
3. What are the characteristics of an algorithm?
1) Input
2) Output
3) Definiteness
4) Finiteness
5) Effectiveness
4. Define Program.
A program is the expression of an algorithm in a programming language. Sometimes works such as procedure, function and subroutine are used synonymously program.
5. Write the For LOOP general format.
The general form of a for Loop is
For variable : = value 1 to value 2 step
Step do
{
<statement 1>
<statement n >
}
6. What is recursive algorithm?
An algorithm is said to be recursive if the same algorithm is invoked in the body. An algorithm that calls itself is Direct recursive. Algorithm A is said to be indeed recursive if it calls another algorithm, which in turn calls A.
7. What is space complexity?
The space complexity of an algorithm is the amount of memory it needs to run to completion.
8. What is time complexity?
The time complexity of an algorithm is the amount of computer time it needs to run to completion.
9. Give the two major phases of performance evaluation
Performance evaluation can be loosely divided into two major phases:
• a prior estimates (performance analysis)
• a Posterior testing(performance measurement)
10. Define input size.
The input size of any instance of a problem is defined to be the number of words(or the number of elements) needed to describe that instance.
11. Define best-case step count.
The best-case step count is the minimum number of steps that can be executed for the given parameters.
12. Define worst-case step count.
The worst-case step count is the maximum number of steps that can be executed for the given parameters.
13. Define average step count.
The average step count is the average number of steps executed instances with the given parameters.
14. Define the asymptotic notation “Big on” (0)
The function f(n) = O(g(n)) iff there exist positive constants C and no such that f(n)£ C * g(n) for all n, n ³n0.
15. Define the asymptotic notation “Omega” ( W ).
The function f(n) =W (g(n)) iff there exist positive constant C and no such that f(n) C * g(n) for all n, n ³ n0.
16. Define the asymptotic t\notation “theta” (q )
The function f(n) =q (g(n)) iff there exist positive constant C1, C2, and no such that C1 g(n)£ f(n) £ C2 g(n) for all n, n ³ n0.
17. Define Little “oh”.
The function f(n) = 0(g(n))
Iff Lim f(n) = 0
n - μ g(n)
18. Define Little Omega.
The function f(n) = w (g(n))
iff
Lim f(n) = 0
n - μ g(n)
19. Write algorithm using iterative function to fine sum of n numbers.
Algorithm sum(a,n)
{
S : = 0.0
For i=1 to n do
S : - S + a[i];
Return S;
}
20. Write an algorithm using Recursive function to fine sum of n numbers.
Algorithm Rsum (a,n)
{
If(n_ 0) then
Return 0.0;
Else Return Rsum(a, n- 1) + a(n);
}
21. What are the basic asymptotic efficiency classes?
The various basic efficiency classes are
Constant:1
Logarithmic: log n
Linear: n
N-log-n: n log n
Quadratic: n2
Cubic: n3
Exponential:2n
Factorial:n!
22. Define Time Space Tradeoff.
Time and space complexity can be reduced only to certain levels, as later on reduction of time increases the space and vice-versa. This is known as Time-space trade-off.
23. Why do we need algorithm analysis?
• Writing a working program is not good enough.
• The program may be in-efficient
• If the program is run on a large data set, then the running time becomes an issue.
24. List the factors which affects the running time of the algorithm.
1. Computer
2. Compiler
3. Algorithm used
4. Input to the algorithm
5. The content of the input affects the running time
6. Typically, the input size is the main consideration.
25. What is recurrence equation?
A recurrence equation is an equation or inequality that describes a function in terms of its value on smaller inputs.
26. What is classification of the recurrence equation?
Recurrence Equations can be classified into
1. Homogeneous
2. Inhomogeneous
PART-B
1. Explain about designing and analyzing an algorithm. Page no – 1.2 to 1.52
2. Explain in detail about analysis frame work. Page no – 1.7 to 1.9
3. Explain about how can you compute space and time complexity of an algorithm
(Or)
Explain about performance of a program. Page no – 1.9 to 1.17
4. Explain about input enhancement with example. Page no – 1.17 to 1.20
5. Explain about pre structuring with an example. Page no – 1.17 to 1.18, 1.20 to1.22
6. Explain about asymptotic notations. Page no – 1.22 to 1.27
7. Explain about conditional asymptotic notations Page no – 1.28 to 1.29
8. Explain about the methods that solves recurrence equations Page no – 1.31 to 1.34
UNIT II
1. Define the divide and conquer method.
Given a function to compute on ‘n’ inputs the divide-and-comquer strategy suggests splitting the inputs in to’k’ distinct susbsets, 1<k <n, yielding ‘k’ sub problems. The sub problems must be solved, and then a method must be foundtocombine sub solutions into a solution of the whole. If the sub problems are still relatively large, then the divide-and conquer strategy can possibly be reapplied.
2. Define control abstraction.
A control abstraction we mean a procedure whose flow of control is clear but whose primary operations are by other procedures whose precise meanings are left undefined.
3. Write the Control abstraction for Divide-and conquer.
Algorithm D And(r)
{
if small(p) then return S(r);
else
{
divide P into smaller instance _ 1, _ 2, _ k, k ³ 1;
Apply D and C to each of these sub problems
Return combine (DAnd C(_1) DAnd C(_2),----, DAnd ((_k));
}}
4. What is the substitution method?
One of the methods for solving any such recurrence relation is called the substitution method.
5. What is the binary search?
If ‘q’ is always chosen such that ‘aq’ is the middle element(that is, q=[(n+1)/2), then the resulting search algorithm is known as binary search.
6. Give computing time for Binary search?
The computing time of binary search by giving formulas that describe the best, average and worst cases. Successful searches q(1) q(logn) q(Logn) best average worst unsuccessful searches q(logn) best, average, worst
7. Define external path length?
The external path length E, is defines analogously as sum of the distance of all external nodes from the root.
8. Define internal path length.
The internal path length ‘I’ is the sum of the distances of all internal nodes from the root
9. What is the maximum and minimum problem?
The problem is to find the maximum and minimum items in a set of ‘n’ elements. Though this problem may look so simple as to be contrived, it allows us to demonstrate divide and conquer in simple setting.
10. What is the Quick sort?
N quick sort, the division into sub arrays is made so that the sorted sub arrays do not need to be merged later.
11. Write the Analysis for the Quick sot.
In analyzing QUICKSORT, we can only make the number of element comparisons c(n). It is easy to see that the frequency count of other operations is of the same order as C(n).
12. Is insertion sort better than the merge sort?
Insertion sort works exceedingly fast on arrays of less then 16 elements, though for large ‘n’ its computing time is O(n2).
13. Write a algorithm for straightforward maximum and minimum>
Algorithm straight MaxMin(a,n,max,min)
//set max to the maximum and min to the minimum of a[1:n]
{
max := min: = a[i];
for i = 2 to n do
{
if(a[i] >max) then max: = a[i];
if(a[i] >min) then min: = a[i];
}
}
14. Give the recurrence relation of divide-and-conquer?
The recurrence relation is
T(n) = g(n)
T(n1) + T(n2) + ----+ T(nk) + f(n)
15. 15. Write the algorithm for Iterative binary search?
Algorithm BinSearch(a,n,x)
//Given an array a[1:n] of elements in nondecreasing
// order, n>0, determine whether x is present
{
low : = 1;
high : = n;
while (low < high) do
{
mid : = [(low+high)/2];
if(x < a[mid]) then high:= mid-1;
else if (x >a[mid]) then low:=mid + 1;
else return mid;
}
return 0;
}
16. What are internal nodes?
The circular node is called the internal nodes.
17. Describe the recurrence relation of merge sort?
If the time for the merging operation is proportional to n, then the computing time of merge sort is described by the recurrence relation
n = 1, a a constant
T(n) = a
2T (n/2) + n n >1, c a constant
18. What is meant by feasible solution?
Given n inputs and we are required to form a subset such that it satisfies some given constraints then such a subset is called feasible solution.
19. Write any two characteristics of Greedy Algorithm?
• To solve a problem in an optimal way construct the solution from given set of candidates.
• As the algorithm proceeds, two other sets get accumulated among this one set contains the candidates that have been already considered and chosen while the other set contains the candidates that have been considered but rejected.
20. Define optimal solution?
A feasible solution either maximizes or minimizes the given objective function is called as optimal solution
21. What is Knapsack problem?
A bag or sack is given capacity n and n objects are given. Each object has weight wi and profit pi .Fraction of object is considered as xi (i.e) 0<=xi<=1 .If fraction is 1 then entire object is put into sack. When we place this fraction into the sack we get wixi and pixi.
22. What is the Greedy choice property?
• The first component is greedy choice property (i.e.) a globally optimal solution can arrive at by making a locally optimal choice.
• The choice made by greedy algorithm depends on choices made so far but it cannot depend on any future choices or on solution to the sub problem.
• It progresses in top down fashion.
23. What is greedy method?
Greedy method is the most important design technique, which makes a choice that looks best at that moment. A given ‘n’ inputs are required us to obtain a subset that satisfies some constraints that is the feasible solution. A greedy method suggests that one can device an algorithm that works in stages considering one input at a time.
24. What are the steps required to develop a greedy algorithm?
• Determine the optimal substructure of the problem.
• Develop a recursive solution.
• Prove that at any stage of recursion one of the optimal choices is greedy choice.
• Thus it is always safe to make greedy choice.
• Show that all but one of the sub problems induced by having made the greedy choice are empty.
• Develop a recursive algorithm and convert into iterative algorithm.
25. Write the general algorithm for Greedy method control abstraction.
Algorithm Greedy (a, n)
{
solution=0;
for i=1 to n do
{
x= select(a);
if feasible(solution ,x) then
solution=Union(solution ,x);
}
return solution;
}
26. Define optimal solution for Job sequencing with deadlines.
Feasible solution with maximum profit is optimal solution for Job sequencing with deadlines.
27. Write the difference between the Greedy method and Dynamic programming.
Only one sequence of decision is Many number of decisions are generated. generated1.
• It does not guarantee to give an It definitely gives an optimal solution always. optimal solution always.
PART-B
1. Explain about container loading problem using greedy algorithm. Page no – 2.27 to 2.28
2. Explain about greedy knapsack problem. Page no – 2.29 to 2.30
3. Consider five items along with their respective weights and values
I=<I1, I2,I3, I4,I5>
W=<5,10,20,30,40>
V=<30,20,100,90,160>
And W=60. Find the solution to the fractional knapsack problem Page no – 2.34 to 2.35
4. Analysis the linear search. Page no – 1.36 to 1.37
5. Explain about general divide and conquer algorithm Page no – 2.1 to 2.4
6. Explain about divide and conquer binary search. Page no – 2.4 to 2.8
7. Explain about finding maximum and minimum using divide and conquer Page no – 2.8 to 2.13
8. Explain about divide and conquer merge sort. Page no – 2.13 to 2.18
9. Sort 3, 1, 4, 1, 5, 9, 2, 6 using merge sort. Page no – 2.35
10. Find the key 10, using binary search 5, 10, 15, 20, 25, 30, 35, 40, 45, 50 Page no – 2.37
11. Find the maximum and minimum value from the list 22, 13, -5, -8, 15, 60, 17, 31, 47 Page no – 2.39 to 2.40
UNIT III
1. Define dynamic programming.
Dynamic programming is an algorithm design method that can be used when a solution to the problem is viewed as the result of sequence of decisions.
2. What are the features of dynamic programming?
• Optimal solutions to sub problems are retained so as to avoid recomputing their values.
• Decision sequences containing subsequences that are sub optimal are not considered.
• It definitely gives the optimal solution always.
3. What are the drawbacks of dynamic programming?
• Time and space requirements are high, since storage is needed for all level.
• Optimality should be checked at all levels.
4. Write the general procedure of dynamic programming.
The development of dynamic programming algorithm can be broken into a sequence of 4 steps.
1. Characterize the structure of an optimal solution.
2. Recursively define the value of the optimal solution.
3. Compute the value of an optimal solution in the bottom-up fashion.
4. Construct an optimal solution from the computed information.
5. Define principle of optimality.
It states that an optimal sequence of decisions has the property that whenever the initial stage or decisions must constitute an optimal sequence with regard to stage resulting from the first decision.
6. Give an example of dynamic programming and explain.
An example of dynamic programming is knapsack problem. The solution to the knapsack problem can be viewed as a result of sequence of decisions. We have to decide the value of xi for 1<i<n. First we make a decision on x1 and then on x2 and so on. An optimal sequence of decisions maximizes the object function Spi xi.
7. Write about optimal merge pattern problem.
Two files x1 and x2 containing m & n records could be merged together to obtain one merged file. When more than 2 files are to be merged together. The merge can be accomplished by repeatedly merging the files in pairs. An optimal merge pattern tells which pair of files should be merged at each step. An optimal sequence is a least cost sequence.
8. Explain any one method of finding the shortest path.
One way of finding a shortest path from vertex i to j in a directed graph G is to decide which vertex should be the second, which is the third, which is the fourth, and so on, until vertex j is reached. An optimal sequence of decisions is one that results in a path of least length.
9. Define 0/1 knapsack problem.
The solution to the knapsack problem can be viewed as a result of sequence of decisions. We have to decide the value of xi. xi is restricted to have the value 0 or 1 and by using the function knap(l, j, y) we can represent the problem as maximum Spi xi subject to Swi xi < y where l -iteration, j - number of objects, y – capacity.
10. What is the formula to calculate optimal solution in 0/1 knapsack problem?
The formula to calculate optimal solution is g0(m)=max{g1, g1(m-w1)+p1}.
11. Write about traveling salesperson problem.
Let g = (V, E) be a directed. The tour of G is a directed simple cycle that includes every vertex in V. The cost of a tour is the sum of the cost of the edges on the tour. The traveling salesperson problem to find a tour of minimum cost.
12. Write some applications of traveling salesperson problem.
• Routing a postal van to pick up mail from boxes located at n different sites.
• Using a robot arm to tighten the nuts on some piece of machinery on an assembly line.
• Production environment in which several commodities are manufactured on the same set of machines.
13. Give the time complexity and space complexity of traveling salesperson
problem.
• Time complexity is O (n2 2n).
• Space complexity is O (n 2n).
14. Define flow shop scheduling.
The processing of jobs requires the performance of several distinct job. In flow shop we have n jobs each requiring n tasks i.e. T1i, T2i,…...Tmi, 1<i<n.
15. What are the conditions of flow shop scheduling?
• Let Tji denote jth task of the ith job. Task Tij is to be performed on Pj number of processors where 1<j<m i.e. number of processors will be equal to number of task
• Any task Tji must be assigned to the processor Pj.
• No processor can have more than one task assigned to it at any time. For any job I
• Processing the task for j>1 cannot be started until T(j-i),i has been completed.
16. Define non preemptive schedule.
A non preemptive schedule is a schedule in which the processing of a task on any processor is not terminated until the task is complete.
17. Define preemptive schedule.
A preemptive schedule is a schedule in which the processing of a task on any processor can be terminated before the task is completed.
18. Define finish time
The finish time fi (S) of job i is the time at which all tasks of job i have been completed in schedule S. The finish time F(S) of schedule S is given by F(S)=max{ fi (S)} 1<i<n
19. Define mean flow time
The mean flow time MFT (S) is defined to be]
MFT (S) = 1 Sfi(S)
n 1<i<n
20. Define optimal finish time.
Optimal finish time scheduling for a given set of tasks is a non preemptive schedule S for which F (S) is minimum over all non preemptive schedules S.
21. Define preemptive optimal finish time.
Preemptive optimal finish time scheduling for a given set of tasks is a preemptive schedule S for which F (S) is minimum over all preemptive schedules S.
22. What are the requirements that are needed for performing Backtracking?
To solve any problem using backtracking, it requires that all the solutions satisfy a complex set of constraints. They are:
1. Explicit constraints.
2. Implicit constraints.
23. Define explicit constraint.
They are rules that restrict each xi to take on values only from a give set. They depend on the particular instance I of the problem being solved. All tuples that satisfy the explicit constraints define a possible solution space.
24. Define implicit constraint.
They are rules that determine which of the tuples in the solution space of I satisfy the criteria function. It describes the way in which the xi must relate to each other.
25. Define state space tree.
The tree organization of the solution space is referred to as state space tree.
26. Define state space of the problem.
All the paths from the root of the organization tree to all the nodes is called as state space of the problem
27. Define answer states.
Answer states are those solution states s for which the path from the root to s defines a tuple that is a member of the set of solutions of the problem.
28. What are static trees?
The tree organizations that are independent of the problem instance being solved are called as static tree.
29. What are dynamic trees?
The tree organizations those are independent of the problem instance being solved are called as static tree.
30. Define a live node.
A node which has been generated and all of whose children have not yet been generated is called as a live node.
31. Define a E – node.
E – node (or) node being expanded. Any live node whose children are currently being generated is called as a E – node.
32. Define a dead node.
Dead node is defined as a generated node, which is to be expanded further all of whose children have been generated.
PART-B
1. Explain about multistage graphs. Page no- 3.3 to 3.6
2. Explain about all pair shortest path algorithm. Page no- 3.11 to 3.14
3. Explain about optimal binary search tree. Page no- 3.18 to 3.20
4. Explain about dynamic programming knapsack problem.Page no- 3.24 to 3.26
5. Explain about dynamic programming travelling salesperson problem.Page no- 3.33 to 3.34
6. Find an optimal binary search tree for the key and probabilities given below
key A B C D
Probabilities .1 .2 .4 .3
7. Find the optimal solution for the given knapsack problem.Knapsack Capacity W=5
Item 1 2 3 4
Weight 2 1 3 2
Value $12 $10 $20 $15
8. Find an optimal tour of the given distance matrix
0 10 15 20
D(0)= 5 0 9 10
6 13 0 12
8 8 9 0
UNIT IV
1. What are the factors that influence the efficiency of the backtracking algorithm?
The efficiency of the backtracking algorithm depends on the following four factors. They are:
• The time needed to generate the next xk
• The number of xk satisfying the explicit constraints.
• The time for the bounding functions Bk
• The number of xk satisfying the Bk.
2. Define Branch-and-Bound method.
The term Branch-and-Bound refers to all the state space methods in which all children of the E-node are generated before any other live node can become the E- node.
3. What are the searching techniques that are commonly used in Branch-and-Bound method.
The searching techniques that are commonly used in Branch-and-Bound method are:
i. FIFO
ii. LIFO
iii. LC
iv. Heuristic search
4. State 8 – Queens problem.
The problem is to place eight queens on a 8 x 8 chessboard so that no two queen “attack” that is, so that no two of them are on the same row, column or on the diagonal.
5. State Sum of Subsets problem.
Given n distinct positive numbers usually called as weights , the problem calls for finding all the combinations of these numbers whose sums are m.
6. State m – color ability decision problem.
Let G be a graph and m be a given positive integer. We want to discover whether the nodes of G can be colored in such a way that no two adjacent nodes have the same color yet only m colors are used.
7. Define chromatic number of the graph.
The m – color ability optimization problem asks for the smallest integer m for which the graph G can be colored. This integer is referred to as the chromatic number of the graph.
8. Define a planar graph.
A graph is said to be planar iff it can be drawn in such a way that no two edges cross each other.
9. What are NP- hard and Np-complete problems?
The problems whose solutions have computing times are bounded by polynomials of small degree.
10. What is a decision problem?
Any problem for which the answer is either zero or one is called decision problem.
11. What is maxclique problem?
A maxclique problem is the optimization problem that has to determine the size of a largest clique in Graph G where clique is the maximal sub graph of a graph.
12. What is approximate solution?
A feasible solution with value close to the value of an optimal solution is called approximate solution.
13. Define Graph coloring” problem.
The graph coloring problem asks us to assign the smallest number of colors to vertices of a graph so that no two adjacent vrtices are the same color.
PART-B
1. Explain the 8-Queen’s problem & discuss the possible solutions.
2. Solve the following instance of the knapsack problem by the branch & bound algorithm.
3. Apply backtracking technique to solve the following instance of subset sum problem : S={1,3,4,5} and d=11 (
4. Explain subset sum problem & discuss the possible solution strategies using backtracking.
5. Explain Graph coloring with example.
6. Explain about Knapsack Problem using back tracking with example.
UNIT IV
1 Define tractable and intractable problems
Problems that can be solved in polynomial time are called tractable problems, problems that cannot be solved in polynomial time are called intractable problems.
2 Explain the theory of computational complexity
A problem's intractability remains the same for all principal models of computations and all reasonable input encoding schemes for the problem under consideration.
3 Explain class P problems
Class P is a class of decision problems that can be solved in polynomial time by(deterministic) algorithms. This class of problems is called polynomial.
4 Explain undecidable problems
If the decision problem cannot be solved in polynomial time, and if the decision problems cannot be solved at all by any algorithm. Such problems are called Undecidable.
5 Explain the halting problem
Given a computer program and an input to it,determine whether the program will halt on that input or continue working indefinitely on it.
6 Explain class NP problems
Class NP is the class of decision problems that can be solved by nondeterministic polynomial algorithms.Most decision problems are in NP. First of all, this class includes all the problems in P. This class of problems is called Nondeterministic polynomial.
7 Explain NP-complete problems
A decision problem d is said to be NP-complete if
1) it belongs to class NP
2) every problem in NP is polynomially reducible to D.
8 When a decision problem is said to be polynomially reducible
A decision problem Dl is said to be polynomially reducible to a decision problem D2 if there exists a function t that transforms instances of Dl to instances ofD2 such that
i) t maps all yes instances of d1 to yes instances odf d2 and all no instances of dl to no instances ofd2
ii) t is computable by a polynomial time algorithm
9 Define a Heuristic
A heuristic is a common-sense rule drawn from experience rather than from a mathematically proved assertion.
Ex: Going to the nearest unvisited city in the traveling salesman problem is a good illustration for Heuristic
10 DefineNP-problems
The notion of an NP-hard problem can be defined more formally by extending the notion of polynomial reducability to problems that are not necessary in class NP including optimization problems.
11 What is meant by articulation point?
A vertex v in a connected graph G is an articulation point if and only if the deletion of vertex v together with all edged incident to v disconnects the graph in to two or more nonempty components.
PART-B
1. Give a suitable example & explain the Breadth first search & Depth first search. (16)
2. Explain about biconnected components with example.
3. Briefly explain NP-Hard and NP-Completeness with examples.
4. Explain about 0/1 Knapsack Problem using branch and bound with example.
No comments:
Post a Comment