Randomized Algorithms: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
|||
| (6 intermediate revisions by the same user not shown) | |||
| Line 3: | Line 3: | ||
=Internal= | =Internal= | ||
* [[ | * [[Algorithms#Randomized_Algorithm|Algorithms]] | ||
* [[Probability#Overview|Probability]] | * [[Probability#Overview|Probability]] | ||
=Overview= | =Overview= | ||
<font color='darkgray'>Enforcing a probability distribution on inputs ensures that no particular input always causes poor performance. </font> | <font color='darkgray'> | ||
TODO [[CLRS]] page 114. | |||
Enforcing a probability distribution on inputs ensures that no particular input always causes poor performance. | |||
</font> | |||
=Probabilistic Analysis= | =Probabilistic Analysis= | ||
=Examples= | |||
* [[Karger's Contraction Algorithm]] | |||
* [[Quicksort]] | |||
* primality testing | |||
* hashing | |||
Latest revision as of 22:54, 20 October 2021
External
Internal
Overview
TODO CLRS page 114.
Enforcing a probability distribution on inputs ensures that no particular input always causes poor performance.
Probabilistic Analysis
Examples
- Karger's Contraction Algorithm
- Quicksort
- primality testing
- hashing