Corrected exercises Divide and conquer algorithm

The following corrected exercises concern the creation of algorithms according to the structure of the divide and rule (divide&conquer).

divide and rule

Exercise 1

We are going to play the game of “smaller, bigger”. The goal is to guess a number between 1 and n (integer). We consider that the algorithm takes as input the value of n and the number x to guess, and that it returns the number of moves to find this number.

a – State the problem more formally.

b – Write the iterative algorithm solving this problem.

c – Write the algorithm recursive solving this problem.

d – Compare complexities.

a – The problem could be rewritten as follows: Given an array sorted in ascending order of integers, how to determine whether an element belongs to this array or not? The principle is well known: the element sought is compared to the median element, and if necessary, the search is repeated in the left or right part of the table.

binary search algorithm

b- The iterative algorithm is as follows:

binary search algorithm

Since the array is cut in two each time, we will go through at most log n element before finding the right one or knowing that it does not exist. The complexity is therefore O(log n)

vs - By default the response of the algorithm is false, unless there is a true which is returned which will give in the main then the method:

binary search algorithm

Since the operation is exactly the same as the iterative algorithm, one suspects that the complexity is the same.

Exercise 2

We are looking for the sum of an array B of n integer elements.

1 – Write a algorithm of divide-and-conquer type which solves this problem.

2 – Analyze its complexity and make the call tree for the array [3,4,2,3,4].

3 – Compare it with an iterative algorithm that you will describe

We define the function Sum(B,i,j) which is the sum of the elements of B between positions i and j. So the sought value is Sum(B,1,n). We will calculate Sum(B,i,j) by dividing the array B[i..j] into two halves; calculating sums for each half; and adding these two sums. This gives the following code:

sum array recursive algorithm

For complexity, since we haven't seen the Master Theorem yet, we'll use the call tree:

sum array recursive algorithm

We understand that we cut the painting in two each time. The calculation is simple, so the complexity only depends on the depth of the tree p such that 2^p > n (array size) hence p > log n and a complexity of O(log n).

The iterative algorithm is as follows:

sum array recursive algorithm

Here the complexity is O(n).

Exercise 3

We say that an array has a majority element if a value of the array is present at least n/2 times out of n elements.

1 – Propose an iterative algorithm to solve this problem.

2 – Propose a method to solve this divide and conquer problem.

3 – Write the method described by an algorithm.

Modify your algorithm taking into account the following properties:

  • if only one of the halves provides a majority, only that element can be a majority in the full array.
  • if the two recursive calls provide majorities, they are different, with a different number of occurrences: the only one that can be a majority is the one with the greatest number of occurrences.
  • in the case where n is a power of 2, and therefore the halves always of equal size, if there are two different majorities with the same number of occurrences, then there can be no majorities in the complete table.

1 – We count the number of occurrences of each element (no need to count to the left because if it exists then it has already been counted before). For the first loop, we could have stopped at n/2 + 1 because even if all the following elements were identical, it would still not be the majority.

majority recursive algorithm

2 – We will start from the principle of divide and conquer:

majority recursive algorithm

If there is a majority element x in E, then x is in the majority in at least one of the two lists E1 and E2 (indeed if x does not have a majority in E1, nor in E2, then in E, number of x ≤ n/4 + n/4 = n/2).

The principle of recursion is then as follows: calculate the majority elements of E1 and E2 (if they exist) with the total number of occurrences of each and deduce whether one of the two is the majority in E.

The following algorithm Majority(i, j) returns a couple which equals (x, cx) if x is the majority in the sub-array E[i..j] with cx occurrences and which equals (−, 0) if it there is no majority in E[i..j], the initial call being Majority(1, n). The Occurence(x, i, j) function calculates the number of occurrences of x in the sub-array E[i..j].

majority recursive algorithm

It is not so easy to understand, let's take an example of an 8 element array with 5 identical elements to fully understand how it works.

majority recursive algorithm

Here is the majority algorithm taking into account the new properties:

majority divide and conquer

Exercise 4

1 – Propose a divide-and-conquer algorithm seeking the minimum of an array.

2 – Likewise with the maximum.

3 – Similarly by looking for both the minimum and the maximum.

I will give the answer directly to question 3 since it contains the answer to the two previous ones. In this method, it is necessary to remember the positions in the table as well as the value of min and max.

min max divide and conquer

Exercise 5

Here is the matrix product formula:

matrix product

1 – Propose an iterative algorithm and give its complexity.

2 – To decompose a matrix into a dichotomy, it must be done both on the rows and on the columns, therefore in 4 parts like the following diagram:

