Sign inSign in

Randomized algorithm

An algorithm that employs a degree of randomness as part of its logic.
as Ryan O'Donnell defines itCarnegie Mellon UniversityThe wording closest to all 6 definitions
Watch it explained

Know first

Named as a prerequisite by the lectures that define this. The number is how many say so. A grey one has no page yet.

Opens up

Concepts that name this one as a prerequisite.

Lecturers

5

Each in their own terms, from the easiest level.

  • Ryan O'Donnell

    Carnegie Mellon University · Undergraduate

    An algorithm that employs a source of randomness to make decisions during its execution.
    • 11:24Randomized Complexity: RP, coRP, and ZPP
  • Erik Demaine & Srini Devadas

    MIT · Undergraduate

    An algorithm that generates random numbers and makes decisions based on their values.
    • 1:20Randomization: Matrix Multiply, Quicksort
  • Tom Leighton

    MIT · Undergraduate

    An algorithm whose strategy depends on a coin flip or guessing a value to potentially achieve a better outcome.
  • Ankur Moitra

    MIT · Undergraduate

    An algorithm that employs a degree of randomness as part of its logic, meaning its output or runtime can vary across different executions.
  • Andy Pavlo

    Carnegie Mellon University · Graduate

    Perform a random walk over a solution space of all possible valid plans for a query until a cost threshold is reached or the optimizer runs for a length of time.
    • 51:20Query Optimizer Implementation 2

Lectures that assume it

25

The first 12 are shown.

Connections

41

The lectures that define it or assume it, and the concepts next to it.

Concepts10

Show 4 more

Lectures31

Show 25 more

5 lecturers. Definitions are written by AI from each lecture’s transcript. A time with a play mark starts the lecture at the moment the lecturer says it.