Tuesday, November 12, 2013

Maximum value in a Sliding Window

Problem Statement
Question: A long array A[] is given to you. There is a sliding window of size w, which is moving from the very left of the array to the very right. You can only see the w numbers in the window. Each time the sliding window moves rightwards by one position.

Example:
The array is [1 3 -1 -3 5 3 6 7], and w is 3.
Window position                Max 
---------------               ----- 
[1  3  -1] -3  5  3  6  7       3  
1  [3  -1  -3] 5  3  6  7       3  
1  3  [-1  -3  5] 3  6  7       5  
1  3  -1  [-3  5  3] 6  7       5  
1  3  -1  -3  [5  3  6] 7       6  
1  3  -1  -3  5  [3  6  7]      7

Input: A long array A[], and a window width w
Output: An array B[], B[i] is the maximum value of from A[i] to A[i+w-1]

Example 2
arr[] = {1, 2, 3, 1, 4, 5, 2, 3, 6}
w= 3
Output :
3 3 4 5 5 5 6

Solution

Method 1: Brute force

The obvious solution with run time complexity of O(nw) is definitely not efficient enough. Every time the window is moved, we have to search for the maximum from w elements in the window.
Code(Java):
void windowMaxBrute(int arr[], int w)
{
    int j, max;
    int n = arr.length;
    int b[] = new int[arr.length];
    int k=0;//tracker for array b
    for (int i = 0; i <= n-w; i++)
    {
        max = arr[i];
    
        for (j = 1; j < w; j++)
        {
            if (arr[i+j] > max)
                max = arr[i+j];
        }
        b[k] = max;
    }
}

Time complexity - O(n)
Can we do better?

Method 2z : Using Heap (will not work)


Of-course we can do better.  The word max value rings the bell in our head - we can use priority queue?

A heap data structure quickly comes to mind. We could boost the run time to approximately O(n lg w) (Note that I said approximately because the size of the heap changes constantly and averages about w). Insert operation takes O(lg w) time, where w is the size of the heap. However, getting the maximum value is cheap, it merely takes constant time as the maximum value is always kept in the root (head) of the heap.

As the window slides to the right, some elements in the heap might not be valid anymore (range is outside of the current window). How should you remove them? You would need to be somewhat careful here. Since you only remove elements that are out of the window’s range, you would need to keep track of the elements’ indices too. Finding the element to delete in the heap, will take O(w) and O(lgW) time for heapify operation. So, time complexity for n elements, will be again O(n*(w+lgw)) = O(nw), which is same as brute force.

But there are couple of solutions. Lets discuss them one by one. Can we use similar structure to heap, like priority queue?

Method 2a - Maximal value in a queue

A window can be viewed as a queue. When it slides, a number is pushed into its back, and its front is popped off. Therefore, the problem is solved if we can get the maximal value of a queue. There are no straightforward approaches to getting the maximal value of a queue. However, there are solutions to get the maximal value of a stack, which is similar to the solution introduced in the blog “Stack with Function min()”. Additionally, a queue can also be implemented with two stacks (details are discussed in another blog “Queue implemented with Two Stacks”).  If a new type of queue is implemented with two stacks, in which a function max() is defined to get the maximal value, the maximal value in a queue is the greater number of the two maximal numbers in two stacks. Lets call this queue QMax.
Here are the steps:
  1. Enqueue w elements into the QMax. Time complexity = O(w)
  2. Get the max element from the QMax, and print it, which takes constant time. O(1)
  3. Dequeue element from QMax. O(1)
  4. Enqueue next element in QMax, O(1)
  5. Repeat step 2, 3, 4 until we reach end of array.
Time complexity = O(w + n+n+n) = O(n+w) This solution is workable. However, we may not have enough time to write all code to implement our own queue and stack data structures during interviews. Let us continue exploring a more concise solution.

Method 2b - Saving the maximal value into the front of a queue

Instead of pushing every numbers inside a sliding window into a queue, we try to push the candidates of maximum only into a queue.

Let us take the array {2, 3, 4, 2, 6, 2, 5, 1} as an example and window size as 3 to analyze the solution step by step.

  • The first number in the array is 2, we push it into a queue. 
  • The second number is 3, which is greater than the previous number 2. The number 2 should be popped off, because it is less than 3 and it has no chance to be the maximal value. There is only one number left in the queue when we pop 2 at the back and push 3 at the back. 
  • The operations are similar when we push the next number 4. There is only a number 4 remaining in the queue. Now the sliding window already has three elements, we can get the maximum value at the front of the queue.
  • We continue to push the fourth number i.e. 2.  It is pushed at the back of queue, because it is less than the previous number 4 and it might be a maximal number in the future when the previous numbers are popped off. There are two numbers, 4 and 2, in the queue, and 4 is the maximum. 
  • The next number to be pushed is 6. Since it is greater than the existing numbers, 4 and 2, these two numbers can be popped off because they have no chance to be the maximum. Now there is only one number in the queue, which is 6, after the current number is pushed. Of course, the maximum is 6.  
  • The next number is 2, which is pushed into the back of the queue because it is less than the previous number 6. There are two numbers in the queue, 6 and 2, and the number 6 at the front of the queue is the maximal value. 
  • It is time to push the number 5. Because it is greater than the number 2 at the back of the queue, 2 is popped off and then 5 is pushed. There are two numbers in the queue, 6 and 5, and the number 6 at the front of the queue is the maximal value. Now let us push the last number 1. It can be pushed into the queue. 

  It is noticeable that the number at the front is beyond the scope the current sliding window, and it should be popped off.  How do we know whether the number at the front of the queue is out of sliding window? Rather than storing numbers in the queue directly, we can store indices instead. If the distance between the index at the front of queue and the index of the current number to be pushed is greater than or equal to the window size, the number corresponding to be the index at the font of queue is out of sliding window.

The analysis process above is summarized in Table 2.
Step Number to Be Pushed Numbers in Sliding Window Indices in queue Maximum in Window
1 2 2 0(2)
2 3 2, 3 1(3)
3 4 2, 3, 4 2(4) 4
4 2 3, 4, 2 2(4), 3(2) 4
5 6 4, 2, 6 4(6) 6
6 2 2, 6, 2 4(6), 5(2) 6
7 5 6, 2, 5 4(6), 6(5) 6
8 1 2, 5, 1 6(5), 7(1) 5
Table 2: The process to get the maximal number in all sliding windows with window size 3 in the array {2, 3, 4, 2, 6, 2, 5, 1}. In the column “Indices in queue”, the number inside a pair of parentheses is the number indexed by the number before it in the array.

