Hoc Est Qui Sumus (discoflamingo) wrote,
Hoc Est Qui Sumus
discoflamingo

The Grand Theft Auto: Vice City Algorithms Mid-Term

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.
Subscribe

  • It's Two Minutes to Midnight, If Anyone Cares

    21:27 Currently looking for a Sousa march that says "I Am a Dashing, Sexy Pirate!". How did my life end up here? #Automatically shipped by…

  • Good sing-along songs?

    O Gentle Readers! I am trying to come up with good songs to practice on my acoustic guitar. Ideally, they are the type of songs that are fun to sing…

  • It can always look up

    Remember: the man who played Richard M. Nixon in Frost/Nixon is the same man who played Skeletor in The Masters of the Universe.

  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 10 comments

  • It's Two Minutes to Midnight, If Anyone Cares

    21:27 Currently looking for a Sousa march that says "I Am a Dashing, Sexy Pirate!". How did my life end up here? #Automatically shipped by…

  • Good sing-along songs?

    O Gentle Readers! I am trying to come up with good songs to practice on my acoustic guitar. Ideally, they are the type of songs that are fun to sing…

  • It can always look up

    Remember: the man who played Richard M. Nixon in Frost/Nixon is the same man who played Skeletor in The Masters of the Universe.