The Grand Theft Auto: Vice City Algorithms Mid-Term
1. As a drug-runner, you have come across four bags of infinitely divisible white powder, each with a different street value per ounce ($p_1$ - $p_4$). You have a knapsack that can carry exactly k ounces of product. Describe the method you would use to carry the maximum profitable amount of product with you from the scene (assume baggies have negligible weight, and you have countably infinite baggies). Give your method's asymptotic complexity.
2. You managed to acquire a pill-box from a competitor - although none of the pills are grouped together by type. Describe a method for sorting $k$ types of pills into distinct piles. Give your method's asymptotic complexity. (Extra Credit: Prove that your method is optimal)
3. Given $p_k$ prices for the pills in problem 2, describe a general method for packing the maximally profitable amount of pills into a bag that can only carry $p$ pills. Give your method's asymptotic complexity.
4. Now that you have your product, describe the algorithm you would use to organize a round-trip distribution tour through the city to $n$ locations from a starting location $s$, given a matrix of the distances between any two destinations. You may approximate a solution if you can justify the demands on planning time for any set of locations.
5. Something with activity selection - how to schedule pimping, killing, dealing, and racing. Eh - I'm tired.
It would be Fox-style, where you could choose 5 of 7 questions. Maybe I'll come up with more tomorrow. I seriously believe that you can cover almost all of algorithms by relating them to GTA:VC.