Ex 15.4-5 of introduction to algorithms

Question:
Give an O(n squared)-time algorithm to find the longest monotonically increasing subsequence of a sequence of n numbers.

Answer:
A brute-force approach is enumerate all subsequences of the n numbers and find out a monotonically increasing one with the longest length. This algorithm has a poor exponential running time.
This problem exhibit optimal substructure and overlapping subproblems properties, and is suited for dynamic programming.

Let A denotes the array of n numbers, A[i] is the ith number of the array.
Let P{i,j} denotes problem of finding the longest monotonically increasing subsequence. So the original problem is P{1,n}.
Let S(i,j) denotes the length of longest subsequence of P{i,j}.
Let M(i,j) denotes the largest number in the longest subsequence of P{i,j}. Note for P{i,j}, there may exist several subsequence has the same longest length, M(i,j) should be the smallest one of them.

For P{1,j}, if A[j] is larger than M(1,j-1), then S(1,j) equals S(1,j-1) plus 1. Otherwise, it equals S(1,j-1).
So, we have:
  S(1,j) = S(1,j-1) if A[j] <> M[1,j-1]

The complicated thing in this procedure is how to maintain M's value correctly. The idea is if A[j] is larger than M(1,j-1), M(1,j) should be A[j]. If A[j] is smaller than M(1,j-1), M(1,j) should either be M(1,j-1) or A[j] if A[j] is larger than M(1,x) where S(1,x) is less than S(1,j-1).

This equation yields a n squared running time algorithm.

Correction:

Having done some tests, the preceding algorithm failed for this case: "8 9 1 2 3 4".  

The recursion can be performed another way. Let S(i) denotes the length of the longest subsequence that ended with item A(i). So, the relationship between a problem and its subproblem can be expressed as:

S(i) = max{ S(k)+1 } (k is between 0 and i -1) that all k satisfies A[k] is less than A[i]

And the final result is the largest one of array S.

Source code for this solution is here:

http://code.google.com/p/rxwen-blog-stuff/source/browse/trunk/algorithm/i2a_ex_15.4-5/ex15_4_5.cpp

Ex 10.4-3 of introduction to algorithms

Question:
Write an O(n)-time nonrecursive procedure that, given an n-node binary tree, prints out the key of each node in the tree. Use a stack as an auxiliary data structure.

Answer:
This isn't a difficult question. But the skill of turning a recursive algorithm to non-recursive algorithm is so important, it worths a blog post.

The data structure for tree node used in this post is defined as:
  class TreeNode
  {
  public:
      int value;
      TreeNode* left; // left child node
      TreeNode* right; // right child node
  }

The simplest and cleanest algorithm for binary tree traversal is the recursion. As shown below:
  void inOrderTraversalRecursive(TreeNode* node)
  {
      if(Null == node)
          return;
      inOrderTraversalRecursive(node->left); // visit left sub-tree first
      visit(node); // visit current node
      inOrderTraversalRecursive(node->right); // visit right sub-tree
  }

In this algorithm, each time we goes down a level to the calling stack, a new stack frame will be created for the new function call. Then the context changes to the new stack frame. And the node is kept on the previous stack frame. In current stack frame, node is the left or right child of last stack frame's node. With the help of stack, after a function call is finished, the context changes back to the previous stack frame and consequently gets back to the parent node. Because this stack is managed automatically be the compiler, this algorithm becomes so simple. But this stack isn't unlimited, if the tree's height is large enough, the stack may exhaust. In order to get over this limit, we can use a heap (whose limit is far larger.) based stack data structure and manage it ourselves.

This is done in a loop. Each iteration of the loop is regarded as a function call in recursive version. At proper point of the iteration, we must push/pop node from/to stack so that the context of the iteration can be maintained.
In recursive version, if node is not null, we need to save current node in stack (push) and change node to node->left. Otherwise, the function call returns right away, which means the node is restored (pop) to the value in last call stack frame. After the left sub-tree has been visited, we visit current node.
Then we save (push) current node again and change node to node->right to visit right sub-tree. After it's done, we need to restore (pop) node. But as we can see in the recursive version, the node isn't used at all after the right sub-tree has been visited. That's to say, it's not necessary to save context before we visit right sub-tree any more. This procedure can be omitted in this case.
The last thing to determine is the termination condition. In what situation can we terminate the loop? First, it's clear that the stack should be empty when the loop terminates. But this isn't enough, the node should be null as well to terminate the loop.

  void inOrderTraversalStack(TreeNode* root)
  {
      typedef std::stack<TreeNode*> TreeStack;
      TreeStack stack;
      TreeNode *node = root;
      while(NULL != node || !stack.empty())
      {
          if(NULL != node)
          {
              stack.push(node);
              node = node->left;
          }
          else
          {
              node = stack.top();
              stack.pop();
              visit(node);
              node = node->right;
          }
      }
  }

Ex 9.3-8 of Introduction to algorithms

Question:
Let X[1 .. n] and Y [1 .. n] be two arrays, each containing n numbers already in sorted order. Give an O(lg n)-time algorithm to find the median of all 2n elements in arrays X and Y.

Answer:
Without losing generality, suppose the median z is the smaller median (there are two medians since total number is even), it's the ith element in array X. In array X, there are i-1 numbers smaller than z and n-i numbers larger than the z. Because z is the median of all 2n elements, there should be n-i numbers in Y smaller than z and i numbers larger than z.
In order to find out z, we first compare the median of X and Y. Say they are mx and my respectively. If mx is smaller than my, we compare mx and the largest element in Y that is smaller than my, say it's my2. If mx is larger than my2, then mx is z, the median of all 2n elements. Otherwise, z must be in higher half of X or lower half of Y. So, we can perform preceding logic recursively.
This algorithm works just like binary search tree whose running time is O(lg n).

