# just do IT

## Friday, December 4, 2009

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

`#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);  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  ---------- `