Hung Truong: The Blog!

Cooking Mama DS Sort Of On Sale At Amazon.com

So Cooking Mama, the game where a woman yells at you for not cooking well, is sort of on sale at Amazon.com. It’s usually $20, but right now it’s $16. Good enough for me! I was thinking of picking up this weird title and the 20% off convinced me.

I also picked up Nodame Cantabile volume 1 so I could get free shipping. And I used my $25 Amazon.com credit card gift certificate, so it ended up being like $.30 total! Yay!

Because The Graphics On Level 3 Aren’t Gonna Tighten Themselves Up…

Back when I still had cable, and access to G4TechTV, which is now just G4, and considerably bad, there was this awesomely bad commercial.

Two guys are playing video games when their boss walks in. Instead of yelling at the guys, she tells them she has another video game that needs designing! Oh man, they’re video game designers! And it’s their job! They just finished level 3! And they need to tighten up the graphics!

The commercial ends with the dude on the left saying that his mom said he’d never get anywhere playing video games. How wrong she was.

The phone number for Westwook College Online is then presented with a caveat: Not intended for residents of Texas or Massachusetts. Obviously these states have banned video games altogether. Or perhaps they don’t recognize dead end online degree programs? Either way, it’s nice of the college to warn people ahead of time. Maybe they should also include, “Not intended for people eventually seeking a job of any kind.”

Google Phone Interview Set For February 9th!

I got an email from the recruiter at Google today. My phone interview is set for February 9th, so I have 4 good days to get ready for it. I’ve been looking at the giant algorithms book, just refreshing myself on stuff like O notation, common sorting algorithms like mergesort, and stuff like that.

I should probably move on to more complicated algorthms next like Dijkstra’s Algorithm and dynamic programming algorithms like the all pairs shortest path algorithm. I don’t think Google would ask me about specific implmentations of these, but it would be good practice to get back into the mindset of designing algorithms this complex, since I haven’t had to do so in a while.

I saw a sample interview question from some blog asking about defining a function f(a,b) to return a string that is all of the characters in a (in order) that are also in b. They ask for an order n² as well as an order n algorithm. The n² one seems trivial, but I can’t think of how to calculate a set intersection (which is what I think the problem boils down to) in order n time… I could try and prove that it would be impossible to do it in n time, but I don’t really want to do that either. Plus I’m not sure if it is impossible…

Edit: Okay, so apparently they’re “strings” for a reason. The N solution is pretty easy. I was trying to solve a more complex problem in N, when I just needed to take a look at the actual question being asked. I guess I should do regular sanity checks during the interview and not try to accomplish more than they ask.

Well, back to the book for me.

Final Fantasy IV (6, or 3…) Out For Gameboy Advance Today!

So Final Fantasy VI is being released today for the Gameboy Advance! I remember playing this when it was known as Final Fantasy III for the SNES. I still have it, too.

Something tells me I shouldn’t buy this, since I already own this and I already beat it before. Plus I have Final Fantasy IV on the GBA which I haven’t beat yet (though I have beat it on the SNES, and I still have it!).

Couple this with the fact that I have Final Fantasy XII unbeaten, and Legend of Zelda Twilight Princess unbeaten, and I do think I have a case for not buying this. But it’s Final Fantasy VI!!!

Decisions…

Vulnerabilities In The Mechanical Turk Search For Jim Gray

I just read about a really awesome use for Amazon.com’s Mechanical Turk: finding missing people! From the Mechanical Turk’s page:

On Sunday, January 28th, 2007, Jim Gray, a renowned computer scientist was reported missing at sea. As of Thursday, Feb. 1st, the US Coast Guard has called off the search, having found no trace of the boat or any of its emergency equipment.

Follow the story here.

Through the generous efforts of his friends, family, various communities and agencies, detailed satellite imagery has been made available for his last known whereabouts.

You will be presented with 5 images. The task is to indicate any satellite images which contain any foreign objects in the water that may resemble Jim’s sailboat or parts of a boat.

Jim’s sailboat will show up as a regular object with sharp edges, white or nearly white, about 10 pixels long and 4 pixels wide in the image.

If in doubt, be conservative and mark the image. Marked images will be sent to a team of specialists who will determine if they contain information on the whereabouts of Jim Gray.

While I think it’s a really nifty and commendable idea, it bothers me how vulnerable this system is from the way I understand it. It seems to me that once an image is marked as containing a sailboat-like object, it will be sent to others for investigation. If not, it will be discarded.

In computer science, you’re trained to think as an adversary to the algorithm. While I’d hope there aren’t any people malicious enough to try and sabotage this system, it’s always worth considering the possibility. I’ve thought of a few vulnerabilities that the Mechanical Turk faces in the search for Jim Gray:

Vulnerability 1

The adversary marks each picture as not containing anything of interest, even if it does. In the case that an adversary finds the picture with the sailboat, he and he alone can invalidate it. The data is never considered and the search fails.

I’m assuming a few things about the system. The biggest assumption is that each HIT will be viewed by only one person. The Mechanical Turk doesn’t specify this. If two people are assigned to each hit, the odds of this happening are lower. Though this system can still be defeated by two adversaries working in tandem.

Vulnerability 2

The adversary marks each picture as being interesting. An overwhelming amount of data is sent to the “team of specialists” and we’re back to square one. We can’t just assume that all of the pictures flagged as interesting were not, because one could be useful.

This kind of attack seems much more malicious to me. At best, you could invalidate all of the adversary’s HITs and reassign them. This could take precious time, though, since once a HIT is taken, it is locked from other users to attempt.

Vulnerability 3

The adversary randomly marks non-interesting pictures interesting, and interesting pictures to be non-interesting.

This is probably the most malicious and the hardest to detect. While the odds of finding an interesting picture to mark non-interesting would be low, it could happen.

I can’t think of a way to combat this kind of attack, apart from having two users work on each HIT. Again, this could still be defeatable by two adversaries working together to dirty the results.

Conclusion

Even with these vulnerabilities, I think the Mechanical Turk’s search for Jim Gray is an incredible idea. I sincerely hope that they do find him. It would be a great victory for everyone involved. Please do join in the search for Jim Gray. Please don’t follow any of the adversarial techniques I mentioned!

I just hope that the people behind the Mechanical Turk are aware of these vulnerabilities, and have come up with solutions (that are better than mine) to combat any kind of malicious use that could undermine the entire project.

If you have any ideas to combat these vulnerabilities, or have any other ideas for vulnerabilities that I may have missed, please let me know in the comments. I’d be interested from a computer science sort of viewpoint.