Recursive Functions
Biostatistics 615
Lecture 5
,Notes on Problem Set 1
z Results were very positive!
• (But homework was time-consuming!)…
z Familiar with Union Find algorithms
z Language of choice
• 50% tried C
• 50% tried R
,Question 1
z How many random pairs of connections
are required to connect 1,000 objects?
• Answer: ~3,740
z Useful notes:
• Count all connections
• Use simple termination condition
, Question 2
z What are path lengths in the saturated
tree?
• ~1.8 nodes on average
• ~5 nodes for maximum path
z Random data is better than worst case
• log2 N nodes
Biostatistics 615
Lecture 5
,Notes on Problem Set 1
z Results were very positive!
• (But homework was time-consuming!)…
z Familiar with Union Find algorithms
z Language of choice
• 50% tried C
• 50% tried R
,Question 1
z How many random pairs of connections
are required to connect 1,000 objects?
• Answer: ~3,740
z Useful notes:
• Count all connections
• Use simple termination condition
, Question 2
z What are path lengths in the saturated
tree?
• ~1.8 nodes on average
• ~5 nodes for maximum path
z Random data is better than worst case
• log2 N nodes