Solved–Assignment No: 4 –Greedy Algorithms– Solution

Description

Let N be a positive integer. We want to reduce N to 1 by applying a sequence of simple operations on N. The operations permitted are division of N by two (provided that N is even), and addition of a small positive or negative integer to N. Your objective is to reach the final goal 1 with as few applications of these operations as possible. For some choices of the small increments/decrements, greedy algorithms work. Parts 1 and 2 deal with two such cases. However, the greedy algorithm does not always work. Part 3 demonstrates that the greedy approach is not guaranteed to give an optimal solution. In Part 4, you devise an algorithm that necessarily produces optimal solutions.

Part 1

In this part, assume that the only operations permitted are decrement (by 1) and division by 2 (allowed if and only if N is even). For example, consider this reduction of 125 to 1, which uses 12 steps:

125→124→62→31→30→15→14→13→12→6→3→2→1.

This sequence is not optimal. An obvious greedy strategy is based on the fact that division by 2 produces the best possible local reduction. However, if N is odd, this operation is not allowed, so decrement N to make it even, and then divide by 2. The optimal solution involves 11 steps only:

125→124→62→31→30→15→14→7→6→3→2→1.

Implement this greedy algorithm in a function greedy1.

Part 2

Now, suppose that besides decrement by 1 and division by 2, you are permitted to increment N by 1. A greedy approach in this case is to keep on dividing N by 2 so long as it remains even. Once N becomes odd, compute N − 1 and N + 1, and choose the one which has a larger number of factors of 2. This is illustrated by the next example. This reduction has nine steps.

125→124→62→31→32→16→8→4→2→1.

A long sequence of consecutive increments/decrements does not help:

125→126→127→128→64→32→16→8→4→2→1.

Changing 125 to 128 by increments is not helpful. A shorter sequence is achieved at a reduced level by one increment of 31 to 32. This greedy strategy fails only for N = 3. The greedy reduction is 3 → 4 → 2 → 1, whereas the optimal reduction is 3 → 2 → 1. Write a function greedy2 to implement these observations.

Part 3

Now, you are allowed to increment N by one of the K values A0, A1, A2, . . . , AK−1. Here, each AI is a small positive or negative integer. Division of even integers by 2 continues to remain allowed. Following the ideas of the last two parts, we can think of a greedy approach that keeps on dividing N by 2 so long as it remains even. Once N becomes odd, you try the one among N + A0, N + A1, N + A2, . . . , N + AK−1, which has the largest number of factors of 2. In case of ties, choose the smallest one with the largest number of factors of 2. In order that this reduction is always possible, assume that A0 is either 1 or −1. Here follows an example, in
which K = 2, A0 = −1, and

125→124→62→31→30→15→14→7→6→3→2→1.

— Page 1 of 3 —
This is the same as the optimal reduction of Part 1. In particular, the option “increment by 4” is unusable under this greedy strategy (why?). We soon see that this greedy strategy is not optimal. Nevertheless, write a function greedy3 to implement this greedy algorithm. Notice that during the reduction process, N is never allowed to become zero or negative. Moreover, take care that this algorithm should not enter an infinite loop (consider N = 25, K = 2, A0 = −1, A1 = 9).

Part 4

In order to produce optimal solutions in the general case introduced in Part 3, one strategy is to avoid the temptation of dividing N by 2 as soon as it becomes even. For that matter, we can modify the greedy algorithm of Part 3 to choose, for division by 2, the smallest one from N, N + A0, N + A1, N + A2, . . . , N + AK−1 with the largest number of factors of 2. You can work out that this modified greedy strategy does not change the solution with 11 steps, given in Part 3. It may help elsewhere though.

The second and more crucial observation is that we should allow multiple addition operations before division by 2 starts. Indeed, an optimal reduction of 125 with K = 2, A0 = −1, and A1 = 4 is this (9 steps only):

125→124→128→64→32→16→8→4→2→1.

Since addition is a commutative operation, this reduction can be rephrased as

125→129→128→64→32→16→8→4→2→1.

Here, two additions are applied before division by 2.

How many consecutive additions we should do before deciding to divide by 2? Since A0 = ±1, using the best solution of Part 1 or 2 implies about log2 N divisions and at most log2 N decrements and/or increments. Since AI are small, adding each to N does not change N substantially. That is, we have to do log2 N divisions anyway. So a sequence of consecutive additions of length larger than log2 N cannot lead to an optimal solution.

Implement an O(KN log N)-time function optimal to compute an optimal solution in the general case. You may assume K 6 5, 1 6 |AI | 6 9, and A0 ∈ {−1, 1}. A recursive formulation of this problem for even N is

BN = 1 + min(BN/2, BN+A0 , BN+A1 , BN+A2 , . . . , BN+AK−1 ),

where BI is the best move count for I. For odd N, the first argument BN/2 of min should be absent. If AI is positive, we have N + AI > N, but the solution BN requires the solution BN+AI (in the above example, B124 requires B128, and B125 requires B129).

Write a loop for iteratively improving the best solutions for each I in the range [2, M], where M is slightly (how much?) larger than N. Consider the reduction of 125. The first iteration discovers the best reduction sequence for 128. The second iteration discovers the best sequence for 129 by noticing that 128 = 129 + A0. Yet another iteration is needed to find an optimal move for 125 by making use of the formula 129 = 125 +A1. You may run the loop log2 N times, or break when no further improvements are achieved in an iteration.

The MAIN() function

• Read N from the user.

• Call greedy1 and greedy2 on this N, and report the greedy reductions of N. These are optimal.

• Read K, and A0, A1, A2, . . . , AK−1 from the user.
• Call greedy3 on N, K, A0, A1, A2, . . . , AK−1 to show the performance of the greedy strategy.

• Call optimal on N, K, A0, A1, A2, . . . , AK−1 to obtain an optimal solution.

Submit a single C/C++ source file. Do not use global/static variables.

— Page 2 of 3 —
Sample output

n = 125
+++ Greedy 1
Start : 125
Decrement : 124
Divide : 62
Divide : 31
Decrement : 30
Divide : 15
Decrement : 14
Divide : 7
Decrement : 6
Divide : 3
Decrement : 2
Divide : 1
— Number of steps = 11
+++ Greedy 2
Start : 125
Decrement : 124
Divide : 62
Divide : 31
Increment : 32
Divide : 16
Divide : 8
Divide : 4
Divide : 2
Divide : 1
— Number of steps = 9
k = 2
-1 4
+++ Greedy 3
Start : 125
Add -1 : 124
Divide : 62
Divide : 31
Add -1 : 30
Divide : 15
Add -1 : 14
Divide : 7
Add -1 : 6
Divide : 3
Add -1 : 2
Divide : 1
— Number of steps = 11
+++ Optimal
Start : 125
Add -1 : 124
Add 4 : 128
Divide : 64
Divide : 32
Divide : 16
Divide : 8
Divide : 4
Divide : 2
Divide : 1
— Number of steps = 9

— Page 3 of 3 —