wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> Random Connections
        
(Message started by: Skandh on Aug 18^th, 2011, 10:45am)

Title: Random Connections
Post by Skandh on Aug 18^th, 2011, 10:45am

I was going through some algorithmic puzzles and got bit confused in following problem (the reason could be I usually get nervous when I see probability :( )

"Random connections. Write a program that takes as command-line arguments
an integer N and a double value p (between 0 and 1), plots N equally spaced dots of size
.05 on the circumference of a circle, and then, with probability p for each pair of points,
draws a gray line connecting them"

Let's say I have N=10 equally spaced dots and p=0.3. Hence with the given data we have 45 pair of points.

So we have to draw lines between these 45 pairs with probability 0.3. What does this mean?

Title: Re: Random Connections
Post by pex on Aug 18^th, 2011, 11:37am

on 08/18/11 at 10:45:28, Skandh wrote:

So we have to draw lines between these 45 pairs with probability 0.3. What does this mean?

The usual meaning is that each of these 45 lines can be drawn, each independently with a probability of 30%. So, something like

for i in 0 to 8
for j = i+1 to 9
draw a random number r, uniform in (0,1)
if r < 0.3
draw a line from point i to point j
end if
end for
end for

Title: Re: Random Connections
Post by TenaliRaman on Aug 23^rd, 2011, 11:51pm

This is the Erdos-Renyi model for generating random graphs [1].

-- AI
[1] http://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93R%C3%A9nyi_model