The code for the algorithm is available at:
http://code.google.com/p/rxwen-blog-stuff/source/browse/trunk/algorithm/i2a_ex_9.3-8/ex9_3_8.cpp

Ex5.1-3 of Introduction to Algorithms

Question:
Suppose that you want to output 0 with probability 1/2 and 1 with probability 1/2. At your disposal is a procedure BIASED-RANDOM, that outputs either 0 or 1. It outputs 1 with some probability p and 0 with probability 1 - p, where 0 < p < 1, but you do not know what p is. Give an algorithm that uses BIASED-RANDOM as a subroutine, and returns an unbiased answer, returning 0 with probability 1/2 and 1 with probability 1/2. What is the expected running time of your algorithm as a function of p?

Answer:
If we run BIASED-RANDOM twice, we might get of of following result: 00, 01, 10, 11. And the probabilities for getting each of them is: (1-p) square, (1-p)*p, p*(1-p), p square respectively. We can see that the probabilities for getting 01 equals 10. So, if we can constraint the output to either 01 or 10, we have a UNBIASED-RANDOM that can return 01 or 10 with probability of 1/2 each. And we can simply replace 01, 10 with 0 and 1 to get desired function. How can we constraint the result in 01 and 10? We can use the similar idea used in Ex5.1-2, that's abandoning any result that doesn't belong to 01 and 10 till we get one of them.
And there's a risk in this algorithm. If p is very close to 1 or 0, we may need to try a looooot of times to get either 01 or 10 which makes a very poor performance. To get around this, we can invoke BIASED-RANDOM more times. As we know, the probability of getting a full 0 or 1 permutation is p power the number of times invoking BIASED-RANDOM. And because p is between 0 and 1, the more we invoke BIASED-RANDOM, the less will the probability be, consequently the quicker we don't get full 0 or 1.

Code:

#include "iostream"
#include "ctime"
using namespace std;
int p = 50;

int BIASED_RANDOM ()
{
  int rc = 0;
  if((rand() % 100) >= p)
      rc = 1;
  else
      rc = 0;
  return rc;
}  // -----  end of function BIASED_RANDOM  -----

int UNBIASED_RANDOM()
{
  int rc = 0;

  int temp = 0;
  int i = 0;
  while(true)
  {
      temp = 0;
      temp = BIASED_RANDOM() * 10 + BIASED_RANDOM();
      if(temp == 10 || temp == 1)
          break;
  }

  if(temp == 10)
      rc = 1;
  else
      rc = 0;
  return rc;
}

int main ( int argc, char *argv[] )
{
  if(argc > 1)
      p = atoi(argv[1]);
  srand(time(NULL));

  int rc = 0;
  for(int i = 0; i < 100; ++i)
      rc += BIASED_RANDOM();
  cout << "BIASED SUM:" << rc << endl;
  rc = 0;
  for(int i = 0; i < 100; ++i)
      rc += UNBIASED_RANDOM();
  cout << "UNBIASED SUM:" << rc << endl;
  return 0;
}    // ----------  end of function main  ---------- 

Ex5.1-2 of introduction to algorithms

A friend asked my idea about the exercise 5.1-2 of introduction to algorithms. Here is the original question:

Question:
Describe an implementation of the procedure RANDOM(a, b) that only makes calls to RANDOM(0, 1). What is the expected running time of your procedure, as a function of a and b? ( RANDOM(0,1) returns either 0 or 1 with the same probability, and RANDOM(a,b) is supposed to return any number between [a,b] with the same probability.)

First Answer: [wrong]
My initial answer which is obviously wrong is like this:

RANDOM(int a, int b)
{
int rc = a;
for(int i = 0; i < b-a; ++i)
rc += _RANDOM(0,1);
return rc;
}

But thinking it more carefully, it doesn't return every number at the same probability.

Second Answer:
The question is similar to flip coins. Each time we flip a coin, we have the same probability to get either 0 or 1. If we flip the coin for several times, the probability of getting each permutation of 0 and 1 is the same. So, if we can use each permutation to represent a distinct number between a and b, we shall get the desired RANDOM function.
How to represent a number with a serials of 0 and 1s? Binary format!
So, if we run the RANDOM(0,1) for 1+lg(b-a) times and convert the final permutation to a decimal value plus a, that's the value we want. And we need to be careful since b-a might not be exact power of 2, so we need to run RANDOM(0,1) for ceiling of 1+lg(b-a) times. But a serial of 0 and 1 of this length might represent a number exceeds b-a, we can abandon the value and restart RANDOM(a,b) till the number is smaller than b-a.
And the code is:

#include    "cmath"
#include    "iostream"
#include    "ctime"

using namespace std;
int _RANDOM()
{
   int r = rand();
   return (r%2 == 0);
}

int RANDOM(int a, int b)
{
   int rc = 0;
   int i = 0;
   // compute log2(b-a) via log10(b-a)/log10(2)
   int t = ceil(log10((float)b-a)/log10((float)2) + 1);
   unsigned int one = 0x1, zero = 0xfffffffe;
   srand(time(NULL));
   while(i < t)
   {
       rc = rc << 1;
       if(_RANDOM())
           rc |= one;
       else
           rc &= zero;
       if(i ==(t - 1)&& rc > (b-a))
       {
           rc = 0;
           i = 0; //restart loop
       }
       ++i;
   }
   return rc + a;
}

int main(int argc, char** argv)
{
   int a, b;
   cin >> a >> b;

   int r = RANDOM(a, b);
   cout << r << endl;
   return 0;
}