Code (c++)
We can implement a solution based on the analysis above. Some sample code in C++ is shown below, which utilizes the type deque of STL.

 vector<int> maxInWindows(const vector<int>& numbers, int windowSize)
{
    vector<int> maxInSlidingWindows;
    if(numbers.size() >= windowSize && windowSize > 1)
    {
        deque<int> indices;

        for(int i = 0; i < windowSize; ++i)
        {
            while(!indices.empty() && numbers[i] >= numbers[indices.back()])
                indices.pop_back();

            indices.push_back(i);
        }

        for(int i = windowSize; i < numbers.size(); ++i)
        {
            maxInSlidingWindows.push_back(numbers[indices.front()]);

            while(!indices.empty() && numbers[i] >= numbers[indices.back()])
                indices.pop_back();
            if(!indices.empty() && indices.front() <= i - windowSize)
                indices.pop_front();

            indices.push_back(i);
        }
        maxInSlidingWindows.push_back(numbers[indices.front()]);
    }

    return maxInSlidingWindows;
}

Method 2c - Another solution to get the maximum of a queue

As we mentioned before, a sliding window can be viewed as a queue. Therefore, we can implement a new solution to get the maximal value of a queue based on the second solution to get the maximums of sliding windows.

The following is the sample code:

 template<typename T> class QueueWithMax
{
public:
    QueueWithMax(): currentIndex(0)
    {
    }

    void push_back(T number)
    {
        while(!maximums.empty() && number >= maximums.back().number)
            maximums.pop_back();

        InternalData internalData = {number, currentIndex};
        data.push_back(internalData);
        maximums.push_back(internalData);

        ++currentIndex;
    }

    void pop_front()
    {
        if(maximums.empty())
            throw new exception("queue is empty");

        if(maximums.front().index == data.front().index)
            maximums.pop_front();

        data.pop_front();
    }

    T max() const
    {
        if(maximums.empty())
            throw new exception("queue is empty");

        return maximums.front().number;
    }

private:
    struct InternalData
    {
        T number;
        int index;
    };

    deque<InternalData> data;
    deque<InternalData> maximums;
    int currentIndex;
};



Since this solution is similar to the second solution to get maximums of sliding windows, we won’t analyze the process step by step, and leave it as an exercise if you are interested.

Method 3 - Use Self-Balancing BST

This is similar to 2z.
  1. Pick first k elements and create a Self-Balancing Binary Search Tree (BST) of size w.
  2. Run a loop for i = 0 to n – w
    1. Get the maximum element from the BST, and print it.
    2. Search for arr[i] in the BST and delete it from the BST.
    3. Insert arr[i+w] into the BST.
This solution is similar to 2z(using heap), but note that delete is less costly operation, as instead of O(w), we will be taking O(lg w).

Time Complexity:
Time Complexity of step 1 is O(w lg(w)).
Time Complexity of steps 2(a), 2(b) and 2(c) is O(Logk). Since steps 2(a), 2(b) and 2(c) are in a loop that runs n-k+1 times, time complexity of the complete algorithm is O(wLogw + (n-k+1)*Logw) which can also be written as O(nLogw).

Method 4 - Usint Dequeue

This method is similar to method 2b.
We create a Dequeue, Qi of capacity w, that stores only useful elements of current window of w elements. An element is useful if it is in current window and is greater than all other elements on left side of it in current window. We process all array elements one by one and maintain Qi to contain useful elements of current window and these useful elements are maintained in sorted order. The element at front of the Qi is the largest and element at rear of Qi is the smallest of current window.
Code(java)

void windowMaxDeque(int arr[],  int w)
{
    // Create a Double Ended Queue, Qi that will store indexes of array elements
    // The queue will store indexes of useful elements in every window and it will
    // maintain decreasing order of values from front to rear in Qi, i.e., 
    // arr[Qi.front[]] to arr[Qi.rear()] are sorted in decreasing order
    Deque <Integer > Qi = new Deque < >(w);
    
    int n = arr.length;
    // Process first w (or first window) elements of array 
    int i;
    for (i = 0; i  < w; ++i)
    {
        // For very element, the previous smaller elements are useless so
        // remove them from Qi
        while ( (!Qi.empty()) && arr[i]  >= arr[Qi.back()])
            Qi.pop_back();  // Remove from rear
 
        // Add new element at rear of queue
        Qi.push_back(i);
    }
 
    // Process rest of the elements, i.e., from arr[w] to arr[n-1]
    for ( ; i  < n; ++i)
    {
        // The element at the front of the queue is the largest element of
        // previous window, so print it
        cout  < < arr[Qi.front()]  < < " ";
 
        // Remove the elements which are out of this window
        while ( (!Qi.empty()) && Qi.front()  <= i - w)
            Qi.pop_front();  // Remove from front of queue
 
        // Remove all elements smaller than the currently
        // being added element (remove useless elements)
        while ( (!Qi.empty()) && arr[i]  >= arr[Qi.back()])
            Qi.pop_back();
 
         // Add current element at the rear of Qi
        Qi.push_back(i);
    }
 
    // Print the maximum element of last window
    System.out.println(arr[Qi.front()]);
}
 
// Driver program to test above functions
public static void main(String[] args)
{
    int arr[] = {12, 1, 78, 90, 57, 89, 56};
    int w = 3;
    windowMaxDeque(arr, w);
}

Please suggest, if you have some other methods.
Source

Saturday, November 9, 2013

Container With Most Water

http://n00tc0d3r.blogspot.in/2013/02/container-with-most-water.html

Maximum Area Rectangle in Histogram using linear search via stack of incomplete sub problems

We have already discussed lots of solution to solve this here, and using the stack to achieve is one of them.

Problem
Question: Find the maximum rectangle (in terms of area) under a histogram in linear time. I mean the area of largest rectangle that fits entirely in the Histogram.

(Please refer figures before code section for clarity. If I include bar i completely, those figure will tell how much maximum area rectangle I can get.)

Consider the histogram below:
Hieghts = { 6,2,5,4,5,1,6}

Max area of the rectangle:

Max area = 4 * 3 = 12



This problem seems like container-with-most-water problem discussed here. But the difference is that we are not using two "wood boards" to make a bucket, but using several boards with different heights.

Brute force solution

A straightforward answer is to go for each bar in the histogram and find the maximum possible area in histogram for it. Finally find the maximum of these values. This will require O(n^2) time but this will be huge if we have a big histogram with thousands of bars. 




Solution with Stack
Here we will use stack (of-course it rings the bell that recursive solution is also possible).

 Time complexity here will be O(n) as we will see. Though as discussed here, there are many better solutions available.

Here we process the elements from left to right order, and maintain a stack of information about started but yet unfinished histograms.The point of this algorithm is to maintain a stack where higher element is always greater or equal to the lower element. Why do we need to maintain that kind of stack? Because if we have a non-decreasing list, we can easily calculate the maximum area in one scan.