matrix product

Each element is a square matrix. Develop the equations for calculating r, s, t, and u.

3 – Strassen has found a method to further reduce the number of calculations. It proposes to calculate r, s, t, u using a linear combination (addition or subtraction) of the following matrices:

Strassen's algorithm

Express r, s, t, u in terms of pi.

4 – Propose a recursive algorithm based on Strassen calculations for the matrix product.

1 – We notice in the formula that we will have to make three loops according to i, j and k. 

matrix product algorithm

Deep within the iteration structures, there are three nested 1 to n loops, so a complexity of O(n^3)

2 – By developing the equation we obtain the following result:

strassen's algorithm

3 – This gives the following linear relations:

strassen's algorithm

4 – The divide and conquer algorithm is as follows:

strassen's algorithm

Exercise 6

Write a pseudo code for a divide and conquer algorithm to find the position of the largest element in an array of numbers. Write a pseudocode for a brute force algorithm, compare with the previous one. Show a tree of the divide and conquer algorithm process. What is the maximum tree level for numbers?

divide and conquer dynamic programming corrected exercises

The brute force algorithm is trivial: a loop.

At each level l, the complete binary tree is composed of 2^(l-1) leaves. So the total of the vertices is 2^l -1. Let l be the level of the tree, so l=sup(log_2 (n)).

Exercise 7

Write pseudocode for a divide-and-conquer algorithm for the exponentiation problem of computing a^n where a>0 and n is a positive integer. Write a pseudocode for a brute force algorithm, compare with the previous one. Show a process tree of the divide and conquer algorithm. What is the maximum level of the tree for n not given? Check the termination, accuracy and completeness.

Exercise 8

To multiply two whole numbers of n digits, a naive method consists in multiplying each digit of the first number by each digit of the second, and making the correct offsets and the correct sums. The calculation time is then in O(n²).

Karatsuba's algorithm uses the principle that the calculation used in this naive approach:

(a × 10^k+ b)(c × 10k+ d) = ac × 10^2k+ (ad + bc) × 10^k+ bd

requiring four products (ac, ad, bc and bd) can be done with only three products by grouping the calculations in the following form:

(a × 10^k + b)(c × 10^k + d) = ac × 10^2k + (ac + bd − (a − b)(c − d)) × 10^k + bd

Certainly subtractions have been introduced, but only three products of large numbers are now necessary: ac, bd and (a − b)(c − d).

As additions and subtractions are inexpensive (negligible compared to multiplications), we will save calculation time. For information, multiplication by a power of the calculation base corresponds to a digit shift and is very quick to execute on a machine.

Write the code of the karatsuba() function allowing to multiply two large integers of n digits according to this principle.

Exercise 9

Given a set of real points, find the minimum distance between two points using a Divide and Conquer type algorithm. For this we will use the Euclidean distance between two points.

The obvious solution is to make a distance matrix between each pair of points. The divide and conquer algorithm cuts the space recursively into 2 blocks and looks at the minimum distance in each block. Moreover, it is then necessary to look at the smallest distance between points of two different blocks.

min distance divide and conquer

Divide-and-rule solution
— Sort the points relative to their x coordinates.
— Divide the points into two groups: the left half and the right half.
— Use recursion to find dg, the min distance between points of
left.
— Use recursion to find dd, the min distance between line points.
— The optimal solution is:
     — either dg,
     — either dd,
     — let be the distance between two points A and B such that A is in the part
left and B is in the right part.

Let midx be the x coordinate of the rightmost point among the left points. Note that in the third case cited above, the two points A and B are located in a thin band of width min(dg, dd), centered at midx.

We notice in the central band, two points located on the same side of the
midx boundary are at least distance d from each other. This information is used as follows:

— We start by sorting all the points present in the central band according to their y coordinate.

 For each point A in the central band, we look at the distance that separates it from the points located in its radius.

min distance divide and conquer

Exercise 10

In this exercise, we are interested in the complexity in the worst case and in the number of comparisons of the algorithms.

1. To find the largest and second largest element of n integers, give a naive algorithm and its complexity.

2. To improve performance, we propose to consider the solution consisting in calculating the maximum according to the principle of a tournament (tennis tournament for example). Consider first the case where there are n = 2^k numbers competing in the tournament. How do we find, once the tournament is over, the second largest? What is the complexity of the algorithm? In the general case, how to adapt the method to deal with arbitrary n?

1.

double max

sequel to come

To share
en_GBEN
%d bloggers like this: