Randomized Algorithms: Difference between revisions

From NovaOrdis Knowledge Base
Jump to navigation Jump to search
 
(10 intermediate revisions by the same user not shown)
Line 1: Line 1:
=External=
=Internal=
=Internal=


* [[Data_Structures_and_Algorithms#Randomized_Algorithm|Data Structures and Algorithms]]
* [[Algorithms#Randomized_Algorithm|Algorithms]]
* [[Probability#Overview|Probability]]


=Overview=
=Overview=
<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=
=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