Algorithm Design and Evaluation - 8

= C 1 n 2 + C 2 (n-1)n And T(n) = O(n 2 )

So we can't improve anything with the usual multiplication algorithm. We transform the formula (*) as follows:

XY = AC10 n + [(A -B)(DC) + AC + BD]10 n/2 + BD (**)

According to this formula, we only need 3 multiplications of n/2 digit integers, 6 additions and subtractions, and 2 multiplications with 10 n , 10 n/2 .

Example 2.2.

We illustrate this process by multiplying 981 by 1234. First we fill the shorter operand with a meaningless zero to make the two operands the same length, so 981 becomes 0981. Then we split each operand into two halves:

0981 splits into w = 09 and x = 81 1234 splits into y = 12 and z = 34

Note that 981 = 10 2 w + x and 1234 = 10 2 y + z. Therefore, the required product can be calculated as

is:

981 x 1234 = (10 2 w + x)( 10 2 y + z)

= 10 4 wy + 10 2 (wz + xy) + xz

= 1080000 + 127800 + 2754

= 1210554

The above procedure gives four multiplications of halves: wy, wz, xy and xz.

Note that the key point here is that we don't actually need to calculate wz or xy, but the sum of the two. Is it possible to get wz + xy by simply multiplying? This seems impossible until we remember that we also need the values ​​of wy and xz to input into the formula above. With this in mind, consider the product:

r = (w + x)(y+z) = wy + (wz + xy) + xz

After just one multiplication, we obtain the sum of all three terms needed to calculate the desired product. This suggests the following procedure:

p = wy = 09 * 12 = 108

q = xz = 81 * 34 = 2754

r = (w + x)(y+z) = 90 * 46 = 4140

and finally

981 x 1234 = 10 4 p + 10 2 (r – p – q) + q

= 1080000 + 127800 + 2754 = 1210554.

Thus the product of 981 and 1234 can be reduced to three multiplications of two two-digit numbers (09 by 12, 81 by 34 and 90 by 46) together with some shift (multiplication by powers of 10), addition and subtraction.

From there we come up with the algorithm for multiplying large integers as Nhan(x,y,n)

{

if (n == 1) Return x[0]*y[0]; Else

{

a = x[n-1]. . . x[n/2];

b = x[n/2-1] . . . x[0];

c = y[n-1]. . . y[n/2];

d = y[n/2-1] . . . y[0];

U = Nhan(a,c,n/2);

V = Nhan(b,d,n/2);

W = Nhan(a+b,c+d,n/2);

Return U*10 n + (WUV)*10 n/2 + V

}

}

4) Evaluate the computational complexity of the algorithm

We have the following recursive equation: T(1) = 1

T(n) = 3T(n/2) + cn

Solving the equation, we get T(n) = O(n log3 ) = O(n 1.59 ). This is clearly a big improvement over the old algorithm. This algorithm can multiply two large integers much faster than the classical multiplication algorithm, and the larger n is, the more valuable this improvement is.

Chapter 2 exercises

1. Give two algorithms designed using divide and conquer technique.

2. Use the divide and conquer technique to design an algorithm to solve the following problem:

Calculate the sum: 1 + 1/2 + 1/3 + ... + 1/n where n is a positive integer.

3. Use the divide and conquer technique to design an algorithm to solve the following problem: Find the greatest common divisor of two positive integers.

4. Hanoi Tower problem

There are n disks with different diameters placed on top of each other at position A, the small disk is on top of the big disk. To move the stack of disks to position B, position C is used as the intermediate position with the following conditions: Only one disk can be moved at a time and during the moving process, the big disk can never be placed on top of the small disk.

Instruct:

Apply the divide and conquer technique:

The problem of moving N disks from A to B can be divided into smaller problems as follows:

(a) Move N-1 disks above from A to C

(b) Move a disk from A to B

(c) Move N-1 disks from C to B.

Thus the problem has been transformed into similar problems of smaller size. The work is continued with (n-1) disks and so on until there is only one disk left.

5. Problem of swapping two parts in a sequence

Let a[1..n] be an array of n elements. We need to swap the first m elements of the array with the rest of the array (nm elements) without using a sub-array.

For example, with n = 8, a[8] = (1, 2, 3, 4, 5, 6, 7, 8)

If m = 3, then the result is: ( 4, 5, 6, 7, 8, 1, 2, 3)

If m = 5, then the result is: ( 6, 7, 8, 1, 2, 3, 4, 5)

If m = 4, then the result is: ( 5, 6, 7, 8, 1, 2, 3, 4) Instructions:

- If m = n – m: Swap the elements of the 2 halves of the array with equal length

:

- If m  n–m

+ If m < n – m: swap the first m elements with the last m elements of the remaining part. Then in the array a[1..nm] we only need to swap the first m elements with the remaining part.

