Glitter Store Thief Inputs: - V[1..n], an array of floating point numbers (not necessarily non-negative), where the ith entry in the array corresponds to the total value of the ith type of glitter in the store. - Q[1..n], an array of non-negative integers, where the Q[i] equals the number of quarts of the ith type of glitter in the store. - k, the number of quart ziplock bags that our thief has Return: X[1..n], an array of integers where the ith entry in the array indicates the amount of a type of glitter that is stolen, such that X that maximizes the profit for the thief. The thiefs profit is given by the following quantity: Subject to the constraints: For all , ? a) Provide a greedy algorithm that correctly solves this problem. Your solution must be written as an algorithm (not computer code). You must provide sufficient detail to clearly show how your algorithm works AND to analyze the running time of your algorithm b) Express the worst case running time of your algorithm in part 1 using big O notation. Make your bounds as tight as possible. c) Provide a proof by contradiction to argue for the partial correctness of your algorithm.

V i Qlil