Analysis of investment problem Now we can compute EX EX]=E∑X ∑E[x i=1 ∑ 1/i Inn+O() Average cost: O(nnc
Analysis of investment problem Now we can compute E [X]: 1 [] [ ] n i i E XE X = = ∑ 1 [ ] n i i E X = = ∑ 1 1/ n i i = = ∑ = ln (1) n O+ Average cost: O (lnnc b )
Randomized algorithm RANDOMIZED-STOCK-INVESTMENT(n) 1. Randomly permute the list of candidates 2. best=0 fori←lton 34567 do investigate candidate i if candidate i is better than candidate best then best←i ly candidate i
Randomized algorithm RANDOMIZED-STOCK-INVESTMENT ( n ) 1. Randomly permute the list of candidates 2. best = 0 3. for i ← 1 to n 4. do investigate candidate i 5. if candidate i is better than candidate best 6. then best ← i 7. buy candidate i
Divide and conquer Quicksort an n-element array 1. Divide: partition the array into two subarrays around a pivot x such that elements in lower subarray ≤x≤ elements in upper subarray. ≤x x≤ 2. Conquer: recursively sort the two subarrays 3. Combine: Trivial Key: Linear-time partitioning subroutine
Divide and conquer Quicksort an n-element array: 1. Divide: Partition the array into two subarrays around a pivot x such that elements in lower subarray ≤ x ≤ elements in upper subarray. ≤ x x x ≤ 2. Conquer: Recursively sort the two subarrays. 3. Combine: Trivial. Key: Linear-time partitioning subroutine
Pseudocode for quicksort QUICKSORT(A,P, r) ifp< 2. then g+ PARTITION(A,,r) 3 QUICKSORT(A, p, g-1) QUICKSORT(A, 9+l, r Initial call: QUICKSORT(A, I
Pseudocode for quicksort QUICKSORT (A, p, r ) 1. if p < r 2. then q ← PARTITION (A, p, r ) 3. QUICKSORT (A, p, q – 1) 4. QUICKSORT (A, q + 1, r ) Initial call: QUICKSORT (A, 1, n )
Example of partitioning 287 3564
Example of partitioning 8 p 7 1 3 5 6 4 i r j 2