Interview Lo Okate Question Adigadu

[kissan]

fair coin output iche function use chesi.. bias function output iche program rayali anta.. bias probability vadi istamochindi enter chestadu

[littlestar]

adi em tech oo..xam thelvakunda question paper ichhinattundi

[Spartan]

[quote name='Little Star' timestamp='1359053782' post='1303167295']
adi em tech oo..xam thelvakunda question paper ichhinattundi
[/quote]


program rayi mannad anukunta..

[littlestar]

[quote name='ChittiNaidu' timestamp='1359053832' post='1303167306']


program rayi mannad anukunta..
[/quote]
edo language untadi kada...

[Guest]

nee husband nissan yetlunnad..

[kissan]

[quote name='ChittiNaidu' timestamp='1359053832' post='1303167306']


program rayi mannad anukunta..
[/quote]
yes, avnu

[kissan]

[quote name='Little Star' timestamp='1359053885' post='1303167317']
edo language untadi kada...
[/quote]
programming language edaina parvaledu.. logic chustanu annadu

[kissan]

[quote name='Guest' timestamp='1359053984' post='1303167332']
nee husband nissan yetlunnad..
[/quote]
naaku udyogam ledu ani odilesadu

[kissan]

[quote name='ChittiNaidu' timestamp='1359053832' post='1303167306']


program rayi mannad anukunta..
[/quote]
neeku ans teliste cheppachu kada.. nxt rund ki velte.. nee peru cheppukoni brathikesta

[kissan]

tech kaadu.. software engg udyogam

[SudhirKumar]

saduvu raanodini IIT exam lo kurchopettinattu..maakendhidi

[Guest]

[quote name='kissan' timestamp='1359054121' post='1303167360']
naaku udyogam ledu ani odilesadu
[/quote]


nee ferformance nachaledemo..[img]http://lh3.ggpht.com/--o7mXz3u-j4/T9VVBGzBJAI/AAAAAAAAGo0/kmj8a1-XW2g/s150/PK-1.gif[/img]

[maverickpuli]

