Note: Algorithm should be written as Pseudo-code and finding the optimal solution for part(b) should be written out steps and solution.

5) There is an s miles long road, with n possible locations for advertisements at distances di,...,dn from the beginning of the road. Putting an advertise- ment at the i'th location brings in revenue p Two advertisements cannot be located closer than distancel from each other. Find a set of locations for the advertisement bringing in maximal revenue. a) Design a dynamic programming algorithm for this problem. b) Use your algorithm to find the optimal solution for distances 5, 9, 17, 23 revenues 4, 8, 6, 1 and distance 10. Hint: Let r, be the maximal revenue achievable by locations on the first j miles stretch of the road. For every j, let prev(i) be the location preceding d, which is at least distance l from the j'th location. Determine an optimal- ity relation for r, involving these quantities and use it to design a dynamic programming algorithm