haihongyuan.com

# L5 Divide And Conquer

Module U08282: Advanced Data Structures Week 5: Divide and Conquer Chris Cox
C Cox - 2012

Topics:
? ? ? ? ? ? ? ? ? ? ? Definitions Some simple problems Binary search Integer multiplication Matrix multiplication Tiling Bisection Median Merge Sort Bucket Sort Adaptive Quadrature
School of Technology

1

Definition
? Divide and conquer is an important algorithm-design paradigm.
C Cox - 2012

? It works by recursively breaking down a problem into two or more sub-problems of the same (or related) type, until these become simple enough to be solved directly. ? The solutions to the sub-problems are then combined to give a solution to the original problem.

? This technique is the basis of efficient algorithms for all kinds of problems, such as sorting (quicksort, mergesort).
Source: Wikipedia

School of Technology

2

Steps in divide and conquer
The divide-and-conquer-strategy for solving a problem consists of three steps:
C Cox - 2012

1. Divide: the problem is decomposed into subproblems 2. Conquer: the subproblems are solved 3. Combine: the solutions of the subproblems are recombined to the solution of the original problem

School of Technology

3

Example of divide and conquer: TallestPerson in USA

C Cox - 2012

1. Each of the 50 states finds the tallest person in that state. 2. Find the tallest of these 50 persons and that is the tallest person in USA.

Part 1. can be determined in parallel.

School of Technology

4

Example of divide and conquer: LargestNumber
function LargestNumber(L:array of integer; start,finish:integer); { pre: L is a non-empty list of integers post: LargestNumber(L) = the largest number in the list L } var largest1,largest2,mid:integer; begin if start=finish then LargestNumber:=L[start] else begin mid:=(start+finish)div 2; largest1:=LargestNumber(L,start,mid); largest2:=LargestNumber(L,mid+1,finish); if largest1>largest2 then largest:=largest1 else largest:=largest2 end; LargestNumber:=largest end { LargestNumber };
Source: Wikipedia, translated into Pascal

C Cox - 2012

School of Technology

5

Example of divide and conquer: Binary search
? We have already seen one divide-and-conquer: binary search ? The search space needs to be in sorted sequence ? At each step we divide the search space in two and then only need to search in one half of the sequence. ? We can do this iteratively or recursively.

C Cox - 2012

School of Technology

6

Binary search: iterative
procedure Position(x:integer;var found:boolean;var pos:integer); var left,right,mid:integer; begin left:=0; right:=size; (* global size*) while left<>right do begin mid:=(left+right) div 2; if a[mid]>x then left:=mid+1 else right:=mid end; found:=(left<>size) and (a[left]=x); if found then pos:=left end (* position *);

C Cox - 2012

School of Technology

7

The binary search recursive function
function search(book:array[1..max] of person; nameKey:String; first,last:integer): integer; Var index:integer; begin if first>la