代写代考 Analysis of Algorithms, I

Analysis of Algorithms, I
CSOR W4231

Computer Science Department

Columbia University
Quicksort, randomized quicksort, occupancy problems

1 Quicksort
2 Randomized Quicksort
3 Random variables and linearity of expectation
4 Analysis of randomized Quicksort
5 Occupancy problems

Quicksort facts
􏰉 Quicksort is a divide and conquer algorithm
􏰉 It is the standard algorithm used for sorting
􏰉 It is an in-place algorithm
􏰉 Its worst-case running time is Θ(n2) but its average-case running time is Θ(n log n)
􏰉 We will use it to introduce randomized algorithms

Quicksort: main idea
􏰉 Pick an input item, call it pivot, and place it in its final location in the sorted array by re-organizing the array so that:
􏰉 all items ≤ pivot are placed before pivot
􏰉 all items > pivot are placed after pivot
􏰉 Recursively sort the subarray to the left of pivot. 􏰉 Recursively sort the subarray to the right of pivot.

Quicksort pseudocode
Quicksort(A, lef t, right)
if |A| = 0 then return //A is empty end if
split = Partition(A, lef t, right) Quicksort(A, lef t, split − 1)
Quicksort(A, split + 1, right)
Initial call: Quicksort(A, 1, n)

Subroutine Partition(A,left,right)
Notation: A[i,j] denotes the portion of A starting at position i and ending at position j.
Partition(A, lef t, right)
1. picks a pivot item
2. re-organizes A[left,right] so that
􏰉 all items before pivot are ≤ pivot
􏰉 all items after pivot are > pivot
3. returns split, the index of pivot in the re-organized array
After Partition, A[left,right] looks as follows:
≤pivot >pivot
left split right

Implementing Partition
1. Pick a pivot item: for simplicity, always pick the last item of the array as pivot, i.e., pivot = A[right].
􏰉 Thus A[right] will be placed in its final location in the sorted output when Partition returns; it will never be used (or moved) again until the algorithm terminates.
2. Re-organize the input array A in place. How?
(What if we didn’t care to implement Partition in place?)

Implementing Partition in place
Partition examines the items in A[left,right] one by one and maintains three regions in A. Specifically, after examining the j-th item for j ∈ [left, right − 1], the regions are:
1. Left region: starts at left and ends at split; A[left,split] contains all items ≤ pivot examined so far.
2. Middle region: starts at split + 1 and ends at j;
A[split + 1, j] contains all items > pivot examined so far.
3. Right region: starts at j + 1 and ends at right − 1; A[j + 1, right − 1] contains all unexamined items.
≤pivot >pivot unexamined
split split+1 j j+1 right-1 right
End of j-th iteration

Implementing Partition in place (cont’d)
At the beginning of iteration j, A[j] is compared with pivot. If A[j] ≤ pivot
1. swap A[j] with A[split + 1], the first element of the middle region (items > pivot): since A[split + 1] > pivot, it is “safe” to move it to the end of the middle region
2. increment split to include A[j] in the left region (items > pivot)

Iteration j: when A[j] ≤ pivot
Beginning of iteration j (assume A[j]≤pivot)
≤pivot >pivot
split split+1
unexamined
End of iteration j: A[j] got swapped with A[split+1], split got updated to split+1
>pivot unexamined

Example: A = {1, 3, 7, 2, 6, 4, 5}, Partition(A, 1, 7)
unexamined
unexamined
unexamined
>pivot unexamined
1 39 7 2 6 4 5
>pivot 1 3 j
1 39 split j
beginning of iteration j=1 A[j]=1
beginning of iteration j=2 A[j]=3
beginning of iteration j=3 A[j]=7
unexamined
beginning of iteration j=4, A[j]=2
beginning of iteration j=5 A[j]=6
1 39 2 7 6 4 5
1 39 2 7 6 4 5 split j
beginning of iteration j=6 A[j]=4
end of iteration j=6 A[j]=4
end of Partition
1 39 2 4 6 7 5 split j
5 7 6 split

Pseudocode for Partition
Partition(A, lef t, right)
pivot = A[right]
split = left − 1
for j=lefttoright−1 do
if A[j] ≤ pivot then swap(A[j], A[split + 1]) split = split + 1
end if end for
swap(pivot, A[split + 1]) //place pivot after A[split] (why?) return split + 1 //the final position of pivot

