Algorithms & data structures
Decrease-and-conquer
Damjan Strnad
2
Decrease-and-conquer
●
decrease-and-conquer is a problem-solving strategy
that exploits the relation between the solution of a larger
problem and the solution of a smaller case of the same
problem
●
after defining the relation between the larger and the
smaller problem instance, we solve the problem in one of
two ways:
– recursively from top down
– iteratively from bottom up
●
there are three main approaches:
– decrease by a constant
– decrease by a constant factor
– decrease by variable amount
3
Decrease by a constant
●
in each iteration of problem solving the problem size
decreases by the same constant (typically 1)
●
example: computing the exponent an for n > 0:
– relation between the problem of size n and the problem of
size n-1 is an = an-1·a
– the problem size is reduced by one in each step
– value f(n) = an can be computed:
●
by recursion from top down:
{
f (n)= f (n−1)⋅a ,
a,
if n>1
if n=1
●
from bottom up by multiplying a by itself (n−1)-times
4
Decrease by constant factor
●
in each iteration of problem solving the problem size
decreases by the same constant factor (typically 2)
●
example: computing the exponent an for n > 0:
– relation between the problem of size n and the problem
half the size is:
{
n/2 2
(a ) , if n is even and n>1
an = (an/2 )2⋅a , if n is odd and n>1
a, if n=1
– time complexity of such computation is O(log2n)
– a divide-and-conquer strategy would split the problem
differently:
{
⌊n/2⌋ ⌈n/2⌉
a = a ⋅a , if n>1
n
a, if n=1
5
Decrease by variable amount
●
in each iteration of problem solving the problem size
decreases by variable amount
●
example: Euclid's algorithm for finding the greatest
common divisor (gcd) of two numbers m and n:
– based on equality gcd(m, n) = gcd(n, m mod n)
– the right side of equation is in each iteration smaller by
a variable amount:
●
gcd(697,306) = gcd(306,85) = gcd(85,51) =
gcd(51,34) = gcd(34,17) = gcd(17,17) = 17
6
Insertion sort
●
insertion sort uses decrease-and-conquer strategy which
reduces the problem of sorting sequence A with n elements in
each iteration by a constant 1
●
if the shorter sequence A[0,...,j-1] is already sorted, we obtain the
longer sorted sequence A[0,...,j] by inserting the element A[j] at the
correct position
●
a similar procedure is used by a card player when sorting its hand
(he starts from the left and moves right, inserting each card at the
correct position in the sequence left of it)
INSERTION-SORT(A)
for j ← 1 to n-1 do
% insert value A[j] into sorted sequence A[0..j-1]
key ← A[j]
i ← j – 1
while i >= 0 and A[i] > key do
A[i+1] ← A[i] % move greater value to the right
i ← i – 1
A[i+1] ← key % put the key into correct position
7
Insertion sort – example
0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7
7 1 6 8 4 0 9 3 1 7 6 8 4 0 9 3
j j
0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7
1 6 7 8 4 0 9 3 1 6 7 8 4 0 9 3
j j
0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7
1 4 6 7 8 0 9 3 0 1 4 6 7 8 9 3
j j
0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7
0 1 4 6 7 8 9 3 0 1 3 4 6 7 8 9
j
8
Insertion sort
●
algorithm time complexity:
– the for loop always executes (n-1)-times
– execution of while loop depends on the sequence:
●
if the sequence is non-decreasing (best case), the loop
body is not executed at all, which gives T(n)=Ω(n)
●
if the sequence is decreasing (worst case), the loop
body executes (j-1)-times, which gives us T(n)=O(n2)
● it is shown that average case complexity is T (n)=O(n2)
A
INSERTION-SORT(A)
for j ← 1 to n-1 do
key ← A[j]
i ← j – 1
while i >= 0 and A[i] > key do
A[i+1] ← A[i]
i ← i – 1
A[i+1] ← key
9
Binary search
●
is an implementation of decrease and conquer strategy
(with reduction factor 2) for finding a value k in sorted array
A[bottom,…,top]:
– value k is compared to the value of middle element at index
m=⌊(bottom+top)/2⌋
– if k=A[m], we found the sought value and return m
– if k<A[m], we continue with the search in part A[bottom,..,m-1]
– if k>A[m], we continue with the search in part A[m+1,..,top]
– if we get to the case bottom>top, the value k is not in the array and
we return NIL
BINARY-SEARCH(A,bottom,top,k)
●
recursive* and iterative if bottom>top then
implementation return NIL
m ← ⌊(bottom+top)/2⌋
if k=A[m] then
return m
if k<A[m] then
return BINARY-SEARCH(A,bottom,m-1,k)
return BINARY-SEARCH(A,m+1,top,k)
10
Binary search
●
is an implementation of decrease and conquer strategy
(with reduction factor 2) for finding a value k in sorted array
A[bottom,…,top]:
– value k is compared to the value of middle element at index
m=⌊(bottom+top)/2⌋
– if k=A[m], we found the sought value and return m
– if k<A[m], we continue with the search in part A[bottom,..,m-1]
– if k>A[m], we continue with the search in part A[m+1,..,top]
– if we get to the case bottom>top, the value k is not in the array and
we return NIL BINARY-SEARCH(A,bottom,top,k)
●
recursive and iterative* while bottom<=top do
m ← ⌊(bottom+top)/2⌋
implementation if k=A[m] then
return m
if k<A[m] then
top ← m – 1
else
bottom ← m + 1
return NIL
