Your friend is a competitive eater and they have solicited your help for upcoming cookie eating...

Transcribed Image Text:

Your friend is a competitive eater¹ and they have solicited your help for upcoming cookie eating competition. The rules of the contest are simple; they must eat n cookies as quickly as possible. However, the tricky part is figuring out which cookies they should eat. There are m different types of cookies, and oddly enough your friend finds that when they eat too many of one type of cookie it slows them down. Having done some practicing, they have determined for any cookie type i and any number of cookies j, how long it will take them to eat j cookies of type i. This information is stored in the form of a list C;[1,...,n] for each type of cookie i, where C:[j] is the amount of time it takes your friend to eat j cookies of type i. You observe that C;[j] is increasing with increasing j for all i. You will use dynamic programming to determine how many cookies of each type your friend should eat so that the total time it takes to eat n cookies is minimized. (a) Describe the set of subproblems that your dynamic programming algorithm will consider. Your solution should look something like "For every..., we define OPT[...] to be ...". Solution: (b) Give a recurrence expressing the solution to each subproblem in terms of the solution to smaller subproblems. Solution: (c) Using your recurrence, design a dynamic programming algorithm to output the optimal distribution of the n cookies over the m types. You may use either a top-down or bottom- up approach. Remember that your algorithm needs to output the optimal distribution of cookies. The output of your algorithm can be an array of length m where the ith entry gives the number of cookies of type i. The running time of your algorithm must be polynomial in n and m. Be sure to describe any auxiliary variables which you use. You should include both pseudocode and a description of your algorithm. Solution: (d) Analyze the running time and space usage of your algorithm. Provide brief justification of each. Your friend is a competitive eater¹ and they have solicited your help for upcoming cookie eating competition. The rules of the contest are simple; they must eat n cookies as quickly as possible. However, the tricky part is figuring out which cookies they should eat. There are m different types of cookies, and oddly enough your friend finds that when they eat too many of one type of cookie it slows them down. Having done some practicing, they have determined for any cookie type i and any number of cookies j, how long it will take them to eat j cookies of type i. This information is stored in the form of a list C;[1,...,n] for each type of cookie i, where C:[j] is the amount of time it takes your friend to eat j cookies of type i. You observe that C;[j] is increasing with increasing j for all i. You will use dynamic programming to determine how many cookies of each type your friend should eat so that the total time it takes to eat n cookies is minimized. (a) Describe the set of subproblems that your dynamic programming algorithm will consider. Your solution should look something like "For every..., we define OPT[...] to be ...". Solution: (b) Give a recurrence expressing the solution to each subproblem in terms of the solution to smaller subproblems. Solution: (c) Using your recurrence, design a dynamic programming algorithm to output the optimal distribution of the n cookies over the m types. You may use either a top-down or bottom- up approach. Remember that your algorithm needs to output the optimal distribution of cookies. The output of your algorithm can be an array of length m where the ith entry gives the number of cookies of type i. The running time of your algorithm must be polynomial in n and m. Be sure to describe any auxiliary variables which you use. You should include both pseudocode and a description of your algorithm. Solution: (d) Analyze the running time and space usage of your algorithm. Provide brief justification of each.

Answer rating: 100% (QA)

This problem can be solved using dynamic programming Lets break down the solution into the requested ... View the full answer