Biostatistics 615/815 Lecture 8
Notes on Problem Set 2
Union Find algorithms Results were very positive! You should be getting comfortable compiling, debugging and executing C codeQuestion 1
How many random pairs of connections are required to connect 1,000 objects?
• Answer: ~3,740
• Number of non-redundant links to controls loop • Repeat simulationto get a better estimates
Path lengths in the saturated tree…
• • •
~1.8 nodes on average ~5 nodes for maximum path
Random data is far from worst case
Worst case would bepaths of log2 N (10) nodes
Path lengths can be calculated using weights
Tree height or weight for optimal quick union operations?
Using height ensures that longest path isshorter. Pointing the root of a tree with X nodes to the root of a tree with Y nodes, increases the average length of all paths by X/N.
• Smallest average length and faster Find operationscorrespond to choosing X < Y.
• Easiest to check if you use the same sequence of
random numbers for both problems.
Last Lecture: Shell Sort
Gradually bring order to array by:
Sortingsub-arrays including every kth element Using a series of step sizes k, ending with k = 1
Each pass handles nearly sorted arrays where insertion sort is efficient Theoretically, N (log N)2 complexity ispossible
Array gradually gains order Eventually, we approach the ideal case where insertion sort is O(N)
Today: Quick Sort
Most widely used sorting algorithm
•Possibly excluding those bubble sorts that
should be banished!
• O(N log N)
The Inventor of Quicksort
Sir Charles A. R. Hoare
• 1980ACM Turing Award
British computer scientist
• Studied statistics as a graduate student
Made major contributions to developing computer languages
C. A. R. Hoare Quote
“I conclude that there...