02-06-2012, 12:01 PM
Design and Analysis of Algorithm
Design and Analysis of Algorithm.doc (Size: 305.5 KB / Downloads: 74)
General method:
• Given a function to compute on ‘n’ inputs the divide-and-conquer strategy suggests splitting the inputs into ‘k’ distinct subsets, 1<k<=n, yielding ‘k’ sub problems.
• These sub problems must be solved, and then a method must be found to combine 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.
• Often the sub problems resulting from a divide-and-conquer design are of the same type as the original problem.
• For those cases the re application of the divide-and-conquer principle is naturally expressed by a recursive algorithm.
• D And C(Algorithm) is initially invoked as D and C(P), where ‘p’ is the problem to be solved.
• Small(P) is a Boolean-valued function that determines whether the i/p size is small enough that the answer can be computed without splitting.
• If this so, the function ‘S’ is invoked.
• Otherwise, the problem P is divided into smaller sub problems.
BINARY SEARCH
• Algorithm, describes this binary search method, where Binsrch has 4I/ps a[], I , l & x.
• It is initially invoked as Binsrch (a,1,n,x)
• A non-recursive version of Binsrch is given below.
• This Binsearch has 3 i/ps a,n, & x.
• The while loop continues processing as long as there are more elements left to check.
• At the conclusion of the procedure 0 is returned if x is not present, or ‘j’ is returned, such that a[j]=x.
• We observe that low & high are integer Variables such that each time through the loop either x is found or low is increased by at least one or high is decreased at least one.
Maximum and Minimum:
• Let us consider another simple problem that can be solved by the divide-and-conquer technique.
• The problem is to find the maximum and minimum items in a set of ‘n’ elements.
• In analyzing the time complexity of this algorithm, we once again concentrate on the no. of element comparisons.
• More importantly, when the elements in a[1:n] are polynomials, vectors, very large numbers, or strings of character, the cost of an element comparison is much higher than the cost of the other operations.
• Hence, the time is determined mainly by the total cost of the element comparison.