CS 240 Module 3: Sorting, Average-case and Randomization

Flashcards generated from lecture notes on sorting, average-case analysis, and randomization.

What is the formula for average-case run-time?

Tavg A (n) = ∑ instance I of size n TA(I) · relative frequency of I

What assumptions are made, for this module, when analyzing average-case run-time?

Assume that the set In of size-n instances is finite (or can be mapped to a finite set in a natural way) and that all instances occur equally frequently.

What does the function random(n) do?

It returns an integer uniformly from {0, 1, 2, . . . , n−1}.

What is TA(I, R) in the context of randomized algorithms?

TA(I, R) is the run-time of a randomized algorithm A for an instance I and the sequence R of outcomes of random trials.

What is the expected run-time Texp(I) for a given instance I in a randomized algorithm?

Texp(I) = E[T(I, R)] = ∑R T(I, R) · Pr(R)

What is the goal of using randomization in algorithms?

Shift the dependency of run-time from what we can’t control (the input) to what we can control (the random numbers).

What is a randomized algorithm?

A randomized algorithm is one which relies on some random numbers in addition to the input.

What is a sorting permutation?

The permutation π ∈ Πn for which A[π(0)] ≤ A[π(1)] ≤ · · · ≤ A[π(n-1)].

What is the selection problem?

Given an array A of n numbers, and 0 ≤ k < n, find the element that would be at position k of the sorted array.

What does choose-pivot(A) do?

Return an index p in A. We will use the pivot-value v ← A[p] to rearrange the array.

What does partition(A, n, p) do?

Rearrange A and return pivot-rank i so that A[j]

Regarding sorting, what does comparison-based mean?

Data is accessed only by comparing two elements (a key-comparison) and moving elements around (e.g. copying, swapping)

What is the name of the sorting algorithm that this signature represents?

bucket-sort(A, n,sort-key(·))

What does Bucket Sort do?

Sort array A by last digit.

What does it mean for a sort to be stable?

Equal items stay in original order.

Is Bucket Sort stable?

bucket-sort is stable.

Provide a summary of sorting.

Sorting is an important and very well-studied problem. Can be done in Θ(n log n) time; faster is not possible for general input.

What are keys when the algorithm assumes keys are numbers in base R (R: radix)

All digits are in {0, . . . , R-1}