We just need to compare: height[i] * (n – i) for every i. (It will be clear in sometime).
So how do we maintain this stack? If we keep seeing larger element, we just need to push them onto the stack. If we see a smaller (compared to the top element on the stack) element, we need to do two things:
  1. Pop the stack until we can maintain the non-decreasing order. Pushing the smaller element for m times, where m = number of popped elements.
  2. Keep track of the maximum area that cause by those pop.
For example, we have height = {1,3,5,7,4}.
We push onto the stack for {1,3,5,7} then we see 4. 4 is less than 7, so we need to pop. We stop popping until we see 3. However many times we pop, we push 4 onto the stack. Therefore the resulted stack would be {1,3,4,4,4}. Because of popping 7, we need to remember that the maximum area that contains 7 is 7. The largest area that contains 5, the other element which get popped, is 10. So we take that down. We then finish processing all the elements in the original array and end up with a non-decreasing stack {1,3,4,4,4}. We can compute the largest area of this stack, which is 4*3 = 12. Since 12 is larger than the previous largest, 10, we output 12.


Code in java
public int largestRectangleArea(int[] height) {
    Stack<Integer> stack =
        new Stack<Integer>();
    int max = 0;
    int i = 0;
    while(i < height.length) {
        if(stack.isEmpty() ||
            height[i] >= stack.peek()) {
            stack.push(height[i]);
            i++;
        }
        else {
            int count = 0;
            while(!stack.isEmpty() &&
                stack.peek() > height[i]) {
                count++;
                int top = stack.pop();
                max = Math.max(max, top * count);
            }
            for(int j = 0; j < count + 1; ++j) {
                stack.push(height[i]);
            }
            i++;
        }
    }
     
    int count = 0;
    while(!stack.isEmpty()) {
        count++;
        max = Math.max(max, stack.pop() * count);
    }
    return max;
}

Dry running the code



Sources
http://tech-queries.blogspot.in/2011/03/maximum-area-rectangle-in-histogram.html
http://blog.theliuy.com/largest-rectangle-in-histogram/
http://tianrunhe.wordpress.com/2012/07/26/largest-rectangle-in-histogram/



Tuesday, November 5, 2013

Maximum weight independent set (WIS) graph problem using DP

Input - A path graph G = (V,E)
with non - negative weights on vertices

eg.Consider the graph with vertex weights - 1,4,5,4


Desired output - subset of non-adjacent vertices - an independent set of maximum total weights.

Solutions
Brute force
polynomial time, so lets do better.

greedy approach
Greedy algos are easy to implement but are sometimes not correct. To apply greedy approach here we have to iteratively choose the max-weight vertex not adjacent to any previously chosen vertex.

So, in the graph above, greedy will fail. Why?
To begin with greedy algo will pick the most weighted vertex, with weight 5, and as it picks 5 it is blocked on both side to pick any other vertex i.e vertices with weight 4 and 4, but it picks 1, which leads to total cost of 6, which is incorrect.

 A divide and conquer approach

We divide the path graph in 2 , so max in 1st part is 4 and max in 2nd part is 5, and now as the recursion is complete, we merge back the solution, but OOPS, the nodes are adjacent, which is again incorrect. As the graph is small, we can think of some way of avoiding this, but in very very big graphs, it will make it very complicated. So, greedy is myopic in this sense.

So, all the paradigms have failed till now, but lets see if Dynamic programming can be of any help.

Dynamic programming
Lets now work on dynamic programming.

Dynamic Programming
Critical step - Reason about structure of an optimal solution.

Motivation - This thought experiment narrows down the set of candidates for the optimal solution, can search through small set using brute force search.So, we have to think that we do have optimal solution, i.e. guessing and finally get that solution.


Notation - Let S ⊆ V be a max-weight independent set (WIS)
Let vn = last vertex of path (i.e. the rightmost vertex).

Case1 - vn  is excluded from optimal solution S
Suppose vn  is excluded from optimal solution S.  ie. vn ∉ S.
Let G' = G with vn deleted.

Note : S also an IS of G'.
Note : S must be a max weight IS of G' - if S* was better it would also be better than S in G [contradiction]

Case 2 - Suppose vn ∈ S ..i.e. S does include vn
Note - previous vertex vn-1 ∉ S due to adjacency rule.

Let G'' = G with vn-1 , vn deleted

Note : S - {vn} is an IS of G''.
Must in fact be a max weight IS of G'' - if S* is better than S, in G'' , then S* U {vn} is better than S in G [contradiction]

We did all this because - the optimal solution is to select the case where either vn is there or its not there. So, lets take either case, and see whichever is better. So, if vn is not included, than we have to search for WIS in G' and if it is included we have to search for WIS in G''. This is kind of brute force, but it is far better.

So, now we have a thought process, we have to come up with algorithm.
If we knew whether or not we exclude the last vertex vn from the optimal solution, because optimal soluton depends on it. So, the optimal solution can have 2 possibilities - either it excludes the final vertex or the last vertex and get max WIS from G' or it includes the last vertex then it gets WIS from G''.

So, if we somehow knew which case we are in,we can just solve this by recursing on rest of the graph based on the case.But there is no way to find this way, so lets resort to brute force. We apply crazy solution that we can compute the solution recursively going into both cases and choosing the path which gives the better result.

Proposed algorithm
Now suppose we apply crazy solution that we can compute the solution recursively going into both cases and choosing the path which gives the better result.

  Recursively compute S1 = max-wt IS of G'
  Recursively compute S2 = max-wt IS of G''
  return S1 or S2 U {vn} - whichever is better


Good news - It will work.
Bad news    - So, this looks like a brute force, as we are going through almost all vertices, hence takes exponential time.

The $64000 Question(Moving towards memoization)
So, this brings us to important question - Over these exponentially many recursive calls, how many distinct sub-problems are ever get solved by this algorithm? Answer is θ (n).

So, even if there are exponential calls, we have to solve only distinct  θ (n) sub problems.

This is because when we start from right vertex, we will be taking it or leaving it, then we will skip 1 vertex and like wise go through till we pluck all the vertices. So, in first recursive call you may pluck out one vertex from the right, and 2nd recursive call you may pluck out 2, but both from the right. So, we always pluck the vertex from the right.

So, we have to remove the redundancy, as we dont have to solve the same problem more than once. So, we will be using a technique called - memoization, where we will cache the sub problem as soon as we see it.

So, we have to see if we have seen that problem earlier, just skip but if we not then just go recursively and solve it.

But more better way is to shun this top down recursion, and accept bottom up iterative algorithm.

Let Gi is the subset of G, containing 1st i vertices of G

Plan - Populate array A bottom up, i.e. left to right with A[i] = IS of Gi

Initialization : A[0] = 0 and A[1] = w1