Analysis of Partition: correctness
Notation: A[i,j] denotes the portion of A that starts at position i and ends at position j.
For left ≤ j ≤ right − 1, at the end of loop j, 1. all items in A[left,split] are ≤ pivot; and 2. all items in A[split + 1, j] are > pivot
Remark: If the claim is true, correctness of Partition follows (why?).

Proof of Claim 1
By induction on j.
1. Base case: For j = left (that is, during the first execution of the for loop), there are two possibilities:
􏰉 if A[left] ≤ pivot, then A[left] is swapped with itself and split is incremented to equal left;
􏰉 otherwise, nothing happens.
In both cases, the claim holds for j = left.
2. Hypothesis: Assume that the claim is true for some left ≤ j < right − 1. 􏰉 That is, at the end of loop j, all items in A[left,split] are ≤ pivot and all items in A[split + 1, j] are > pivot.

Proof of Claim 1 (cont’d)
3. Step: We will show the claim for j + 1. That is, we will show that after loop j + 1, all items in A[lef t, split] are ≤ pivot and all items in A[split + 1, j + 1] are > pivot.
􏰉 At the beginning of loop j + 1, by the hypothesis, items in A[left, split] are ≤ pivot and items in A[split + 1, j] are > pivot.
􏰉 Inside loop j + 1, there are two possibilities:
1. A[j + 1] ≤ pivot: then A[j + 1] is swapped with A[split + 1]. At this point, items in A[lef t, split + 1] are ≤ pivot and items in A[split + 2, j + 1] are > pivot. Incrementing split (the next step in the pseudocode) yields that the claim holds for j + 1.
2. A[j + 1] > pivot: nothing is done. The truth of the claim follows from the hypothesis.
This completes the proof of the inductive step.

Analysis of Partition: running time and space
􏰉 Running time: on input size n, Partition goes through each of the n − 1 leftmost elements once and performs constant amount of work per element.
⇒ Partition requires Θ(n) time. 􏰉 Space: in-place algorithm

Analysis of Quicksort: correctness
􏰉 Quicksort is a recursive algorithm; we will prove correctness by induction on the input size n.
􏰉 We will use strong induction: the induction step at n requires that the inductive hypothesis holds at all steps 1,2,…,n−1 and not just at step n−1, as with simple induction.
􏰉 Strong induction is most useful when several instances of the hypothesis are required to show the inductive step.

Analysis of Quicksort: correctness
􏰉 Base case: for n = 0, Quicksort sorts correctly.
􏰉 Hypothesis: for all 0 ≤ m < n, Quicksort correctly sorts on input size m. 􏰉 Step: show that Quicksort correctly sorts on input size n. 􏰉 Partition(A, 1, n) re-organizes A so that all items 􏰉 in A[1,...,split − 1] are ≤ A[split]; 􏰉 in A[split + 1,...,n] are > A[split].
􏰉 Next, Quicksort(A, 1, split − 1), Quicksort(A, split + 1, n) will correctly sort their inputs (by the hypothesis). Hence
A[1] ≤ . . . ≤ A[split − 1] and A[split + 1] ≤ . . . ≤ A[n]. At this point, Quicksort terminates and A is sorted.

Analysis of Quicksort: space and running time
􏰉 Space: in-place algorithm
􏰉 Running time T(n): depends on the arrangement of the input elements
􏰉 the sizes of the inputs to the two recursive calls –hence the form of the recurrence– depend on how pivot compares to the rest of the input items

Running time of Quicksort:
Suppose that in every call to Partition the pivot item is the median of the input.
Then every Partition splits its input into two lists of almost equal sizes, thus
T (n) = 2T (n/2) + Θ(n) = O(n log n). This is a “balanced” partitioning.
􏰉 Exampleofbestcase: A=[1 3 2 5 7 6 4] Remark 1.
You can show that T (n) = O(n log n) for any splitting where the two subarrays have sizes αn, (1 − α)n respectively, for constant 0 < α < 1. Running time of Quicksort: Worst Case 􏰉 Upper bound for worst-case running time: T(n) = O(n2) 􏰉 at most n calls to Partition (one for each item as pivot) 􏰉 Partition requires O(n) time 􏰉 This worst-case upper bound is tight: 􏰉 If every time Partition is called pivot is greater (or smaller) than every other item, then its input is split into two lists, one of which has size 0. 􏰉 This partitioning is very “unbalanced”: let c, d > 0 be constants, where T (0) = d; then
T(n) = T(n−1)+T(0)+cn = Θ(n2). △ A worst-case input is the sorted input!

