Sunday, June 6, 2010

Algorithms for 8 queens problem

The 8 queens problem is a very popular puzzle especially for a Computer Science engineer. From the point of view of algorithms, there can be many approaches towards its solution. The problem statement and various solution approaches are mentioned below.


Problem: Arrange 8 queen pieces in the standard chess board so that none of the queens can take any other queens, i.e, there is no conflict in their positions.

Solution:
Approach 1: The common and straightforward solutions for the beginners is the brute force technique. Take all the arrangements of 8 pieces that can be possible and discard those that are in conflicts. It is not at all a suggested approach as its exponential if the problem is generalized to n-queens on an nxn board problem.

Approach-2: Backtracking is a common AI approach of solving problems. In this problem, we start arranging the queens column wise such that the current queens position is not in conflict with any of the previous ones. If there is a conflict in the column, we try to place it in the next available(conflict-free) column. If we run out of columns, we backtrack to the last stable arrangement and continue process from there and so on. This is actually accomplished through recursive backtracking technique.

Approach-3: Permutation Method. First a solution is found out for 8 rooks on a chess board which has only 8!=40320 possibilities. Then take each permutation and replace the pieces by queens and discard those arrangement where the queen is attacked diagonal-wise.

All solutions mentioned above produce guaranteed results. There are other heuristic based approaches which may get stuck midway.

Reference:

Stumble Upon Toolbar

Saturday, June 5, 2010

Everything about Bottleneck Spanning Tree

In this post we will take a detail look on BottleNeck Spanning Tree (BNST).
But first, lets understand the definition of BNST.
Suppose we have a graph G(V, E). Now take out all the spanning trees of G. In all the Spanning trees, the maximum weight edge is called the bottleneck edge [because this edge is some sort of bottleneck for us. The ST cost can be reduced if we reduce this edge]. Of all the spanning trees, pick the tree whose bottleneck weight is such that its the smallest of all other bottleneck weights of other trees, i.e there exist no other spanning tree which has its bottleneck value lesser than the bottleneck value of the tree you picked up.
Lets take an example. Consider the graph below. Also shown are its spanning trees.
The bottleneck edge value is 2 in each case and if I pick any tree, there exist no other tree having its bottleneck value less than 2. Hence all three spanning trees are also BNST [NOTE: the middle spanning tree is a BNST but not a MST, the other two are].
Another example can be as shown.

Consider all its spanning trees. We can notice that spanning trees can have either of AB, BD or BC edge to include the B vertex(or more than one). So 8,9,10 are the heaviest edge that one of the spanning trees can contain and among all the spanning trees, there is no spanning tree whose maximum edge weight is less than 8. So pick any spanning tree with AB edge in it and it will be a BNST. Note that BNST is only concerned with its maximum edge weight.

Problem 1: Is an MST a BNST also? Is a BNST an MST also?
Solution: There are two ways to proving this.

First, by contradiction. Lets say an MST is not a BNST i.e for graph G(V, E), lets say there is an MST, T and a BNST, T'. Assume the maximum edge in T is e and that of T' is e'.
W(e)>W(e') because T' is a BNST and its by definition of BNST that all other spanning trees have their maximum edge weight greater than that of T'. That means if I add edge e to T', it will form a cycle and the cycle will have the maximum edge as e. By the red rule, the edge e cannot belong to any MST hence its contradicting. So the MST is same as BNST.

Second, Instead of proving MST=>BNST, lets prove that ~BNST=>~MST. Assume graph G has a spanning tree T that is not a BNST. Let e be the maximum weight edge in T. Lets say e connects two trees T1 and T2. Since T is not a BNST, there exists another edge e' which also connects T1 and T2 and W(e')
T=T1+T2+e
T'=T1+T2+e', where T' is the BNST.

