08-09-2016, 02:19 PM
[attachment=70750]
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. In addition, all algorithms must satisfy the following criteria:
1) input
2) Output
3) Definiteness
4) Finiteness
5) Effectiveness.
3. 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.
4. 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
}
5. 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.
6. What is space complexity?
The space complexity of an algorithm is the amount of memory it needs to run to completion.
7. What is time complexity?
The time complexity of an algorithm is the amount of computer time it needs to run to completion.
8. Give the two major phases of performance evaluation
Performance evaluation can be loosely divided into two major phases:
(i) a prior estimates (performance analysis)
(ii) a Posterior testing(performance measurement)
10. Define best-case step count.
The best-case step count is the minimum number of steps that can be executed for the given parameters.
11. Define worst-case step count.
The worst-case step count is the maximum number of steps that can be executed for the given parameters.
12. Define average step count.
The average step count is the average number of steps executed an instances with the given parameters.
13. 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.
14. Define the asymptotic notation “Omega” ( Ω ).
The function f(n) =Ω (g(n)) iff there exist positive constant C and no such that f(n) C * g(n) for all n, n ≥ n0.
15. Define the asymptotic t\notation “theta” (θ )
The function f(n) =θ (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.
16. Define Little “oh”.
The function f(n) = 0(g(n))
iff
Lim f(n) = 0 n
- ∝ g(n)
17. Define Little Omega.
The function f(n) = ω (g(n))
iff
Lim f(n) = 0 n - ∝ g(n)
18. 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;
}
19. 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);
20. 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‟ subproblems. The subproblems must be solved, and then a method must be found to combine subsolutions into a solution of the whole. If the subproblems are still relatively large, then the divide-and conquer strategy can possibly be reapplied.
21. 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.
22. Write the Control abstraction for Divide-and conquer.
Algorithm DAnd(ρ)
{
if small(p) then return S(ρ); else
{
divide P into smaller instance ρ 1, ρ 2, ρ k, k ≥ 1; Apply D and C to each of these
subproblems
Return combine (DAnd C(ρ1) DAnd C(ρ2),----, DAnd ((ρk));
}
}
23. What is the substitution method?
One of the methods for solving any such recurrence relation is called the substitution method.
24. 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.
25. Give computing time for Binary search?
In conclusion we are now able completely describe the computing time of binary search by giving formulas that describe the best, average and worst cases.
Successful searches
θ(1) θ(logn) θ(Logn) best average worst
unsuccessful searches θ(logn)
best, average, worst
28. 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-comquer in simple setting.
29. What is the Quick sort?
n quicksort, the division into subarrays is made so that the sorted subarrays do not need to be merged later.
30. Write the Anlysis for the Quick sot.
In analyzing QUICKSORT, we can only make the number of element comparisions c(n). It is easy to see that the frequency count of other operations is of the same order as C(n).
31. 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).
32. 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]; }
33. Give the recurrence relation of divide-and-conquer?
The recurrence relation is
T(n) = g(n)
T(n1) + T(n2) + ----+ T(nk) + f(n)
34. 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;
}
36. Describe the recurrence relation ofr 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
37.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.
38. 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.
39. Define optimal solution?
A feasible solution either maximizes or minimizes the given objective function is called as optimal solution
40. 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.
43. 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.
45. 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.
48. Define forest.
Collection of sub trees that are obtained when root node is eliminated is known as forest
.49. .What does Job sequencing with deadlines mean?
* Given a set of „n‟ jobs each job „i‟ has a deadline di such that di>=0 and a profit pi such that pi>=0.
* For job „i‟ profit pi is earned iff it is completed within deadline.
* Processing the job on the machine is for 1unit of time. Only one machine is available.
50. Define post order traversal.
The order in which the TVSP visits the nodes of the tree is called the post order traversal.
53. When is a task said to be late in a schedule?
A task is said to be late in any schedule if it finishes after its deadline else a task is early in a schedule.
56. 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;
}
57. . Define optimal solution for Job sequencing with deadlines.
Feasible solution with maximum profit is optimal solution for Job sequencing with deadlines.
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. In addition, all algorithms must satisfy the following criteria:
1) input
2) Output
3) Definiteness
4) Finiteness
5) Effectiveness.
3. 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.
4. 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
}
5. 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.
6. What is space complexity?
The space complexity of an algorithm is the amount of memory it needs to run to completion.
7. What is time complexity?
The time complexity of an algorithm is the amount of computer time it needs to run to completion.
8. Give the two major phases of performance evaluation
Performance evaluation can be loosely divided into two major phases:
(i) a prior estimates (performance analysis)
(ii) a Posterior testing(performance measurement)
10. Define best-case step count.
The best-case step count is the minimum number of steps that can be executed for the given parameters.
11. Define worst-case step count.
The worst-case step count is the maximum number of steps that can be executed for the given parameters.
12. Define average step count.
The average step count is the average number of steps executed an instances with the given parameters.
13. 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.
14. Define the asymptotic notation “Omega” ( Ω ).
The function f(n) =Ω (g(n)) iff there exist positive constant C and no such that f(n) C * g(n) for all n, n ≥ n0.
15. Define the asymptotic t\notation “theta” (θ )
The function f(n) =θ (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.
16. Define Little “oh”.
The function f(n) = 0(g(n))
iff
Lim f(n) = 0 n
- ∝ g(n)
17. Define Little Omega.
The function f(n) = ω (g(n))
iff
Lim f(n) = 0 n - ∝ g(n)
18. 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;
}
19. 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);
20. 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‟ subproblems. The subproblems must be solved, and then a method must be found to combine subsolutions into a solution of the whole. If the subproblems are still relatively large, then the divide-and conquer strategy can possibly be reapplied.
21. 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.
22. Write the Control abstraction for Divide-and conquer.
Algorithm DAnd(ρ)
{
if small(p) then return S(ρ); else
{
divide P into smaller instance ρ 1, ρ 2, ρ k, k ≥ 1; Apply D and C to each of these
subproblems
Return combine (DAnd C(ρ1) DAnd C(ρ2),----, DAnd ((ρk));
}
}
23. What is the substitution method?
One of the methods for solving any such recurrence relation is called the substitution method.
24. 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.
25. Give computing time for Binary search?
In conclusion we are now able completely describe the computing time of binary search by giving formulas that describe the best, average and worst cases.
Successful searches
θ(1) θ(logn) θ(Logn) best average worst
unsuccessful searches θ(logn)
best, average, worst
28. 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-comquer in simple setting.
29. What is the Quick sort?
n quicksort, the division into subarrays is made so that the sorted subarrays do not need to be merged later.
30. Write the Anlysis for the Quick sot.
In analyzing QUICKSORT, we can only make the number of element comparisions c(n). It is easy to see that the frequency count of other operations is of the same order as C(n).
31. 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).
32. 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]; }
33. Give the recurrence relation of divide-and-conquer?
The recurrence relation is
T(n) = g(n)
T(n1) + T(n2) + ----+ T(nk) + f(n)
34. 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;
}
36. Describe the recurrence relation ofr 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
37.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.
38. 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.
39. Define optimal solution?
A feasible solution either maximizes or minimizes the given objective function is called as optimal solution
40. 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.
43. 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.
45. 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.
48. Define forest.
Collection of sub trees that are obtained when root node is eliminated is known as forest
.49. .What does Job sequencing with deadlines mean?
* Given a set of „n‟ jobs each job „i‟ has a deadline di such that di>=0 and a profit pi such that pi>=0.
* For job „i‟ profit pi is earned iff it is completed within deadline.
* Processing the job on the machine is for 1unit of time. Only one machine is available.
50. Define post order traversal.
The order in which the TVSP visits the nodes of the tree is called the post order traversal.
53. When is a task said to be late in a schedule?
A task is said to be late in any schedule if it finishes after its deadline else a task is early in a schedule.
56. 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;
}
57. . Define optimal solution for Job sequencing with deadlines.
Feasible solution with maximum profit is optimal solution for Job sequencing with deadlines.