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

use memcmp to compare objects?

I came across a question regarding c++, is it more efficient to use memcmp to determine equality of two objects of the same type.
This is not a question regarding efficiency at all, it's about correctness. Using memcmp to compare two objects MAY be correct sometimes, but it really depends on several factors:

1. Class alignment
2. Compiler implementation
3. Compiler configuration

You may get different results when work with different types, with different compilers. Even worse, you may get different results between two invocations in the same environment. Though it seems to be efficient, it's not reliable.

We know many compiler will align a class's members to word size for better performance, because it's harder to read or write memories at arbitrary location. So possibly, there are gaps (unused memories) between fields.

Those gaps are occupied by objects of the class, but are note directly managed through objects. The contents of these gaps are undefined. They may be what's left over since their last usage. Or they might be cleared/filled by a diligent compiler.
When you use memcmp to compare two objects, these gaps which has random bits are also taken into considertion. But this is undesired behavior and leads to uncertainty.

So, never do this unless you're 100% sure about the memory layout, compiler behavior, and you really don't care portability, and you really want to gain the efficiency.

The demo below shall show using memcmp doesn't work correctly with microsoft's c++ compiler v15.00.30729.01 and gcc v4.4.1.

#include "string.h"
// ==================================
//        Class:  Foo
//  Description:
// ==================================
class Foo
{
  public:
      Foo (): a(0), b(0), c(0){          
      };   // constructor
      int a;
      char b;
      int c;

}; // -----  end of class Foo  -----

void shuffle_stack()
{
  Foo f1;
  Foo f2;

  *((int*)(&f1.b)) = 0x87654321;
  *((int*)(&f2.b)) = 0x12345678;
}

int compare()
{
  Foo f1;
  Foo f2;

  return memcmp((void*)(&f1), (void*)(&f2), sizeof(Foo));
}

int main ( int argc, char *argv[] )
{
  int rc = 0;
  shuffle_stack();
  rc = compare();
  return 0;
} // ----------  end of function main  ----------

communicate with service on android

While doing android programming, it's a common sense to use Activity to interact with users and use Service to perform time consuming tasks (actually, such tasks are usually performed on a new thread spawned by the service). A classic example is media player. It's composed of several Activities and a playing-back Service. Through Activities, users can pick a media file to play, or control (start, pause, fast forward, set volume, etc) the playing-back Service. And the Service is responsible for playing the media file. The service can run in background even no Activity of the player application is active. It's also possible that the Service is implemented and hosted in another application other than the one where Activities are implemented.
In order to allow Activities to control the behavior of the Service, there should be an mechanism to allow they talk to each other. And by following the Process Agnostic feature of Android platform, this communication mechanism should also be able to handle Inter-Process and Inside-Process communication consistently. Such that from the upper layer application code's point of view, it's making communications between components independent of which process these components run in.
Luckily, Android has already provided such a RPC mechanism which has been briefly introduced here: Android application fundamentails - remote procedure calls. And the document Designing a Remote Interface Using AIDL also shows a tutorial about how to perform RPC.
But the documents above don't include a complete yet simple example for us to follow, so I'd like to explore how to do Inside-Process as well as Inter-Process with an example.
This example is composed of two applications. The first application (app1) will bind to a service runs in another application (app2) when a button is clicked, thus demonstrates Inter-Process communication. app2 can bind to the service too, which demonstrates Inside-Process communication.

There are two buttons on each application's Activity. First, you need to click button titled start svc to bind to service and get a reference to Binder object. Then, you can click button titled call rpc to invoke a method in service.

It's trivial to repeat the tutorial of designing remote interface. So I'd like to just post some findings during my exploration.

1. The onBind method of service should return a non-null IBinder. Otherwise, the callback function onServiceConnected won't be fired.
2. Add two aidl interface with the same name to both projects (ISvcController.aidl in our example). And the interface can be used in both projects to manipulate the IBinder object returned by the service. These two interfaces can have different member functions, but any function to be used must have the same signature and be placed at the same place (index) in these interfaces.
3. When access the service in the same process, the original IBinder returned in onBind method is passed to onServiceConnected callback method. When access the service in a different process, a proxy for the IBinder is passed to onServiceConnected callback method.
4. It's necessary to call unbindService to avoid connection leaking. This can be done upon specific event handler such as a button click. A better choice is to unbind in one of Activity's life cycle events, for example, onStop. So that the connection will be freed no matter in which way the user leaves the Activity.
   