Running time: average case analysis
Average case: what is an “average” input to sorting?
􏰉 Depends on the application.
􏰉 Inntuition why average-case analysis for uniformly distributed inputs to Quicksort is O(n log n) appears in your textbook.
􏰉 We will use randomness within the algorithm to provide Quicksort with a uniform at random input.

1 Quicksort
2 Randomized Quicksort
3 Random variables and linearity of expectation
4 Analysis of randomized Quicksort
5 Occupancy problems

Two views of randomness in computation
1. Deterministic algorithm, randomness over the inputs
􏰉 On the same input, the algorithm always produces the same output using the same time.
􏰉 So far, we have only encountered such algorithms. 􏰉 The input is randomly generated according to some
underlying distribution.
􏰉 Average case analysis: analysis of the running time of the algorithm on an average input.

Two views of randomness in computation (cont’d)
2. Randomized algorithm, worst-case (deterministic) input
􏰉 On the same input, the algorithm produces the same output but different executions may require different running times.
􏰉 The latter depend on the random choices of the algorithm (e.g., coin flips, random numbers).
􏰉 Random samples are assumed independent of each other.
􏰉 Worst-case input
􏰉 Expected running time analysis: analysis of the running time of the randomized algorithm on a worst-case input.

Remarks on randomness in computation
1. Deterministic algorithms are a special case of randomized algorithms.
2. Even when equally efficient deterministic algorithms exist, randomized algorithms may be simpler, require less memory of the past or be useful for symmetry-breaking.

Randomized Quicksort
Can we use randomization so that Quicksort works with an “average” input even when it receives a worst-case input?
1. Explicitly permute the input.
2. Use random sampling to choose pivot: instead of using
A[right] as pivot, select pivot randomly.
Idea 1 (intuition behind random sampling).
No matter how the input is organized, we won’t often pick the largest or smallest item as pivot (unless we are really, really unlucky). Thus most often the partitioning will be “balanced”.

Pseudocode for randomized Quicksort
Randomized-Quicksort(A, lef t, right)
if |A| == 0 then return //A is empty
split = Randomized-Partition(A, lef t, right) Randomized-Quicksort(A, lef t, split − 1) Randomized-Quicksort(A, split + 1, right)
Randomized-Partition(A, lef t, right) b = random(lef t, right)
swap(A[b], A[right])
return Partition(A,left,right)
Subroutine random(i,j) returns a random number between i and j inclusive.

1 Quicksort
2 Randomized Quicksort
3 Random variables and linearity of expectation
4 Analysis of randomized Quicksort
5 Occupancy problems

Discrete random variables
􏰉 To analyze the expected running time of a randomized algorithm we keep track of certain parameters and their expected size over the random choices of the algorithm.
􏰉 To this end, we use random variables.
􏰉 A discrete random variable X takes on a finite number of values, each with some probability. We’re interested in its expectation
E[X] = 􏰆 j · Pr[X = j]. j

Example 1: Bernoulli trial
Experiment 1: flip a biased coin which comes up 􏰉 heads with probability p
􏰉 tailswithprobability1−p
Question: what is the expected number of heads?

Example 1: Bernoulli trial
Experiment 1: flip a biased coin which comes up 􏰉 heads with probability p
􏰉 tailswithprobability1−p
Question: what is the expected number of heads? Let X be a random variable such that
􏰂 1 , if coin flip comes heads X= 0 ,ifcoinflipcomestails

Indicator random variables
􏰉 Indicator random variable: a discrete random variable that only takes on values 0 and 1.
􏰉 Indicator random variables are used to denote occurrence (or not) of an event.
Example: in the biased coin flip example, X is an indicator random variable that denotes the occurrence of heads.
If X is an indicator random variable, then E[X] = Pr[X = 1].

Example 2: Bernoulli trials
Experiment 2: flip the biased coin n times Question: what is the expected number of heads?

Example 2: Bernoulli trials
Experiment 2: flip the biased coin n times Question: what is the expected number of heads?
Answer 1: Let X be the random variable counting the number of times heads appears.
Pr[X = j]?
E[X] = 􏰆 j · Pr[X = j]. j=0

Example 2: Bernoulli trials
A different way to think about X:
Answer 2: for 1 ≤ i ≤ n, let Xi be an indicator random
variable such that
􏰂 1 , if i-th coin flip comes heads Xi = 0 , if i-th coin flip comes tails