Main loop : For i = 1, 2, ...,n   {

                      A[i] = max (A[i-1] , A[i-2]+wi)
(max of case 1 or case 2)

This is same as recursive , only thing is it skips the redundant cases. Also, note that this algorithm gives us the max weight in the array element A[n] and not the solution containing the vertex path.
    Time complexity: O(n)
    Applying this algorithm on above problem
    So, our path graph is 1,4,5,4 :

     So, as initialization we will have A[0] = 0 and A[1] = w1 = 1. Our array looks like:
    Now,A[2] = max ( A[i-1], A[i-2]+w2) , where i = 2
    A[2] = max( 1, 0 + 4) = 5.
    Similarly we go on and array becomes:
    So, here we have got 8 as the maximum value, as it is the max value(if we take vertices b and d, with weights 4 and 4). So, we notice here that the algorithm gives us optimal value and  not the optimal solution.



    Getting the Optimal solution from the Optimal value
     We can do 2 things to get optimal solution:
    1. Put in the optimal solution value at the time of construction [Not recommended, hence we didnt do the same in algorithm above]
    2. Reconstruct the path as and when required using array A which we created in algorithm above.
     So, lets follow point 2. How to trace back? Key point - We know that vertex vi belongs to max weight IS of Gi. So, our last element in the array is either included in optimal solution or not. So, if last element is higher than element just before it, then it is included and similarly for other elements.
    Let A = filled in array A
    i = n
    Let S = {}
    
    while i>=1{
       if(A[i-1]>=A[i-2])
          decrease i by 1
       else
          add vi to S, 
          decrease i by 2
    
    return S
    

    Running time : O(n)

    Now we can define dynamic programming.Key ingredients of dynamic programming:
    1. Identify a small number of sub problems
      eg. compute the max-weights IS of Gi, for i=0,1,2,...n
    2. Quickly and correctly solve "larger" sub problems given solutions to "smaller sub problems"
      usually via recurrence such as A[i] = max(A[i-1],A[i-2]+wi)

    Sequence Alignment using Dynamic Programming

    Problem :
    Input :
    2 strings or sequence of characters i.e. X = x1x2...xm, Y = y1y2...yn

    Goal - To define the similarity matrix between the 2 sequences with best alignment. This is based on penalty score, called Needleman/Wunsch score.

    Eg. consider the sequence - AGGGCT and AGGCA , best alignment here is:
    AGGGCT
     |  |  |      |
    AGG - CA

    Penalty
    Penalty = penalty of match+penalty of difference + penalty of space

    In the problem all the penalties are given.


    For this example, the two sequences to be globally aligned are G A A T T C A G T T A (sequence #1)
    G G A T C G A (sequence #2)
    So M = 11 and N = 7 (the length of sequence #1 and sequence #2, respectively)
    A simple scoring scheme is assumed where
    • Si,j = 1 if the residue at position i of sequence #1 is the same as the residue at position j of sequence #2 (match score); otherwise
    • Si,j = 0 (mismatch score)
    • w = 0 (gap penalty) 
    Applying the DP
     Now lets apply the DP here. Suppose X is x1x2...xm, and Y=y1y2...yn. In this case, the last array position can have 3 possibilities (in top and bottom sequence respectively):
    1. xm and yn are aligned
    2. xm is aligned with space / gap
    3. space / gap  is aligned with yn
    (Note that space cannot align with space, as it will be useless)

    Optimal substructure
    Let X' = X- {xm} , Y' = Y - {yn}
    If case 1  holds, then induced alignment of X' and Y' as X' and Y' are of same size.
    Similarly for case 2 and case 3.

    Relevant sub problems 
    Here sub problems get smaller, by plucking the characters from either 1st string or 2nd string or both. Hence we need to track how many characters we have plugged, and hence we need 2D array to keep track tof 2 things.


    Optimal solution for penalty:
    Let P denotes the Penalty here.
    Lets consider the case 1 - xm and yn are aligned
    Mij = Sij  + M(i-1)(j-1)

    Case2 - xm is aligned with space / gap
    Mij = w + M(i-1,j)

    Case 3 - space / gap  is aligned with yn
    Mij = w + M(i,j-1)

    Mi,j = MAXIMUM[
         Mi-1, j-1 + Si,j (match/mismatch in the diagonal),
         Mi,j-1 + w (gap in sequence #1),
         Mi-1,j + w (gap in sequence #2)]
     
    In case the penalties are such that we are given penalty Sij of mismatch is higher than penalty of match, then we have to use minimum function.
     
    Three steps in dynamic programming
    1. Initialization
    2. Matrix fill (scoring)
    3. Traceback (alignment)
    Initialization Step-edge cases
    The first step in the global alignment dynamic programming approach is to create a matrix with M + 1 columns and N + 1 rows where M and N correspond to the size of the sequences to be aligned.
    Since this example assumes there is no gap opening or gap extension penalty, the first row and first column of the matrix can be initially filled with 0.(Note in normal problem if Sgap is not 0, then use it some as i.gap)


    Matrix Fill Step

    One possible (inefficient) solution of the matrix fill step finds the maximum global alignment score by starting in the upper left hand corner in the matrix and finding the maximal score Mi,j for each position in the matrix. In order to find Mi,j for any i,j it is minimal to know the score for the matrix positions to the left, above and diagonal to i, j. In terms of matrix positions, it is necessary to know Mi-1,j, Mi,j-1 and Mi-1, j-1.
    For each position, Mi,j is defined to be the maximum score at position i,j; i.e.
    Mi,j = MAXIMUM[
         Mi-1, j-1 + Si,j (match/mismatch in the diagonal),
         Mi,j-1 + w (gap in sequence #1),
         Mi-1,j + w (gap in sequence #2)]
    
    Note that in the example, Mi-1,j-1 will be red, Mi,j-1 will be green and Mi-1,j will be blue.
    Using this information, the score at position 1,1 in the matrix can be calculated. Since the first residue in both sequences is a G, S1,1 = 1, and by the assumptions stated at the beginning, w = 0. Thus, M1,1 = MAX[M0,0 + 1, M1, 0 + 0, M0,1 + 0] = MAX [1, 0, 0] = 1.
    A value of 1 is then placed in position 1,1 of the scoring matrix.
    Since the gap penalty (w) is 0, the rest of row 1 and column 1 can be filled in with the value 1. Take the example of row 1. At column 2, the value is the max of 0 (for a mismatch), 0 (for a vertical gap) or 1 (horizontal gap). The rest of row 1 can be filled out similarly until we get to column 8. At this point, there is a G in both sequences (light blue). Thus, the value for the cell at row 1 column 8 is the maximum of 1 (for a match), 0 (for a vertical gap) or 1 (horizontal gap). The value will again be 1. The rest of row 1 and column 1 can be filled with 1 using the above reasoning.
    Now let's look at column 2. The location at row 2 will be assigned the value of the maximum of 1(mismatch), 1(horizontal gap) or 1 (vertical gap). So its value is 1.
    At the position column 2 row 3, there is an A in both sequences. Thus, its value will be the maximum of 2(match), 1 (horizontal gap), 1 (vertical gap) so its value is 2.
    Moving along to position colum 2 row 4, its value will be the maximum of 1 (mismatch), 1 (horizontal gap), 2 (vertical gap) so its value is 2. Note that for all of the remaining positions except the last one in column 2, the choices for the value will be the exact same as in row 4 since there are no matches. The final row will contain the value 2 since it is the maximum of 2 (match), 1 (horizontal gap) and 2(vertical gap).
    Using the same techniques as described for column 2, we can fill in column 3.
    After filling in all of the values the score matrix is as follows:

    Traceback Step

    After the matrix fill step, the maximum alignment score for the two test sequences is 6. The traceback step determines the actual alignment(s) that result in the maximum score. Note that with a simple scoring algorithm such as one that is used here, there are likely to be multiple maximal alignments.
    The traceback step begins in the M,J position in the matrix, i.e. the position that leads to the maximal score. In this case, there is a 6 in that location.


    Traceback takes the current cell and looks to the neighbor cells that could be direct predacessors. This means it looks to the neighbor to the left (gap in sequence #2), the diagonal neighbor (match/mismatch), and the neighbor above it (gap in sequence #1). The algorithm for traceback chooses as the next cell in the sequence one of the possible predacessors. In this case, the neighbors are marked in red. They are all also equal to 5.


    Since the current cell has a value of 6 and the scores are 1 for a match and 0 for anything else, the only possible predacessor is the diagonal match/mismatch neighbor. If more than one possible predacessor exists, any can be chosen. This gives us a current alignment of

        (Seq #1)      A 
                      |
        (Seq #2)      A
    
    So now we look at the current cell and determine which cell is its direct predacessor. In this case, it is the cell with the red 5.

     


    The alignment as described in the above step adds a gap to sequence #2, so the current alignment is

        (Seq #1)     T A
                       |
        (Seq #2)     _ A
    
    Once again, the direct predacessor produces a gap in sequence #2.
    After this step, the current alignment is

          (Seq #1)     T T A
                           |
                       _ _ A 
    Continuing on with the traceback step, we eventually get to a position in column 0 row 0 which tells us that traceback is completed. One possible maximum alignment is :
    Giving an alignment of :
              G A A T T C A G T T A
              |   |   | |   |     | 
              G G A _ T C _ G _ _ A 
     
    An alternate solution is:
    Giving an alignment of :
              G _ A A T T C A G T T A
              |     |   | |   |     | 
              G G _ A _ T C _ G _ _ A
    

     
    There are more alternative solutions each resulting in a maximal global alignment score of 6. Since this is an exponential problem, most dynamic programming algorithms will only print out a single solution.

    Time complexity

    O(m n)
    m = size of sequence X, and n = size of Y

     

    Monday, October 21, 2013

    Application of clustering

    Informal goal - given n points [web pages images, genome fragments, etc] classify into "coherent groups"
    People in machine learning must have heard of unsupervised learning.
    Assumption
    1) As input, given a (dis) similarity measure
    2 symmetric

    examples - euclidean distance, genome similarity

    goal - same clusters => nearby

    So, coherent group has smaller distance.

    Objective function to do clustering - there are many objective functions, but we are reading max-spacing k-clusterings. 

    Max spacing  k-clustering
    Assume we know  k = number of clusters desired
    [In practice, can experiment with a range of values]

    Call points p and q seperated if they are assigned to different clusters.

    Problem statement - given a distance d and k, compute the k-clustering with maximum spacing.

    greedy algorithm

    pseudocode



    Saturday, October 19, 2013

    Minimum Spanning tree MST

    MST is used to connect a bunch of points to each other as cheaply as possible.

    Applications
    • clustering
    • networking

    Blazingly fast greedy algorithms
    There are many greedy algorithm, but we will talk about 2:
    • Prim's algo [1957, also djikstra' 1959] or Jarnic found it in 25 years earlier.
    • Kruskal's algo[1956]. Will be using union find data-structure.
    They are blazingly fast as they are almost close to linear time of number of edges:
    O( m log n) time m = edges, n=vertices OR better O (|E| log |V|)

    Problem definition
    Input - undirected graph G (V,E) .

    We assume adjacency list representations
    Ce - cost of edge e ∈ E
    Note :
    1. Its ok if edge costs are negative (opposite to djikstra's algo)
    2. We are using graph undirected graph. For directed graph, this problem is called optimal branching. Those algo are out of scope of this course

    Output - Min. cost tree T subset of E that spans all vertices.

    What do we mean by cost here?
    cost here means summing up of all the edge costs or weights.

    What do we mean by spanning tree - aka difference between spanning tree and minimum spanning tree?
    Spanning tree properties
    A sub-graph T of a connected graph G(V,E) is called a Spanning Tree if
    • T has no cycles 
    • if T includes every vertex of G i.e. V(T)=V(G)
    If |V|=n and |E|=m, then the spanning tree of G must have n vertices and hence n-1 edges.
    The resultant spanning ensure that the graph remain connected and further there is no circuit in it.

    Two algorithms for finding a spanning tree are BFS (Breadth First Search) and DFS (Depth First Search).

    Minimum spanning tree
      minimum spanning tree (MST) or minimum weight spanning tree is then a spanning tree with weight less than or equal to the weight of every other spanning tree.

    Two algorithms commonly used, Prim's algorithm and Kruskal's algorithm.


    Assumptions made

    1. G cotnains path from any 1 node to other node.
    2. Edge costs are distinct (though this is not very important as both prims and kruskal's algorithms work with non distinct edges)
    Algorithms to solve MST

    Saturday, October 5, 2013

    Binary Tree Level-Order Traversal Using Depth First Search (DFS) [Not to USE BFS]

    Given a binary tree, print out the tree in level order (ie, from left to right, level by level). Output a newline after the end of each level. Breadth First Search (BFS) is not allowed. We have already seen how to do level order traversal here.

    Example
    So consider the tree:
          1
       /    \
      2      3
     /   \   /    \
    4   5  6   7
    The BFS or level order traversal here is :
    1 2 3 4 5 6 7

    Last time we used BFS, but this time it is not allowed.

    Hint:
    Write a function call printLevel(BinaryTree *p, int level) which will print all nodes of a given level. Assume you know the height of the tree, then you can print the entire tree level by level utilizing printLevel.

    Solution:
    printLevel function can be solved using DFS. Decrement level by one as you advance to the next level. When level equals 1, you’ve reached the given level. To find the maximum height (or the max depth) of a tree, you can read my post: Maximum Height or Depth of a Binary Tree.
    void printLevel(BinaryTree *p, int level) {
      if (!p) return;
      if (level == 1) {
        cout << p->data << " ";
      } else {
        printLevel(p->left, level-1);
        printLevel(p->right, level-1);
      }
    }
     
    void printLevelOrder(BinaryTree *root) {
      int height = maxHeight(root);
      for (int level = 1; level <= height; level++) {
        printLevel(root, level);
        cout << endl;
      }
    }
    

    Further Thoughts:
    If you look carefully, you will notice that the DFS solution traverses the same node multiple times. Since BFS traverses each node exactly one time, BFS is much more efficient than DFS.
    Could you find the run time complexity for the DFS level-order traversal solution? Try to estimate as best as you can, and then find the correct answer by proving it using Math. Does your estimate fares well with the correct answer? Why?
    Answer:
    Although the DFS solution traverse the same node multiple times, it is not another order slower than the BFS solution. Here is the proof that the DFS solution above runs in O(N) time, where N is the number of nodes in the binary tree and we assume that the binary tree is balanced.

    We first compute the complexity of printLevel for the kth level:
    T(k) = 2T(k-1) + c
         = 2k-1 T(1) + c
         = 2k-1 + c
    

    Assuming it’s a balanced binary tree, then it would have a total of lg N levels.
    Therefore, the complexity of printing all levels is:
    T(1) + T(2) + ... + T(lg N)
    = 1 + 2 + 22 + ... + 2lg N-1 + c
    = O(N)
    

    Finding the maximum height of the tree also takes O(N) time, therefore the overall complexity is still O(N).

    Thanks.

    Binary Tree Post-Order Traversal - Recursive and Iterative Solution

    Consider the tree:



    To traverse a binary tree in Postorder, following operations are carried-out (i) Traverse all the left external nodes starting with the left most subtree which is then followed by bubble-up all the internal nodes, (ii) Traverse the right subtree starting at the left external node which is then followed by bubble-up all the internal nodes, and (iii) Visit the root.
    Therefore, the Postorder traversal of the above tree will outputs:
    0, 2, 4, 6, 5, 3, 1, 8, 10, 9, 7

    Recursive solution

    postorder(Node *root)
    {
      if(root)
      {
        postorder(root->left);
        postorder(root->right);
        printf("Value : [%d]", root->value);
      }
    }

    Iterative solution
    Iterative solution involves 2 stacks. So if we want to do the same thing iteratively; we just need to maintain 2 stacks child and parent. Following is the algorithm of this method:

    • Push the root node to the child stack.
    • while child stack is not empty
    • Pop a node from the child stack, and push it to the parent stack.
    • Push its left child followed by its right child to the child stack.
    • end while
    • Now the parent stack would have all the nodes ready to be traversed in post-order. Pop off the nodes from the parent stack one by one and you will have the post order traversal of the tree.

    Here is the code for the same:
    void postOrderTraversalIterativeTwoStacks(TreeNode *root)  
        {  
            if (!root) return;  
            stack<binarytree*> child;  
            stack<binarytree*> parent;  
              
            //Initialization  
            child.push(root);  
              
            while (!child.empty()) {  
                BinaryTree *curr = child.top();  
                parent.push(curr);  
                child.pop();  
                if (curr->left)  
                    child.push(curr->left);  
                if (curr->right)  
                    child.push(curr->right);  
            }  
              
            //Printing the post order traversal      
           while (!parent.empty()) {          
                cout << parent.top()->data << " ";      
                parent.pop();  
            }  
        }  
    

    Dry running the code
    Lets see a light example of how it works. Suppose we have a binary tree as shown below and we need to compute its post order traversal. It's post order traversal will be
    {A, C, E, D, B, H, I, G, F}


     Here is how the stack grows:

     Iterative solution using arrays
    void iterativePostorder(node *root) {
      struct   { 
        node *node; 
        unsigned vleft :1;   // Visited left?
        unsigned vright :1;  // Visited right?  
     }save[100];   
    
    int top = 0;   
    save[top++].node = root;   
    
     while ( top != 0 )   {       
    /* Move to the left subtree if present and not visited */  
         if(root->left != NULL && !save[top].vleft)       { 
              save[top].vleft = 1; 
              save[top++].node = root;  
              root = root->left;   
             continue; 
          }       /* Move to the right subtree if present and not visited */ 
          if(root->right != NULL && !save[top].vright )       { 
              save[top].vright = 1; 
              save[top++].node = root; 
              root = root->right; 
              continue; 
          } 
          printf("[%d] ", root->value); 
          /* Clean up the stack */ 
          save[top].vleft = 0;  
          save[top].vright = 0; 
          /* Move up */   
         root = save[--top].node;    
     } 
    }

    http://leetcode.com/2010/10/binary-tree-post-order-traversal.html

    Binary Tree In-Order Traversal - Recursive and Iterative Solution


    Consider the tree
    Inorder traversal prints the binary tree in increasing order in case of Binary Search Tree, but here we are discussing any binary tree.

    To traverse a binary tree in Inorder, following operations are carried-out :
    1. Traverse the left most subtree starting at the left external node, 
    2. Visit the root, and
    3. Traverse the right subtree starting at the left external node.
    Therefore, the Inorder traversal of the above tree will outputs:
    0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10



    Solutions

    There are 3 solutions to achieve this. One is iterative and other is recursive. As we move from recursive to iterative, stack is the obvious choice. But we also have Morris Traversal.

    Method 1 - Recursive solution

    inorder(Node *root)
    {
      if(root)
      {
        inorder(root->left);
        printf("Value : [%d]", root->value);
        inorder(root->right);
      }
    }
    
    

    Method 2 - Iterative solution using Stack

    Using Stack is the obvious way to traverse tree without recursion. Below is an algorithm for traversing binary tree using stack. See this for step wise step execution of the algorithm.
    1) Create an empty stack S.
    2) Initialize current node as root
    3) Push the current node to S and set current = current.left until current is NULL
    4) If current is NULL and stack is not empty then
         a) Pop the top item from stack.
         b) Print the popped item, set current = current.right
         c) Go to step 3.
    5) If current is NULL and stack is empty then we are done.

    Here is the code in java:
    public static <T> void InorderTraversalIterativeWithStack(
      BinaryTreeNode<T> root) {
     Stack<BinaryTreeNode<T>> s = new Stack<BinaryTreeNode<T>>();
    
     BinaryTreeNode<T> current = root;
     while (current != null) {
      s.add(current);
      current = current.left;
     }
    
     while (!s.isEmpty() && current == null) {
      current = s.pop();
      out.print(current.data+ " ");
      
      current = current.right;
      while (current != null) {
       s.add(current);
       current = current.left;
      }
     }
    
    }
    
    
    

    Let us consider the below tree for example
                1
              /   \
            2      3
          /  \
        4     5
    

    Step 1 Creates an empty stack: S = NULL

    Step 2 sets current as address of root: current -> 1

    Step 3 Pushes the current node and set current = current->left until current is NULL
         current -> 1
         push 1: Stack S -> 1
         current -> 2
         push 2: Stack S -> 2, 1
         current -> 4
         push 4: Stack S -> 4, 2, 1
         current = NULL

    Step 4 pops from S
         a) Pop 4: Stack S -> 2, 1
         b) print "4"
         c) current = NULL /*right of 4 */ and go to step 3
    Since current is NULL step 3 doesn't do anything.

    Step 4 pops again.
         a) Pop 2: Stack S -> 1
         b) print "2"
         c) current -> 5/*right of 2 */ and go to step 3

    Step 3 pushes 5 to stack and makes current NULL
         Stack S -> 5, 1
         current = NULL

    Step 4 pops from S
         a) Pop 5: Stack S -> 1
         b) print "5"
         c) current = NULL /*right of 5 */ and go to step 3
    Since current is NULL step 3 doesn't do anything

    Step 4 pops again.
         a) Pop 1: Stack S -> NULL
         b) print "1"
         c) current -> 3 /*right of 5 */ 

    Step 3 pushes 3 to stack and makes current NULL
         Stack S -> 3
         current = NULL

    Step 4 pops from S
         a) Pop 3: Stack S -> NULL
         b) print "3"
         c) current = NULL /*right of 3 */ 

    Now what if we can't use extra space. Then, we use Morris traversal.

    Method 3 - Using Morris traversal

    For BST traversal, recursion is a natural way of thought. But sometimes interviewer want to know the iterative way of traversal.
    Inorder traversal without recursion:
    Using Morris Traversal, we can traverse the tree without using stack and recursion. The idea of Morris Traversal is based on Threaded Binary Tree. In this traversal, we first create links to Inorder successor and print the data using these links, and finally revert the changes to restore original tree.
    1. Initialize current as root
    2. While current is not NULL
       If current does not have left child
          a) Print current’s data
          b) Go to the right, i.e., current = current->right
       Else
          a) Make current as right child of the rightmost node in current's left subtree
          b) Go to this left child, i.e., current = current->left


    Using Morris Traversal, we can traverse the tree without using stack and recursion. The idea of Morris Traversal is based on Threaded Binary Tree. In this traversal, we first create links to Inorder successor and print the data using these links, and finally revert the changes to restore original tree.
    1. Initialize current as root
    2. While current is not NULL
    If current does not have left child
    a) Print current’s data
    b) Go to the right, i.e., current = current->right
    Else
    a) Make current as right child of the rightmost node in current's 
       left subtree
    b) Go to this left child, i.e., current = current->left

    Here is the code in java
    //MorrisTraversal
    public static <T> void InorderTraversalIterativeWithoutStack(
      BinaryTreeNode<T> root) {
     BinaryTreeNode<T> current, pre;
     if (root == null)
      return;
     current = root;
     while (current != null) {
      if (current.left == null) {
       System.out.print(current.data + " ");
       current = current.right;
      } else {
       pre = current.left;
       while (pre.right != null && pre.right != current)
        pre = pre.right;
       if (pre.right == null) {
        pre.right = current;
        current = current.left;
       } else {
        pre.right = null;
        System.out.print(current.data + " ");
        current = current.right;
       }
      }
     }
    }
    

    Here is the tree after this algo(taken from http://articles.leetcode.com/2010/04/binary-search-tree-in-order-traversal.html):


    Comparison between Method 2 and 3


    Compared to stack based traversal this takes no extra space. Though tree is modified during traversal, it is reverted back to original.

    References
    http://leetcode.com/2010/04/binary-search-tree-in-order-traversal.html
    http://www.geeksforgeeks.org/inorder-tree-traversal-without-recursion/

    Find the rank w.r.t K - Number of nodes with value less than K

    If the rank of the BST is k, it implies how many nodes/keys are less than k.

    So, it boils down to 3 easy recursive calls
    • In the simplest case if K==node value, then whole of the let is rank of the node
    • if K < node.value then we know that rank depends on the size of left sub tree and its less than sub tree's length
    • If K > node.value then we know that we have to count full left subtree w.r.t with that node, and some nodes in right

    public int rank(int K, node x)
    {
       if(x==null) return 0;
       if(K < x.data)   return rank(K,x.left);
       else if(K > x.data)   return 1 + size(x.left) + rank(K,x.right);
       else if(K == x.data)   return size(x.left);   
    }
    


    Tuesday, September 10, 2013

    Iterators - Allowing iteration over data structures (in java)

    Many times we need to iterate over the data structures. But should we allow our clients to know the internal details of the data-structure like whether it is using array or linked list and then iterate themselves.

    Here's where java gives us the power called iterators which allows us to iterate over data structure.

    Design Challenge
    Consider the stack data structure and we want to support iteration over it on client side.

    Step 1 - Make your stack ADT implement Iterable interface.
    What is Iterable?
    has a method that returns an Iterator.
    public interface Iterable <Type>{
      Iterator <Type>l; iterator();
    }
    


    What is Iterator?
    Has methods hasNext() and next()
    public interface Iterator<Type>{
        boolean hasNext();//tells if it has more element
        Type next();      //gives the next element
        void remove();    //use at your own risk
    }
    


    What makes a data structures Iterable?
    Once the class implements Iterable interface, one can do following
    for(String s:stack)
       print (s);//print each string in stack
    

    here the stack is Stack of strings.
    Long hand code to do the same(though not needed in newer versions of java)
    Iterator <String> i = stack.iterator();
    while(i.hasNext())
    {
        String s = i.next();
        print s;
    }
    

    Now the class becomes.

    Generic data structures in java

    Suppose we have a stack of string, but later we want to use it for integers. We have to re-write the code again and again for every data type. So how can we solve this.

    Attempt 1 - Creating the stack for every data type, which is very exhaustive and needs code changes again.

    Attempt 2 - Implement a stack using Object class.
    Example

    Downside -

    • Discover type mismatch errors at run time
    • Casting has to be done at client side
    • Code looks ugly because of so many castings
    Attempt 3 - Java generics

    Evaluating postfix expression using stack

    We have seen the conversion of infix to postfix expression here. Now lets  see how to evaluate it.

    Algorithm
    1. Scan input expression from left to right
      • If scanned input is an operand, push it into the stack
      • If scanned input is an operator, pop out two values from stack. Then, perform operation between popped values and then push back the result into the stack.
    2. Repeat above two steps till all the characters are scanned.
    3. After all characters are scanned, there will be only one element in the stack, and this is the result of given expression.
    Note that here we are having operand stack, but while conversion to postfix from infix, we had operator stack.

    Pseudocode
    Here is the pseudocode for the same.

    evaluatePostfix(postfix) // Evaluates a postfix expression.
    valueStack = a new empty stack
    while (postfix has characters left to parse)
    { nextCharacter = next nonblank character of postfix
      switch (nextCharacter)
      { 
        case variable:
             valueStack.push(value of the variable nextCharacter)
             break;
      case '+': case '-': case '*': case '/': case '^':
             operandTwo = valueStack.pop()
             operandOne = valueStack.pop()
             result = the result of the operation in nextCharacter and 
                     its operands operandOne and operandTwo
             valueStack.push(result)
             break;
      default: 
           break;
      }
    }
    return valueStack.peek()
    

    Lets start with infix expression -
    2 * (3 + 5) - 6

    On post fix conversion -
    2 3 5 + * 6 -

    Here is how we will proceed
    Input token Operation Stack contents (top on the right) Details
    2 Push 2
    3 Push 2, 3
    4 Push 2, 3,5
    + Add 2,8 Pop two values: 3 and 5 and push the result 8.
    * Multiply 16 Pop two values: 2 and 8 and push the result 16.
    6 Push 14, 6
    - Subtract 8 Pop two values: 14 and 6 and push result 8
    (End of tokens) Finish 8 Pop the only value 8 and return it

    Java code
    Here is code in java
       public int calculate(String s)  
       {  
         int n,r=0;  
         n=s.length();  
         Stack a=new Stack(n);  
         for(int i=0;i<n;i++)  
         {  
           char ch=s.charAt(i);  
           if(ch>='0'&&ch<='9')  
             a.push((int)(ch-'0'));  
           else  
           {  
             int x=a.pop();  
             int y=a.pop();  
             switch(ch)  
             {  
               case '+':r=x+y;  
                  break;  
               case '-':r=y-x;  
                  break;  
               case '*':r=x*y;  
                  break;  
               case '/':r=y/x;  
                  break;  
               default:r=0;  
             }  
             a.push(r);  
           }  
         }  
         r=a.pop();  
         return(r);  
       }  
    

    Thanks.

    References

    Converting an Infix Expression to Postfix expression using a stack

    Pre-requisite - What is infix, postfix and prefix?

    Infix, Postfix and Prefix notations are three different but equivalent ways of writing expressions. 
    Postfix is also known as Reverse Polish Notation or RPN , and prefix expression is also known as Polish notation.

    Infix - Operators are written in-between their operands. eg.  A+B
    Postfix -  Operators are written after their operands.      eg.  AB+    
    Prefix - Operators are written before their operands.      eg.  +AB


    Here are more examples:
    InfixPostfixPrefixNotes
    A * B + C / D A B * C D / + + * A B / C D multiply A and B,
    divide C by D,
    add the results
    A * (B + C) / D A B C + * D / / * A + B C D add B and C,
    multiply by A,
    divide by D
    A * (B + C / D) A B C D / + * * A + B / C D divide C by D,
    add B,
    multiply by A

    Converting infix to postfix expression

    Converting and infix expression to postfix or Reverse Polish notation.
    I have used a stack ADT developed using a linked list. I prefer linked lists as memory can be allocated dynamically.
    One famous algorithm is the Shunting yard algorithm. The approach used in this article is the usual input and stack precedence comparison algorithm.
    Precedence values of stack and input characters

    Symbols Input Precedence Stack precedence
    
    +,-          1                 2
    *,/          3                 4
    $,^          6                 5
    operands     7                 8
    (            9                 0
    )            0                 -
    #            -                 -1
    

    Pseduocode
    To do so, we have to add the operator to the stack, and operands to the string expression, and whenever we find a lower priority operator, we pop out the operator with higher precedence and append to the expression. When whole string expression finishes, we get the postfix expression.

    There is an algorithm to convert an infix expression into a postfix expression. It uses a stack; but in this case, the stack is used to hold operators rather than numbers. The purpose of the stack is to reverse the order of the operators in the expression. It also serves as a storage structure, since no operator can be printed until both of its operands have appeared.

    Examples of Pseudocode

    Example 1 -  A * B + C
    Lets take a simple example - A * B + C , which should evaluate to A B * C  +
    current symbol operator stack postfix string
    1 A A
    2 * * A
    3 B * A B
    4 + + A B * {pop and print the '*' before pushing the '+'}
    5 C + A B * C
    6 A B * C +

    Example 2 - A + B * C
    A + B * C becomes A B C * +
    >
    current symbol operator stack postfix string
    1 A A
    2 + + A
    3 B + A B
    4 * + * A B
    5 C + * A B C
    6 A B C * +

    Above examples were taken from http://csis.pace.edu/~wolf/CS122/infix-postfix.htm.
    Example 3 - a/b*(c+(d-e))
    Consider the following expression -a/b*(c+(d-e))

    Suppose a=2, b = 4

    Now we do further

    Once the conversion, we can evaluate the expression using the stack again.


    Implementation in java
    Here is java program of the above:
    import java.io.*;
    
    class InfPos
    {
        private Stack stackADT;
        private String input;
        private String output = "";
        public InfPos(String in)
        {
            input = in;
            stackADT = new Stack();
        }
        public String convert()
        {
            stackADT.push('#');
            System.out.print(stackADT.Peek().item);
             
            for(int j=0; j inpPrec(ch))
                {
                    output = output + stackADT.pop().item;
                    symbol = stackADT.Peek().item;
                }
                if(stackPrec(symbol) != inpPrec(ch))
                    stackADT.push(ch);
                else
                    stackADT.pop();
            }
                     
          
            while( !stackADT.isEmpty() )
            {
                if(stackADT.pop().item != '#')
                    output = output + stackADT.pop().item;
            }
            return output;
        }
        public int stackPrec(char ch)
        {
            switch(ch)
            {  
                case '+':
                case '-': return 2;
                case '*':
                case '/': return 4;
                case '^':
                case '$': return 5;
                case '(': return 0;
                case '#': return -1;
                default: return 8;
            }
        }
        public int inpPrec(char ch)
        {
            switch(ch)
            {
                case '+':
                case '-': return 1;
                case '*':
                case '/': return 3;
                case '^':
                case '$': return 6;
                case '(': return 9;
                case ')': return 0;
                default: return 7;
            }
        }
     
    }
    class InfixToPostfix
    {
        public static void main(String[] args) throws IOException
        {
            String input, output;
            while(true)
            {
                System.out.print("Enter infix: ");
                System.out.flush();
                InputStreamReader isr = new InputStreamReader(System.in);
                BufferedReader br = new BufferedReader(isr);
                input = br.readLine();
                if( input.equals("") )
                    break;
                InfPos theTrans = new InfPos(input);
                output = theTrans.convert();
                System.out.println("Postfix: " + output + '\n');
            }
        }
     
    } 
    

    Source