Question

Assume that you have a list of n home maintenance/repair tasks (numbered from 1 to n ) that must be done in numeric order on your house. You can either do each task i yourself at a positive cost (that includes your time and effort) of c[i] . Alternatively, you could hire a handyman who will do the next 4 tasks for the fixed cost h (regardless of how much time and effort those 4 tasks would cost you). The handyman always does 4 tasks and cannot be used if fewer than four tasks remain. Create a dynamic programming algorithm that finds a minimum cost way of completing the tasks. The inputs to the problem are h and the array of costs c[1],...,c[n] .

a) Find and justify a recurrence (without boundary conditions) giving the optimal cost for completing the tasks. Use M(j) for the minimum cost required to do the first j tasks.

b) Give an O(n) -time recursive algorithm with memoization for calculating the M(j) values.

c) Give an O(n) -time bottom-up algorithm for filling in the array.

d) Describe how to determine which tasks to do yourself, and which tasks to hire the handyman for in an optimal solution.

Answer 1

Step-by-step explanation:

(a) The recurrence relation for the given problem is :

T(n) = T(n-1) + T(n-4) + 1

(b) The O(n) time recursive algorithm with memoization for the above recurrence is given below :

Create a 1-d array 'memo' of size, n (1-based indexing) and initialize its elements with -1.

func : a recursive function that accepts the cost array and startingJobNo and returns the minimum cost for doing the jobs from startingJobNo to n.

Algorithm :

func(costArr[], startingJobNo){

if(startingJobNo>n)

then return 0

END if

if(memo[startingJobNo] != -1)

then return memo[startingJobNo];

END if

int ans1 = func(costArr, startingJobNo+1) + costArr[startingJobNo]

int ans2 = func(costArr, startingJobNo+4) + h

memo[startingJobNo] = min(ans1,ans2);

return memo[startingJobNo];

}

(c)

First, Create a 1-d array 'dp' of size, N+1.

dp[0] = 0

bottomUp(int c[]){

for i=1 till i = n

DO

dp[i] = min(dp[i-1] + c[i], dp[max(0,i-4)] + h);

END FOR

return dp[n];

}

(d)

Modifying the algorithm given in part (b) as follows to know which job to do yourself and in which jobs we need to hire a handyman.

First, Create a 1-d array 'memo' of size, n (1-based indexing) and initialize its elements with -1.

Next, Create another 1-d array 'worker' of size,n (1-based indexing) and initialize its elements with character 'y' representing yourself.

Algorithm :

func(costArr[], startingJobNo){

if(startingJobNo>n)

then return 0

END if

if(memo[startingJobNo] != -1)

then return memo[startingJobNo];

END if

int ans1 = func(costArr, startingJobNo+1) + costArr[startingJobNo]

int ans2 = func(costArr, startingJobNo+4) + h

if(ans2 < ans1)

THEN

for (i = startingJobNo; i<startingJobNo+4 and i<=n; i++)

DO

// mark worker[i] with 'h' representing that we need to hire a mechanic for that job

worker[i] = 'h';

END for

END if

memo[startingJobNo] = min(ans1,ans2);

return memo[startingJobNo];

}

//the worker array will contain 'y' or 'h' representing whether the ith job is to be done 'yourself' or by 'hired man' respectively.