The Greedy Approach Other examples: Dijkstra's algorithm for the shortest path problem Kruskal's algorithm for the minimum cost spanning tree problem
The Greedy Approach ◼ Other examples: ➢ Dijkstra’s algorithm for the shortest path problem ➢ Kruskal’s algorithm for the minimum cost spanning tree problem
Divide and Conquer A divide-and-conquer algorithm divides the problem instance into a number of subinstances (in most cases 2),recursively solves each subinsance separately,and then combines the solutions to the subinstances to obtain the solution to the original problem instance
Divide and Conquer ◼ A divide-and-conquer algorithm divides the problem instance into a number of subinstances (in most cases 2), recursively solves each subinsance separately, and then combines the solutions to the subinstances to obtain the solution to the original problem instance
Divide and Conquer Consider the problem of finding both the minimum and maximum in an array of integers A[1...n]and assume for simplicity that n is a power of 2. Divide the input array into two halves A1...1/2] and A[(/2)+1...n],find the minimum and maximum in each half and return the minimum of the two minima and the maximum of the two maxima
Divide and Conquer ◼ Consider the problem of finding both the minimum and maximum in an array of integers A[1…n] and assume for simplicity that n is a power of 2. ◼ Divide the input array into two halves A[1…n/2] and A[(n/2)+1…n], find the minimum and maximum in each half and return the minimum of the two minima and the maximum of the two maxima
Divide and Conquer Input:An array A[1...n of n integers,where n is a power of 2; Output:(x,y:the minimum and maximum integers in A; 1.minmax(1,ni minmax low,high 1.if highlow=1 then ■ 2. if Alow]<A[high]then return (A[low],A[high]) ■ 3. else return(A[high],A[low]) ■ 4. end if; ■ 5.else ■ 6. midk(low+high)/2; ■ 7. (,h)←-minmax low,mi); ■ 8. (x,y)-minmax mid+1,high); ■ 9. -minf,为； ■ 10.y←-max{h,i 11. return(x,y); ■ 12.end if;
Divide and Conquer ◼ Input: An array A[1…n] of n integers, where n is a power of 2; ◼ Output: (x, y): the minimum and maximum integers in A; ◼ 1. minmax(1, n); ◼ minmax(low, high) ◼ 1. if high-low=1 then ◼ 2. if A[low]<A[high] then return (A[low], A[high]); ◼ 3. else return(A[high], A[low]); ◼ 4. end if; ◼ 5. else ◼ 6. mid(low+high)/2; ◼ 7. (x1 , y1 )minmax(low, mid); ◼ 8. (x2 , y2 )minmax(mid+1, high); ◼ 9. xmin{x1 , x2}; ◼ 10. y max{y1 , y2}; ◼ 11. return(x, y); ◼ 12. end if;
Divide and Conquer How many comparisons does this algorithm need?
Divide and Conquer ◼ How many comparisons does this algorithm need?