+ If m > n – m : swap the first nm elements with the next nm elements. Then in the array a[n-m+1 . . n] we swap the last nm elements of the array with the elements of the first part.

Thus, by applying the divide and conquer method, we divide the problem into 2 sub-problems:

- The first problem is to swap two sub-arrays of equal length, specifically swapping half of the first and last elements of the array with each other by swapping each pair of corresponding elements.

- The second problem is of the same form as the given problem but smaller in size, so we can call a recursive algorithm to solve it and the recursive calling process will stop when we reach the exchange of 2 parts of equal length.

So the key to the algorithm is to perform the operation of swapping 2 groups of elements, repeating this operation while the number of elements of the 2 groups is still different. Therefore, we will replace the recursive algorithm with an iterative algorithm.

// Swap the first m elements of the array with the remaining ones. Input : a[1..n], m. (m ≤n)

Output : a[1..n] with the property that m elements of the first array a (input array) are at the end of the result array, nm elements of the last array input are at the beginning of the result array.

Algorithm description: Transpose(a,n,m)

{

i = m; j = nm; m = m+1; When ( i != j)

If ( i > j)

{

Exchange(a,mi,m,j); i = i – j;

}

Opposite

{

j = j – i;

Exchange(a,mi,m+j,i);

}

Exchange(a,mi,m,i);

}

Exchange function: input a,

i,j, //position

m; // Number of elements to swap output a

Exchange(a,i,j,m)

{

For all p = 0 -> m-1

Swap (a[i+p], a[j+p]);

}

6. Schedule sports events

There are n = 2 k opponents competing with each other in a round robin format: Each player must compete with every other player 1 match. Each player can compete at most 1 match per day. Arrange the competition schedule so that the number of competition days is the least.

Instruct:

Since the competition is a round robin, each player must play exactly n-1 matches. We can easily see that since n is an even number, we can arrange at most n/2 pairs to compete in one day and therefore need at least n-1 days. We will try to build a schedule so that the number of competition days is n-1.

The match schedule is a table of n rows and n-1 columns. The rows are numbered from 1 to n and the columns are numbered from 1 to n-1, where row i represents player i, column j represents match day j and cell (i, j) records the player who has to play against player i on day j.

The divide and conquer technique is applied to build the competition schedule as follows: To schedule n players, we will schedule n/2 players, to schedule n/2 players, we will schedule n/4 players...

This process will lead to the basic problem of scheduling matches for 2 players. These two players will play one match in one day, so scheduling them is easy. The difficulty is that from the schedules for the two players, we synthesize them to get the schedule

4 player, 8 player, ...

The upper left corner of the table is the schedule of n/2 players from 1 to n/2 on days 1 to [(n-1)/2], from which we have the lower left corner is the schedule of players from n/2+1 to n on these days: it will be equal to the elements in the upper left corner plus n/2. The lower right corner of the table is the upper left corner and the upper right corner is the lower left corner. As for the column [(n-1)/2] +1, the first n/2 players will play against the next n/2 players in turn and vice versa.

For example: Starting from the schedule for two players, we can build a schedule for four players as follows: The schedule for four players will be a table with 4 rows and 3 columns. The schedule for players 1 and 2 on the first day is the schedule for two players (basic problem). Thus, we have O(1,1) = “2” and O(2,1) = “1”. Similarly, we have the schedule for players 3 and 4 on the first day. That is, O(3,1) = “4” and O(4,1) = “3”. (We can see that O(3,1) = O(1,1) + 2 and O(4,1) = O(2,1) + 2 ). We

Take the upper left corner of the board and fit it to the lower right corner and take the lower left corner and fit it to the upper right corner. Now to complete the match schedule for 4 players, we fill in column 2.

The schedule for 8 players is a table of 8 rows and 7 columns. The upper left corner is the schedule for the first 3 days of the 4 players from 1 to 4. The cells in the lower left corner will be equal to the corresponding cells in the upper left corner plus 4. This is the schedule for the 4 players 5, 6, 7 and 8 in the first 3 days. Now we complete the schedule by filling the lower right corner with the upper left corner and the upper right corner with the lower left corner and filling in column 4.

Below are the match schedules for 2 players, 4 players and 8 players according to the above construction:

2 players

2

1

1

1

2

4 players

Maybe you are interested!

• Algorithm Design and Evaluation - 15
• Algorithm Design and Evaluation - 13
• Evaluation of Research Situation and Issues Raised for the Thesis
• Design and construction of color TV PAN model - 2
• Evaluation of Online Marketing Activities of Philip Entertainment Media and Entertainment Company Limited - 1

1 2 3

1

2

3

4

8 players

1 2 3 4 5 6 7

1

2

3

4

5

6

7

8