Source Code
browse code here:
http://code.google.com/p/rxwen-blog-stuff/source/browse/#svn/trunk/android/rpc-with-service
or via command:
svn co https://rxwen-blog-stuff.googlecode.com/svn/trunk/android/rpc-with-service

windows side by side assemblies

There are times when I deployed an application on a box different from the developing box, the application failed to start with following message:
"This application has failed to start because the application configuration is incorrect. Reinstalling the application may fix this problem."
And run the application in windbg also ends in no avail. It simply complained error 14001 without hitting the ntdll!DbgBreakPoint. There should be something wrong with windows loading the application. After we manually copied msvcp90.dll and msvcr90.dll to the installation folder, it still failed.
Actually, the recommended way to solve this is provided in this msdn document. But to better understand this, we need to know what's side by side assemblies on windows. Simply put, side by side assemblies is invented to get rid of dll hell.


Traditionally, windows searches for dependent dlls in application's current directory and several predefined centric locations (e.g. c:\windows\system32) by dll name. If there are several applications use different versions of a library which is planed to be stored in centric location, there comes conflicts. This can be solved by placing dependent dll in the application's folder, but it also has disadvantages. For example, if an application depends on msvcr80.dll and make a copy of this dll in the application's installation folder. Later, microsoft releases a updated version for this dll with critical bug fixing. It would be difficult to apply this update to the application. The main idea of side by side assemblies is to allow different version of the same dll to coexist in centric location that is easier to manage.
On windows, side by side assemblies are stored in c:\windows\winsxs folder. Every assembly installed there has a folder whose name is composed of the dll name and a hash value, a manifest file and policy file(redirects application from using specified version assembly to another version) in manifest, policy folder respectively. Because different version should at least have different hash value, they don't conflict with each other.
Since windows xp or later, the application loader will take care of finding the correct dll to load. If an application enables side-by-side assemblies, the application loader will load the correct version as being specified by the application in manifest file.


Applications take advantage of side by side assemblies need to have a manifest file specifying dlls it depends on (Actually, windows doesn't allow you dynamically link against crt without manifest file). The manifest file can be embedded in the binary as resource or placed in the application local folder separately. For the latter case, the manifest file's naming convention is Executable_File_Name_With_Extension.manifest. Note that if a separate manifest file exists with a binary having embedded embedded manifest, which one takes precedence is windows version specific and may be different.

To diagnose such issue, here are some tools:
1. System event viewer
The system logs information about the assembly that it fails to locate in System Event. We can use it to find out what is missing.

2. Dependency Walker
It's the best tool for identifying if dependent dlls of an application is available on the system or not.

3. FileAlyzer Utility
It can extract and categorize information from PE file, including embedded manifest file.

4. sxstrace
sxs debugging utility. But only available on vista or later version windows.


References:
How to Debug 'The System cannot Execute the specified program' message
MSDN About Isolated Application and Side by Side Assemblies
Windows Side-by-Side Assemblies (WinSxS)

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  ---------- 

main thread in android application

In android sdk document, it's mentioned that all components(Activity, Service, etc) run on the main thread. The main thread is the thread where our code works on.
Conventionally, when talk about a Service, we think it this way:
void service()
{
while(isRunning)
{
// do something
}
}
In other words, a service is usually implemented as a infinite loop. If this is the case for android service, how can it run with other components on the same thread simultaneously?
And think about activity. It has to listen for incoming events like clicking a button, which also implies the pattern of an infinite loop. So, it's also not possible for activity to coexist with other components in the same thread as well.
In fact, components don't have their own loop, instead, they share the same main loop which is implemented in Looper. This also explains why google strongly recommends not do any long-running tasks in a component's life cycle events. Say, if we run a procedure for a long time in onBind function of a service, the main thread won't have any chance to deal with new message in the loop until the procedure finishes. The best idea is to spawn a new thread to do the task and let the main thread back to the main loop as soon as possible.
Looper is the starting point of an application. It acts as the role of message loop. It loops forever waiting for incoming messages and dispatch messages to corresponding components to handle. Upon receiving a message, the corresponding handler object's dispatchMethod will be invoked.
So, in android, a component is a object with a state machine and is able to handle all kinds of messages.

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;
}