Algorithms

I wrote some cool stuff for algorithms this semester.  For each of these there’s code and written analyses.  I’m just an undergrad student, so I do make mistakes.  Let me know if you find any.

Forge

Co-written with Bion Oren.  You and your opponent each take turns putting down tanks on an undirected graph.  A tank cannot be placed immediately adjacent to a tank from another team.  What’s the maximum number of tanks you can place if you make the right moves?  The least amount of tanks you can restrict the other team to?  The highest ratio?

Not only did we develop an algorithm for this NP-hard problem, we created an AI engine that plays against the human player.

Monkey Puzzle Problem

Co-written with Bion Oren.  You’re given a square number of square tiles.  Each tile has four links (N,S,E,W).  Each link has a color (red, green, blue, orange) and a boolean value (true/false).  Can you form a square using all tiles such that each touching color is equal and each touching boolean value is unequal?

This one’s NP-hard (and probably NP-complete), so the best way is simply to put tiles down until you find a match.  The cool part about this problem is that the order in which you put the tiles down makes a big difference in the overall speed.  Finding the fastest ordering empirically is another hard problem (trying each one is n!), but we think we found the optimal ordering anyway for 3×3, 4×4,and 5×5 grids.

Tiger Problem

With help from Bion Oren.  This is a fast convex hull algorithm that has linear behavior in the average case, and n*lg[n] in the worst case. I borrowed some OSS code for this one, so it’s not all mine.  The quadrilateral optimization, however, is original as far as I know.

After I wrote this, I came up with an even faster n*lg[o] that’s simpler than Chan’s, but I need some time to analyze it before I publish it.

Election Simulator

Your program will simulate the voting habits of an impressionable town in which each person decides at the end of each day how they will vote based on the majority of voting persuasions of their immediate neighbors.  This one’s pretty straightforward, just a simple simulation.

Copyright © 2011 Drew Crawford, All Rights Reserved
Powered by WordPress