Performance measurement is concerned with obtaining the space and the time requirements of a particular algorithm.
An algorithm is a finite set of instructions that, if followed, accomplishes a particular task.
A program is the expression of an algorithm in a programming language. Sometimes works such as procedure, function and subroutine are used synonymously program.
The general form of a for Loop is
For variable : = value 1 to value 2 step
Step do
{
<statement 1>
<statement n >
}
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.
The space complexity of an algorithm is the amount of memory it needs to run to completion.
The time complexity of an algorithm is the amount of computer time it needs to run to completion.
Performance evaluation can be loosely divided into two major phases:
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.
The best-case step count is the minimum number of steps that can be executed for the given parameters.
The worst-case step count is the maximum number of steps that can be executed for the given parameters.
The average step count is the average number of steps executed an instances with the given parameters.
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.
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.
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.
The function f(n) = 0(g(n))
Iff Lim f(n) = 0
n - µ g(n)
The function f(n) = w (g(n))
iff
Lim f(n) = 0
n - µ g(n)
Algorithm sum(a,n)
{
S : = 0.0
For i=1 to n do
S : - S + a[i];
Return S;
}
Algorithm Rsum (a,n)
{
If(n_ 0) then
Return 0.0;
Else Return Rsum(a, n- 1) + a(n);
}
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!
One of the methods for solving any such recurrence relation is called the substitution method.
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.
A recurrence equation is an equation or inequality that describes a function in terms of its value on smaller inputs.
Recurrence Equations can be classified into
UNIT II - BRUTE FORCE AND DIVIDE-AND-CONQUER
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 tocombine subsolutions into a solution of the whole. If the subproblems are still relatively large, then the divide-and conquer strategy can possibly be reapplied.
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.
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 subproblems
Return combine (DAnd C(_1) DAnd C(_2),----, DAnd ((_k));
}
}
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.
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(log n) best, average and worst.
The external path length E, is defines analogously as sum of the distance of all external nodes from the root.
The internal path length ‘I’ is the sum of the distances of all internal nodes from the root.
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.
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.
N quick sort, the division into sub arrays is made so that the sorted sub arrays do not need to be merged later.
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).
Insertion sort works exceedingly fast on arrays of less then 16 elements, though for large ‘n’ its computing time is O(n2).
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];
}
}
The recurrence relation is
T(n) = g(n)
T(n1) + T(n2) + ----+ T(nk) + f(n)
Algorithm BinSearch(a,n,x)
//Given an array a[1:n] of elements in non decreasing
// 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;
}
The circular node is called the internal nodes.
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
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.
A feasible solution either maximizes or minimizes the given objective function is called as optimal solution.
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.
A directed binary tree for which each edge is labeled with a real number (weight) is called as weighted tree.
In places where the loss exceeds the tolerance level boosters have to the placed. Given a network and loss tolerance level the tree vertex splitting problems is to determine an optimal placement of boosters.
The ‘n’ task will be given with starting time si and finishing time fi. Feasible Solution is that the task should not overlap and optimal solution is that the task should be completed in minimum number of machine set.
Let T= (V, E, W) be a weighted directed binary tree where
V_ vertex set
E_ edge set
W_ weight function for the edge.
W is more commonly denoted as w (i,j) which is the weight of the edge <i,j> _ E.
Collection of sub trees that are obtained when root node is eliminated is known as forest
The order in which the TVSP visits the nodes of the tree is called the post order traversal.
To calculate delay
d(u)=max{d(v)+w(u, v)}
v _ c(u)
The condition in which the node gets splitted are:
d(u)+w(u ,v)>_ and also d(u) is set to zero.
The network can tolerate the losses only up to a certain limit tolerance limit.
A task is said to be late in any schedule if it finishes after its deadline else a task is early in a schedule.
Given a weighted tree T(V,E,W) and a tolerance limit _ any subset X of V is a
feasible solution if d(T/X).
An optimal solution is one in which the number of nodes in X is minimized.
UNIT III - DYNAMIC PROGRAMMING AND GREEDY TECHNIQUE
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.
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.
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.
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.
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.
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;
}
Feasible solution with maximum profit is optimal solution for Job sequencing with deadlines.
Greedy method Dynamic Programming
candidates.
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.
Thus it is always safe to make greedy choice.
choice are empty.
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.
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.
The formula to calculate optimal solution is
g0(m)=max{g1, g1(m-w1)+p1}.
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.
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.
A preemptive schedule is a schedule in which the processing of a task on any processor can be terminated before the task is completed.
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.
The mean flow time MFT (S) is defined to be]
MFT (S) = 1 S fi(S)
n 1<i<n
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.
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.
The tree organizations that are independent of the problem instance being solved are called as static tree.
The tree organizations those are independent of the problem instance being solved are called as static tree.
A node which has been generated and all of whose children have not yet been
generated is called as a live node.
E – node (or) node being expanded. Any live node whose children are currently being generated is called as a E – node.
Dead node is defined as a generated node, which is to be expanded further all of whose children have been generated.
A spanning tree of a graph G is a sub graph which is basically a tree and it contains all the vertices of G containing no circuit.
A minimum spanning tree of a weighted connected graph G is a spanning tree with minimum or smallest weight.
34. What is the difference between Prim’s and Kruskal’s algorithm?
S.No |
Prim’s algorithm |
Kruskal’s algorithm |
1 |
This algorithm is for obtaining minimum spanning tree by selecting the adjacent vertices of already selected vertices. |
This algorithm is for obtaining minimum spanning tree but it is not necessary to choose adjacent vertices of already selected vertices |
UNIT V - COPING WITH THE LIMITATIONS OF ALGORITHM
A bi-connected graph G = (V, E) is a connected graph which has no articulation point. A bi-connected component of a graph G is maximal bi-connected sub graph.
The Graph G = (V, E0) be a connected undirected graph, then an articulation point of a graph G is a vertex whose removal disconnects graph G. This articulation point is a kind of cut-vertex.
Find a solution by trying one of several choices. If the choice proves incorrect, computation backtracks or restarts at the point of choice and tries another choice. It is often convenient to maintain choice points and alternate choices using recursion.
Branch and bound refers to all state space search methods in which all children of an E-node are generated before any other live node can become the E-node.
5. What is the difference between backtracking and branch and bound?
S.No |
Backtracking |
Branch and bound |
1 |
State space tree is constructed using depth first search |
State space tree is constructed using best first search |
2. |
Finds solutions for combinatorial |
Finds solutions for combinatorial |
3. |
No bounds are associated with the nodes in the state space tree. |
Bounds are associated with the each and every node in the state space tree. |
The Least cost search is a kind of search in which least cost is involved for reaching to answer node. At each E-node the probability of being an answer node is checked.
If an NP hard problem can be solved in polynomial time then all NP complete problems can also be solved in polynomial time. An optimization problem may be hard, cannot be complete.
A problem that is NP complete can be solved in polynomial time then all NP complete problems can also be solved in polynomial time. Only decision problem can be NP complete.
10. Differentiate between Deterministic and Non Deterministic algorithms.
S.No |
Deterministic algorithm |
Non-Deterministic algorithm |
1 |
Deterministic algorithms are the algorithms with uniquely defined results and predictable in terms of output for certain output. |
Non-Deterministic algorithms are the algorithms that allowed containing operations whose outcomes are limited to a given a set possibilities instead of being uniquely defined. |
Any problem for which the answer is either zero or one is called a decision problem.
Any problem that involves the identification of an optimal value of a given cost function is known as an optimization problem.
Explicit constraints are rules that restrict each xi to take values only from a given set.
e.g :
xi > 0 or Si = {all nonnegative real numbers}
xi = 0 or 1 or Si = {0,1}
li ≤ xi ≤ ui or Si = {a: li ≤ a ≤ ui}
All tuples satisfying the explicit constraints define a possible solution space for i
(i-problem instance).
The implicit constraints are rules that determine which of the tuples in the solution space of I satisfy the criterion function. Thus implicit constraints describe the way in which the xi must relate to each other. E.g: 8-queens problem.
It is a classic combinatorial problem that place eight queens on an 8×8 chessboard so that no two attack that is no two of them are on the same row, column, or diagonal.
A state space tree is a rooted tree whose nodes represent partially constructed solutions to given problem. In backtracking the state space tree is built for finding the solution. This tree is built using depth first search fashion.
Static trees are ones for which tree organizations are independent of the problem instance being solved
Live node is a generated node for which all of the children have not yet been generated.
Dead node is a generated node that is not to be expanded any further or for which all of its children have been generated.
Bounding function is a function used to kill live nodes without generating all their children.
Tuples that satisfy the explicit constraints define a solution space. The solution space can be organized into a tree.
Backtracking always produces optimal solution since backtracking is a systematic way to go through all the possible configurations of a solution space for the problem instance
There are n distinct positive numbers and desired to find all combinations of these numbers, whose sums are m. This is called sum of subset problem.
G = (V, E) be a connected graph with n vertices. A Hamiltonian cycle is a round trip path along n edges of G which visits every vertex once and returns to its starting position. The tour of a traveling salesperson problem is a Hamiltonian cycle.
E-node is a live node whose children are currently being generated or expanded.
Answer states are that solution state s, for which the path from root node to s defines a tuple that is a member of set of solutions. These states satisfy implicit constraints.
To solve any problem using backtracking, it requires that all the solutions satisfy a complex set of constraints. They are:
i. Explicit constraints.
ii. Implicit constraints.
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.
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.
The tree organization of the solution space is referred to as state space tree.
All the paths from the root of the organization tree to all the nodes is called as state space of the problem
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.
Source: https://www.snscourseware.org/snsct/files/CW_588edbb22de05/IT204-Design%20and%20Analysis%20of%20Algorithms.doc
Web site to visit: https://www.snscourseware.org
Author of the text: indicated on the source document of the above text
If you are the author of the text above and you not agree to share your knowledge for teaching, research, scholarship (for fair use as indicated in the United States copyrigh low) please send us an e-mail and we will remove your text quickly. Fair use is a limitation and exception to the exclusive right granted by copyright law to the author of a creative work. In United States copyright law, fair use is a doctrine that permits limited use of copyrighted material without acquiring permission from the rights holders. Examples of fair use include commentary, search engines, criticism, news reporting, research, teaching, library archiving and scholarship. It provides for the legal, unlicensed citation or incorporation of copyrighted material in another author's work under a four-factor balancing test. (source: http://en.wikipedia.org/wiki/Fair_use)
The information of medicine and health contained in the site are of a general nature and purpose which is purely informative and for this reason may not replace in any case, the council of a doctor or a qualified entity legally to the profession.
The texts are the property of their respective authors and we thank them for giving us the opportunity to share for free to students, teachers and users of the Web their texts will used only for illustrative educational and scientific purposes only.
All the information in our site are given for nonprofit educational purposes