Sum of tree edge weights, S(T)>S(T'), so T cannot be the MST. Now T is not a BNST, implies it cannot be the MST as well. Hence proved.

The second part of the question can be proved using the counter example explained above.

Problem-2: Give an algorithm to create a BNST of a given graph G(V, E).
Solution: The solution is very simple. For this, starting with the largest edge, remove edges from G one by one. If removal of any edge disconnects G, then keep that edge and continue the process with the next edge in sequence. Continue this until all vertices are covered. Now we have a spanning tree which is a BNST. Note that it is an exact opposite of Kruskal's algorithm to find the MST of G. Moreover any MST finding algorithm is also fine because MST is a BNST as well.
Another method is, find the median edge weight and remove all edges with weight more than the median. If the remaining graph is connected recursively repeat the process. If the graph is not connected then there are connected components in the G. Shrink these components into single vertices with edges coming out is similar to original graph and reconstruct till G is connected again. Repeat the whole process till result is achieved. It is O(|E|+|V|log|V|).

Problem 3: Give a Linear time algorithm to determine if a graph G(V,E) contains a BNST with its maximum edge <= b, where b is a given constant.
Solution: We remove all the edges with weights > b from G. Then we check is G is still connected. If yes, then such a BNST is possible, else not. We can use DFS to check connectedness of G which is linear.


References:

Stumble Upon Toolbar

Friday, June 4, 2010

Algorithm: Determine the element that occurs more than n/2 times in an array of size n

Problem: An array of size n contains integers between 1 to n. You have to determine if there exists an integer which occurs more than n/2 times in the array. Also, find the element. This is also called the majority problem. One more thing, the solution has to be done in linear time and using constant extra space.


Solution: I tried real hard to think it over myself but gave up eventually. Going through the solutions posted in the web, I selected the following ones, which seemed to me more acceptable.

Despite many claims of doing it in under linear time (like logn), it is not possible to do it. I can always find a way to arrange the numbers such that one has to traverse the whole array atleast. Also, sorting is not allowed as it will make it nlogn complexity, greater than linear. O(n) sorting is possible, like radix sort but I think they donot do it in constant extra space. So here are my collected approaches.

Approach-1: A simple solution is to find the median of the integers in the array. Median can be found in O(n) time, called the Selection in Worst case in linear time. Since if an integer exists in majority, it must be the median itself. But median doesn't always guarantee that its the one. Once median is found, we need to run another traversal of array to count the number of times the median element occurs. If its more than n/2, thats the answer else return none.

Before going to next approaches, lets understand the concept of the solution. Since there is only one integer(if any) that can occur more than n/2 times in the array, the trick is every time you encounter 2 different integers adjacent to each other, make arrangements to remove them from the array, or simply pair them together and forget about them. And if adjacent numbers are equal, you continue with next integer in the row but remembering that the integer you encountered just now could be a potential majority element. If we go through this one, we are actually collecting the majority element together, and the in-between different elements are (kind of) removed by pairing them with one of the potential majority element. In other words, we are sacrificing one of the majority element to remove one of the other (different ) element. Eventually, the non-majority elements will vanish but atleast one of majority element will still exist because it is present more than half the times.

Approach-2: Take the first element, consider it as ele, the majority element, and put a mark for it. Traverse through other elements and do the following:
a. If next element in array is equal to ele, increment mark by 1.
b. If next element is not equal to ele, decrement mark by 1.
c. If mark is zero, make mark as 1 and consider the current element as ele.
When traversal is done, take the ele and perform another traversal through the array and count the number of occurrence of ele. If its more than n/2, return it as answer, else return NONE.

pseudocode:
-------------------------------------
m = 0
for (x = i..j)
if (m = 0)
m = 1
ele = A [x]
else if (A [x] = ele)
m = m + 1
else
m = m –1
endif
endfor
Another array traversal and count number of times ele occurs
if count>n/2
return ele;
else
return NULL;
------------------------------------------

Approach 3: This solution is very much similar to the one above, i.e the same concept of taking out pair of different elements out of the array and this one uses a stack to remember the previous encounters.
Create an empty stack. traverse the array and for each new element e,
a. If the stack is empty, push e into the stack.
b. If stack is non-empty, compare e with top of stack e', if both are equal, push e into the stack, else remove e' from top of stack (pop).
c. Once traversal is finished, if stack is non empty, remove the top of stack e' and do another array traversal and count the number of times e' occurs. If its more than n/2, return it as answer else return NONE.
As one can see that the stack performs the work similar to mark in the previous approach.

References:

--

Stumble Upon Toolbar