Suppose you want to dial a telephone number consisting of n digits on a standard

Question

Suppose you want to dial a telephone number consisting of n digits on a standard 12-button telephone keypad, using the index fingers of both hands. Assuming both fingers start over the 1 button, devise an O(n) time algorithm using dynamic programming (in particular, give the recursive formulation) which determines which finger to use for each of the n digits so as to minimize the sum of the total distance traveled by both fingers. Assume that the distance between two buttons i and j is given by the 11.4. EXERCISES 167 function dist(i, j). You should first give the recursive formulation, clearly explaining what the subproblems are. Then devise two efficient algorithms that implements your recursive formulation — a recursive algorithm (using top-down, lookup strategy) and an iterative (DP, bottom-up strategy). Analyze the running time of your algorithms.

Explanation / Answer

ANS:-

Given that,

  you want to dial a telephone number consisting of n digits on a standard 12-button telephone keypad, using the index fingers of both hands. Assuming both fingers start over the 1 button, devise an O(n) time algorithm using dynamic programming (in particular, give the recursive formulation) which determines which finger to use for each of the n digits so as to minimize the sum of the total distance traveled by both fingers

solution

Take a 3d array of dimension (n+1)*12*12. Call it DP.

ijk th entry of DP denotes : DP[i][j][k] = Min distance moved by both the fingers when the first finger is at key (j+1) and second finger is at key (k+1) to dial a number containing digits i to n of the original number.

Now we have the recursion formula:

Suppose we have dialed some digits and t is the next digit we have to dial.

DP[i][j][k] = Min( [DP[i+1][t][k] + dist(j,t)] , [DP[i+1][j][t] + dist(k,t)] )

We do this for all values of j and k.

Now filling the array in reverse order of its first dimension our answer would be the DP[1][1][1].

Runtime of the algorithm : to fill all values of j and k for particular value of i time taken is 12*12*c. Hence total runtime is 144*c*n.

Complexity = O(n).

please do like it :). if you have any doubts reply me back, im always here to help you ..

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.