?

Log in

No account? Create an account
 
 
30 November 2003 @ 04:07 am
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.
 
 
 
Josiah Carlsonchouyu_31 on December 2nd, 2003 08:45 pm (UTC)
Do you actually want the algorithms? Because I'll give them to you.
Hoc Est Qui Sumusdiscoflamingo on December 2nd, 2003 08:50 pm (UTC)
I think I already know what they'd be (Knapsack, TSP, Quicksort, etc.) - but I think the questions (so far) have very decent coverage of topics appropriate to the class at mid-term time, while still all being things that might happen in GTA. The pill-box analogy is spreading it awfully thin, but I thought I did all right. You?
Josiah Carlsonchouyu_31 on December 2nd, 2003 09:07 pm (UTC)
I think it is satisfactory.

Remember, the infinitely divisible white powder is FRACTIONAL knapsack, and is trivial to solve.
Hoc Est Qui Sumusdiscoflamingo on December 2nd, 2003 09:15 pm (UTC)
But only if you paid any attention in class, AT ALL.

If your tales are to be believed, I would throw it on as a "gimme" at Mac, and a litmus test at Irvine. But I'm probably just being a bitch. Hehe.
Josiah Carlsonchouyu_31 on December 2nd, 2003 10:01 pm (UTC)
Yeah, dynamic programming is covered in the last couple weeks out here. We do knapsack, longest common subsequence, optimal matrix chain multiplication, optimal binary search tree, and maybe one or two others. Those topics weren't covered in Wagon's algorithms class. I got to learn them in my first quarter as a TA here.
King of the Voidabaddonx99 on December 2nd, 2003 11:22 pm (UTC)
Oh, Molnar makes damn sure we know alllll of those. Wotta bastard.
Josiah Carlsonchouyu_31 on December 2nd, 2003 11:41 pm (UTC)
At least you're getting a decent algorithms education.
King of the Voidabaddonx99 on December 3rd, 2003 10:35 pm (UTC)
The thing is, I really don't feel as if I am. Becuase I find Molnar so difficult to learn from. I know others that can and do learn a lot from him, but I just can't. I write down what he's trying to impart to us, and I go home and look it up for myself. Oh well. Not much I can do about it, you know?
Hoc Est Qui Sumusdiscoflamingo on December 5th, 2003 09:44 am (UTC)
The most important things to learn in Algorithms are these:

1. Big O-Notation/Time Complexity Theory/The Master Theorem
2. A broad expanse of searching, sorting, graph, and other algorithms
3. The more important advanced data structures (b- and m-trees, red-black trees (if he covered them), heaps, advances matrices), along with their theory and application

That's what an algorithms class should really be about - if you don't feel like you understand all of those, then we can set up a time to go over some of them, since I don't want Molnar to hold you back on this.
King of the Voidabaddonx99 on December 6th, 2003 01:18 pm (UTC)
1. Ok, except for the master theorem.
2. Pretty well covered and understood.
3. No m-trees, red-black or advances matrices.

That's about where I stand in my understanding right now.