[color=#000000][font=Arial,]
Assuming:[/font][/color]
int fairCoinToss();
[color=#000000][font=Arial,]
returns 1 for heads and 2 for tails, writing:[/font][/color]
int biasedCoinToss(int n);
[color=#000000][font=Arial,]
where heads (1) will appear 1/n of the time this should work:[/font][/color]
int biasedCoinToss(int n) {
if (n == 1) {
return 1; // 1/1 = 1 = always heads
} else if (n == 2) {
return fairCoinToss(); // 1/2 = 50% = fair coint oss
}
int r = random_number(n);
return r == 0 ? 1 : 0;
}
[color=#000000][font=Arial,]
where random_number(n) generates a fair random integer i such that 0 <= i < n. Sorandom_number(3) is 0, 1 or 2. Assuming even distribution, value 0 will come out 1/3 of the time.[/font][/color][color=#000000][font=Arial,]
Of course we can't use a native random number generator but we can create one anyway.fairCoinToss() randomly generates a 1 or 0. Multiple coin tosses can be combined to generate a larger number. For example:[/font][/color]
fairCoinToss() << 1 | fairCoinToss()
[color=#000000][font=Arial,]
will generate:[/font][/color]
00 = 0
01 = 1
10 = 2
11 = 3
[color=#000000][font=Arial,]
which by definition is a random number from 0 to 3 (n = 4).[/font][/color][color=#000000][font=Arial,]
That's fine if n is a power-of-2 but it isn't necessarily. That's easy enough to cater for however. Assume n = 5. At best we can generate a random number from 0 to 7. If you "reroll" 5, 6 or 7 until you get a number in the range of 0 to 4 then you have (non-deterministically) constructed a random number fairly distributed from 0 to 4 inclusive, satisfying the requirement.[/font][/color][color=#000000][font=Arial,]
Code for that looks something like this:[/font][/color]
int random_number(int n) {
int ret;
do {
int limit = 2;
ret = fairCoinToss();
while (limit < n) {
ret <<= 1;
ret |= fairCoinToss();
limit <<= 1;
}
} while (ret >= n);
return ret;
}

[Guest]

[quote name='maverickpuli' timestamp='1359054634' post='1303167440']

[color=#000000][font=Arial,]Assuming:[/font][/color]
int fairCoinToss();

[color=#000000][font=Arial,]returns 1 for heads and 2 for tails, writing:[/font][/color]
int biasedCoinToss(int n);

[color=#000000][font=Arial,]where heads (1) will appear 1/n of the time this should work:[/font][/color]
int biasedCoinToss(int n) {
if (n == 1) {
return 1; // 1/1 = 1 = always heads
} else if (n == 2) {
return fairCoinToss(); // 1/2 = 50% = fair coint oss
}
int r = random_number(n);
return r == 0 ? 1 : 0;
}

[color=#000000][font=Arial,]where random_number(n) generates a fair random integer i such that 0 <= i < n. Sorandom_number(3) is 0, 1 or 2. Assuming even distribution, value 0 will come out 1/3 of the time.[/font][/color]
[color=#000000][font=Arial,]Of course we can't use a native random number generator but we can create one anyway.fairCoinToss() randomly generates a 1 or 0. Multiple coin tosses can be combined to generate a larger number. For example:[/font][/color]
fairCoinToss() << 1 | fairCoinToss()

[color=#000000][font=Arial,]will generate:[/font][/color]
00 = 0
01 = 1
10 = 2
11 = 3

[color=#000000][font=Arial,]which by definition is a random number from 0 to 3 (n = 4).[/font][/color]
[color=#000000][font=Arial,]That's fine if n is a power-of-2 but it isn't necessarily. That's easy enough to cater for however. Assume n = 5. At best we can generate a random number from 0 to 7. If you "reroll" 5, 6 or 7 until you get a number in the range of 0 to 4 then you have (non-deterministically) constructed a random number fairly distributed from 0 to 4 inclusive, satisfying the requirement.[/font][/color]
[color=#000000][font=Arial,]Code for that looks something like this:[/font][/color]
int random_number(int n) {
int ret;
do {
int limit = 2;
ret = fairCoinToss();
while (limit < n) {
ret <<= 1;
ret |= fairCoinToss();
limit <<= 1;
}
} while (ret >= n);
return ret;
}
[/quote]

[maverickpuli]

[size=1]

[b] Make a fair coin from a biased coin[/b]
[/size]


[size=1]
[color=#000000][font=Helvetica, Arial, Verdana, sans-serif][size=3]
You are given a function foo() that represents a biased coin. When foo() is called, it returns 0 with 60% probability, and 1 with 40% probability. Write a new function that returns 0 and 1 with 50% probability each. Your function should use only foo(), no other library method.[/size][/font][/color][color=#000000][font=Helvetica, Arial, Verdana, sans-serif][size=3]
[b]Solution:[/b]
We know foo() returns 0 with 60% probability. How can we ensure that 0 and 1 are returned with 50% probability?
The solution is similar to [url="http://www.geeksforgeeks.org/archives/22539"]this [/url]post. If we can somehow get two cases with equal probability, then we are done. We call foo() two times. Both calls will return 0 with 60% probability. So the two pairs (0, 1) and (1, 0) will be generated with equal probability from two calls of foo(). Let us see how.[/size][/font][/color][color=#000000][font=Helvetica, Arial, Verdana, sans-serif][size=3]
[b](0, 1):[/b] The probability to get 0 followed by 1 from two calls of foo() = 0.6 * 0.4 = 0.24
[b](1, 0):[/b] The probability to get 1 followed by 0 from two calls of foo() = 0.4 * 0.6 = 0.24[/size][/font][/color][color=#000000][font=Helvetica, Arial, Verdana, sans-serif][size=3]
[i]So the two cases appear with equal probability. The idea is to return consider only the above two cases, return 0 in one case, return 1 in other case. For other cases [(0, 0) and (1, 1)], recur until you end up in any of the above two cases.[/i][/size][/font][/color][color=#000000][font=Helvetica, Arial, Verdana, sans-serif][size=3]
The below program depicts how we can use foo() to return 0 and 1 with equal probability.[/size][/font][/color][color=#000000][font=Helvetica, Arial, Verdana, sans-serif][size=3]
[size=1]
[size=1]
[size=1]
#include <stdio.h>[/size]
[size=1]
int foo() // given method that returns 0 with 60% probability and 1 with 40%[/size] [size=1]
{[/size] [size=1]
// some code here[/size] [size=1]
}[/size]
[size=1]
// returns both 0 and 1 with 50% probability [/size] [size=1]
int my_fun() [/size] [size=1]
{[/size] [size=1]
int val1 = foo();[/size] [size=1]
int val2 = foo();[/size] [size=1]
if (val1 == 0 && val2 == 1)[/size] [size=1]
return 0; // Will reach here with 0.24 probability[/size] [size=1]
if (val1 == 1 && val2 == 0)[/size] [size=1]
return 1; // // Will reach here with 0.24 probability[/size] [size=1]
return my_fun(); // will reach here with (1 - 0.24 - 0.24) probability[/size] [size=1]
}[/size]
[size=1]
int main()[/size] [size=1]
{[/size] [size=1]
printf ("%d ", my_fun());[/size] [size=1]
return 0;[/size] [size=1]
}[/size]
[/size] [/size][/size][/font][/color][/size]