Zark Muckerburg, having just purchased the photo-sharing app Delaypound (DP), real- izes that with so many users creating and deleting content, he'll need a more adaptable storage array. Zark wants to support two operations: appending image data at the end of the array and deleting the image data from the end of the array when a photo is removed. In particular, he begins with an array of length one and inserts the first element into the one free space in this array. In general, if at any point Zark has a full array of length n and wants to append an element, he creates a new empty array of length n + 1, copies the n elements from the length-n array to the first n entries of this new array, and then inserts the new element into the last space. If Zark wants to delete the last element from an array of length n, he creates a new empty array of length n-1 and copies the first n-1 elements from the length-n array to the n-1 entries of this new array. Suppose that copying each element when resizing the array has a cost of 1, as does adding a single element, or deleting a single element when the array is not being resized. (a) (10 points) Calculate the cost of performing n insertions followed by n dele- tions. Given this cost, find the amortized cost per operation. (b) [10 points] Zark is unsatisfied by this nave storage method, so he puts his top engineers on the problem, and they propose an alternative solution. They suggest that, whenever the array reaches capacity, rather than being copied to a new array that is one unit longer, it can be copied to one that is twice as long. In particular, to append an element to a full length-n array, Zark can create a new empty array of length 2n, copy the n elements from the length-n array to the first n entries of this new array, and then insert the new element into the (n+1)th space. To handle deletions, the engineers suggest that an array can be shrunk if the number of elements reduces to one-half the length of the array. In particular, if the array has length n but is only populated by elements in the first +1 slots and Zark wants to delete an element, then he can create a new empty array of length, and copy the first elements from the length-n array to the entries of this new array. The engineers purport that their algorithm achieves the desired amortized (1) cost per operation. Propose an adversarial sequence of operations in which the amortized cost per operation is 12(n). (c) (25 points] Zark sees some potential to the solution that his top engineers pro- pose, but is still unsatisfied, so he recruits you to see if an amortized (1) cost per operation can truly be achieved. You, being a hardworking algorithms student, realize that although the doubling scheme for appending elements is spot-on, the halving scheme is a bit ineffective. Instead, you propose that Zark should only halve the size of the array if the number of elements reduces to one-quarter of the length of the array. In particular, if the array has length n but is only populated by elements in the first + 1 slots and one element is to be deleted, then he can create a new empty array of length, and copy the first elements from the length-n array to the first entries of this new array. Use the potential method to demonstrate that this implementation provides an amortized cost of O(1) per operation, as desired. Hint: use the potential function (m,n) = max{2m - n, -m}, where m is the current number of stored elements and n is the current capacity (length) of the array. Zark Muckerburg, having just purchased the photo-sharing app Delaypound (DP), real- izes that with so many users creating and deleting content, he'll need a more adaptable storage array. Zark wants to support two operations: appending image data at the end of the array and deleting the image data from the end of the array when a photo is removed. In particular, he begins with an array of length one and inserts the first element into the one free space in this array. In general, if at any point Zark has a full array of length n and wants to append an element, he creates a new empty array of length n + 1, copies the n elements from the length-n array to the first n entries of this new array, and then inserts the new element into the last space. If Zark wants to delete the last element from an array of length n, he creates a new empty array of length n-1 and copies the first n-1 elements from the length-n array to the n-1 entries of this new array. Suppose that copying each element when resizing the array has a cost of 1, as does adding a single element, or deleting a single element when the array is not being resized. (a) (10 points) Calculate the cost of performing n insertions followed by n dele- tions. Given this cost, find the amortized cost per operation. (b) [10 points] Zark is unsatisfied by this nave storage method, so he puts his top engineers on the problem, and they propose an alternative solution. They suggest that, whenever the array reaches capacity, rather than being copied to a new array that is one unit longer, it can be copied to one that is twice as long. In particular, to append an element to a full length-n array, Zark can create a new empty array of length 2n, copy the n elements from the length-n array to the first n entries of this new array, and then insert the new element into the (n+1)th space. To handle deletions, the engineers suggest that an array can be shrunk if the number of elements reduces to one-half the length of the array. In particular, if the array has length n but is only populated by elements in the first +1 slots and Zark wants to delete an element, then he can create a new empty array of length, and copy the first elements from the length-n array to the entries of this new array. The engineers purport that their algorithm achieves the desired amortized (1) cost per operation. Propose an adversarial sequence of operations in which the amortized cost per operation is 12(n). (c) (25 points] Zark sees some potential to the solution that his top engineers pro- pose, but is still unsatisfied, so he recruits you to see if an amortized (1) cost per operation can truly be achieved. You, being a hardworking algorithms student, realize that although the doubling scheme for appending elements is spot-on, the halving scheme is a bit ineffective. Instead, you propose that Zark should only halve the size of the array if the number of elements reduces to one-quarter of the length of the array. In particular, if the array has length n but is only populated by elements in the first + 1 slots and one element is to be deleted, then he can create a new empty array of length, and copy the first elements from the length-n array to the first entries of this new array. Use the potential method to demonstrate that this implementation provides an amortized cost of O(1) per operation, as desired. Hint: use the potential function (m,n) = max{2m - n, -m}, where m is the current number of stored elements and n is the current capacity (length) of the array