Posts

Showing posts from July, 2012

Backtracking II: equal division of batches

Suppose that you are given a set of N numbers representing stocks batches: some are positive, others are negative. The batches have the following values: {15, -3, 4, -1, -16, 5, 14, -13, 7, -6, 2, 1} Your task is to distribute these batches amongst 3 brothers. However… you need to be fair with all the brothers, hence the total dollar amount has to be exactly the same for all the brothers. First question is: is there a solution for this problem? Second: what is the solution? There are in general two approaches for solving this problem: dynamic programming or backtracking. The first one requires some constraints in terms of the values of the batches – if the batches for instance contain float numbers I’m pretty sure the dynamic programming won’t work. The second approach is the one shown in the previous blog post, which is backtracking, and to recap, here is the overall structure of backtracking solutions: Backtracking(Enumeration L, Solution S) { //Part 1 If (L is the final enume

Backtracking, knights and patterns

Another commonly used technique in Computer Science for solving algorithm problems is backtracking. Backtracking consists of recursively enumerating all the different possible solutions, and picking the best one out of all of them (in case the problem’s dealing with optimal solutions). Backtracking usually makes use of heuristics to cut/prune down the search space. In general the high-level structure of a backtracking algorithm is as follows: Backtracking(Enumeration L, Solution S) {   //Part 1   If (L is the final enumeration)     Check if S is the best one thus far   //Part 2   For each K such that K is in the neighborhood of S     Backtracking(L+1, K) } And that’s it. To exemplify backtracking I picked a chess problem: given the dimensions of a chess board (usually 8, but we’ll let the user decides which dimension) N, determine the maximum number of knights that can be safely placed on the N-board without one knight threatening any other. You will see that the solution to this

Simple Traversals in Binary Trees

A common data structure used in algorithms is a tree (which actually should have been named “pyramid” since a tree has its root at the bottom, not at the top) and traversing a tree becomes one of the fundamentals techniques in computer science. For a simple binary tree, there are basically three well-known techniques for traversing the tree: ·          Pre-Order: in which you perform some computation against the current node, then recursively perform the computation for the left and then the right nodes ·          In-Order: in which you perform some computation against the left node (recursively), then against the current node then recursively against the right node (recursively) ·          Post-Order: in which you perform some computation against the left node (recursively), then against the right node (recursively) and then against the current node The following problem can be solved with any of the traversals above: given a binary tree, determine whether the tree is a Bina