Thursday, January 31, 2008

Solving algorithmic problem

There are some general techniques that I've found quite useful to come up with a solution for an algorithmic problem.

Understand the problem
1. Make sure the problem is well defined and understood. Try to rephrase the problem in different ways to double verify the understanding is correct.
2. Understand the constraints and optimization goals of the expected solution. There will be many conflicting dimensions of a solution (e.g. performance, security, scalability ... etc), knowing what can be traded off is important.
Design the solution
1. While you are thinking about the solution, try to make it visual. e.g. Sketch the solution on a whiteboard to help you think.
2. See if you can solve the problem by using a simple-minded, brute force search. Try all the possible combinations of solution to determine which one works. But get a sense of the BigO complexity analysis to judge whether the brute-force approach is feasible.
3. See if you translate the problem into a search problem. Then you can utilize existing search algorithm (e.g. hill climbing, A*, BFS, DFS ... etc) to help.
4. By exploit the nature of the problem, see if you can define your solution recursively. Assume that you already have a solution with the problem of the smaller size, can you use that to construct the current solution. e.g. Can you define F(n) based on F(n-1), F(n-2) .... etc. And also try to see if you can translate the recursive solution into an iterative one.
5. At this point, you may have found multiple solutions. Do a BigO analysis in both time and space and pick the one that aligns with your optimization goal.
Verify the solution
1. Walk through some simple examples to test out your solution, include some boundary cases in the examples to see how your solution handle those corner cases.
2. Prototype your solution. Define some measurement and instrument your prototype. Run it and compare the result with what you expect.