Linearity of expectation
X = 􏰆Xi, E[Xi] = p, E[X] =?

Linearity of expectation
X = 􏰆Xi, E[Xi] = p, E[X] =?
Remark 1: X is a complicated random variable defined as the sum of simpler random variables whose expectation is known.

Linearity of expectation
X = 􏰆Xi, E[Xi] = p, E[X] =?
Remark 1: X is a complicated random variable defined as the
sum of simpler random variables whose expectation is known.
Proposition 1 (Linearity of expectation).
Let X1, . . . , Xk be arbitrary random variables. Then
E[X1 +X2 +…+Xk]=E[X1]+E[X2]+…+E[Xk]

Back to example 2: Bernoulli trials
Answer 2: for 1 ≤ i ≤ n, let Xi be an indicator random variable such that
􏰂 1 , if i-th coin flip comes heads Xi = 0 , if i-th coin flip comes tails
Define the random variable
By Fact 1, E[Xi] = p, for all i. By linearity of expectation, nnn
E[X] = E􏰒􏰆X 􏰓 = 􏰆E[X ] = 􏰆p = np. ii
i=1 i=1 i=1

1 Quicksort
2 Randomized Quicksort
3 Random variables and linearity of expectation
4 Analysis of randomized Quicksort
5 Occupancy problems

Expected running time of randomized Quicksort
􏰉 Let T(n) be the expected running time of Randomized-Quicksort.
􏰉 We want to bound T(n).
􏰉 Randomized-Quicksort differs from Quicksort only in
how they select their pivot elements.
⇒ We will analyze Randomized-Quicksort based on Quicksort and Partition.

Pseudocode for Partition
Partition(A, lef t, right)
pivot = A[right]
split = left − 1
for j=lefttoright−1 do
if A[j] ≤ pivot then swap(A[j], A[split + 1]) split = split + 1
end if end for
swap(pivot, A[split + 1]) return split + 1
line 1 line 2 line3 line 4 line 5 line 6
line 7 line 8

Few observations
1. How many times is Partition called?

Few observations
1. How many times is Partition called? At most n.
2. Further, each Partition call spends some work 1. outside the for loop
2. inside the for loop

Few observations
1. How many times is Partition called? At most n.
2. Further, each Partition call spends some work 1. outside the for loop
􏰉 every Partition spends constant work outside the for loop
􏰉 at most n calls to Partition
⇒ total work outside the for loop in all calls to Partition is O(n)
2. inside the for loop
􏰉 let X be the total number of comparisons performed at line 4 in
all calls to Partition
􏰉 each comparison may require some further constant work (lines 5
⇒ total work inside the for loop in all calls to Partition is O(X)

Towards a bound for T(n)
X = the total number of comparisons in all Partition calls. The running time of Randomized-Quicksort is
Since X is a random variable, we need E[X] to bound T(n).

Towards a bound for T(n)
X = the total number of comparisons in all Partition calls. The running time of Randomized-Quicksort is
Since X is a random variable, we need E[X] to bound T(n).
Fix any two input items. During the execution of the algorithm, they may be compared at most once.
Comparisons are only performed with the pivot of each Partition call. After Partiton returns, pivot is in its final location in the output and will not be part of the input to any future recursive call.

Simplifying the analysis
􏰉 There are n numbers in the input, hence 􏰊n􏰋 = n(n−1) 22
distinct (unordered) pairs of input numbers.
􏰉 From Fact 1, the algorithm will perform at most 􏰊n􏰋 2
comparisons.
􏰉 What is the expected number of comparisons?

Simplifying the analysis
􏰉 There are n numbers in the input, hence 􏰊n􏰋 = n(n−1) 22
distinct (unordered) pairs of input numbers.
􏰉 From Fact 1, the algorithm will perform at most 􏰊n􏰋
comparisons.
􏰉 What is the expected number of comparisons? To simplify the analysis
􏰉 relabel the input as z1,z2,…,zn, where zi is the i-th smallest number.
􏰉 assume that all input numbers are distinct; thus zi < zj, for i < j. Writing X as the sum of indicator random variables Let Xij be an indicator random variable such that 􏰂 1, if zi and zj are ever compared Xij = 0, otherwise Writing X as the sum of indicator random variables Let Xij be an indicator random variable such that 􏰂 1, if zi and zj are ever compared The total number of comparisons is given by X = 􏰅 Xij. 1≤iCS代考加微信: powcoder QQ: 1823890830 Email: powcoder@163.com

Related Posts