Week-3 (Matrix Multiplication/Quick Sort)
CE100 Algorithms and Programming II¶
Week-3 (Matrix Multiplication/ Quick Sort)¶
Spring Semester, 2021-2022¶
Download DOC-PDF, DOC-DOCX, SLIDE, PPTX
Matrix Multiplication / Quick Sort¶
Outline (1)¶
-
Matrix Multiplication
-
Traditional
-
Recursive
-
Strassen
Outline (2)¶
-
Quicksort
-
Hoare Partitioning
-
Lomuto Partitioning
-
Recursive Sorting
Outline (3)¶
-
Quicksort Analysis
-
Randomized Quicksort
-
Randomized Selection
-
Recursive
-
Medians
-
Matrix Multiplication (1)¶
- Input: \(A=[a_{ij}],B=[b_{ij}]\)
- Output: \(C=[c_{ij}]=A \cdot B\) \(\Longrightarrow i,j=1,2,3, \dots, n\)
Matrix Multiplication (2)¶
- \(c_{ij}=\sum \limits_{1\leq k \leq n}^{}a_{ik}.b_{kj}\)
Matrix Multiplication: Standard Algorithm¶
Running Time: \(\Theta(n^3)\)
for i=1 to n do
for j=1 to n do
C[i,j] = 0
for k=1 to n do
C[i,j] = C[i,j] + A[i,k] + B[k,j]
endfor
endfor
endfor
Matrix Multiplication: Divide & Conquer (1)¶
IDEA: Divide the \(nxn\) matrix into \(2x2\) matrix of \((n/2)x(n/2)\) submatrices.
Matrix Multiplication: Divide & Conquer (2)¶
Matrix Multiplication: Divide & Conquer (3)¶
MATRIX-MULTIPLY(A, B)
// Assuming that both A and B are nxn matrices
if n == 1 then
return A * B
else
//partition A, B, and C as shown before
C[1,1] = MATRIX-MULTIPLY (A[1,1], B[1,1]) +
MATRIX-MULTIPLY (A[1,2], B[2,1]);
C[1,2] = MATRIX-MULTIPLY (A[1,1], B[1,2]) +
MATRIX-MULTIPLY (A[1,2], B[2,2]);
C[2,1] = MATRIX-MULTIPLY (A[2,1], B[1,1]) +
MATRIX-MULTIPLY (A[2,2], B[2,1]);
C[2,2] = MATRIX-MULTIPLY (A[2,1], B[1,2]) +
MATRIX-MULTIPLY (A[2,2], B[2,2]);
endif
return C
Matrix Multiplication: Divide & Conquer Analysis¶
\(T(n) = 8T(n/2) + \Theta(n^2)\)
- \(8\) recursive calls \(\Longrightarrow 8T(\cdots)\)
- each problem has size \(n/2\) \(\Longrightarrow \cdots T(n/2)\)
- Submatrix addition \(\Longrightarrow \Theta(n^2)\)
Matrix Multiplication: Solving the Recurrence¶
-
\(T(n) = 8T(n/2) + \Theta(n^2)\)
-
\(a=8\), \(b=2\)
- \(f(n)=\Theta(n^2)\)
-
\(n^{log_b^a}=n^3\)
-
Case 1: \(\frac{n^{log_b^a}}{f(n)}=\Omega(n^{\varepsilon}) \Longrightarrow T(n)=\Theta(n^{log_b^a})\)
Similar with ordinary (iterative) algorithm.
Matrix Multiplication: Strassen’s Idea (1)¶
Compute \(c_{11},c_{12},c_{21},c_{22}\) using \(7\) recursive multiplications.
In normal case we need \(8\) as below.
Matrix Multiplication: Strassen’s Idea (2)¶
- Reminder:
- Each submatrix is of size \((n/2)*(n/2)\)
- Each add/sub operation takes \(\Theta(n^2)\) time
- Compute \(P1 \dots P7\) using \(7\) recursive calls to matrix-multiply
Matrix Multiplication: Strassen’s Idea (3)¶
- How to compute \(c_{ij}\) using \(P1 \dots P7\) ?
Matrix Multiplication: Strassen’s Idea (4)¶
- \(7\) recursive multiply calls
- \(18\) add/sub operations
Matrix Multiplication: Strassen’s Idea (5)¶
e.g. Show that \(c_{12} = P_1+P_2\) :
Strassen’s Algorithm¶
-
Divide: Partition \(A\) and \(B\) into \((n/2)*(n/2)\) submatrices. Form terms to be multiplied using \(+\) and \(-\).
-
Conquer: Perform \(7\) multiplications of \((n/2)*(n/2)\) submatrices recursively.
-
Combine: Form \(C\) using \(+\) and \(–\) on \((n/2)*(n/2)\)submatrices.
Recurrence: \(T(n) = 7T(n/2) + \Theta(n^2)\)
Strassen’s Algorithm: Solving the Recurrence (1)¶
-
\(T(n) = 7T(n/2) + \Theta(n^2)\)
-
\(a=7\), \(b=2\)
- \(f(n)=\Theta(n^2)\)
-
\(n^{log_b^a}=n^{lg7}\)
-
Case 1: \(\frac{n^{log_b^a}}{f(n)}=\Omega(n^{\varepsilon}) \Longrightarrow T(n)=\Theta(n^{log_b^a})\)
\(T(n)=\Theta(n^{log_2^7})\)
\(2^3 = 8, 2^2=4\) so \(\Longrightarrow log_2^7 \approx 2.81\)
or use https://www.omnicalculator.com/math/log
Strassen’s Algorithm: Solving the Recurrence (2)¶
-
The number \(2.81\) may not seem much smaller than \(3\)
-
But, it is significant because the difference is in the exponent.
-
Strassen’s algorithm beats the ordinary algorithm on today’s machines for \(n \geq 30\) or so.
-
Best to date: \(\Theta(n^{2.376 \dots})\) (of theoretical interest only)
Maximum Subarray Problem¶
Input: An array of values
Output: The contiguous subarray that has the largest sum of elements
- Input array: \([13][-3][-25][20][-3][-16][-23]\overbrace{[18][20][-7][12]}^{\textrm{max. contiguous subarray}}[-22][-4][7]\)
Maximum Subarray Problem: Divide & Conquer (1)¶
- Basic idea:
- Divide the input array into 2 from the middle
- Pick the best solution among the following:
- The max subarray of the left half
- The max subarray of the right half
- The max subarray crossing the mid-point
Maximum Subarray Problem: Divide & Conquer (2)¶
Maximum Subarray Problem: Divide & Conquer (3)¶
-
Divide: Trivial (divide the array from the middle)
-
Conquer: Recursively compute the max subarrays of the left and right halves
-
Combine: Compute the max-subarray crossing the \(mid-point\)
- (can be done in \(\Theta(n)\) time).
- Return the max among the following:
- the max subarray of the \(\text{left-subarray}\)
- the max subarray of the \(\text{rightsubarray}\)
- the max subarray crossing the \(\text{mid-point}\)
TODO : detailed solution in textbook...
Conclusion : Divide & Conquer¶
- Divide and conquer is just one of several powerful techniques for algorithm design.
- Divide-and-conquer algorithms can be analyzed using recurrences and the master method (so practice this math).
- Can lead to more efficient algorithms
Quicksort (1)¶
- One of the most-used algorithms in practice
- Proposed by C.A.R. Hoare in 1962.
- Divide-and-conquer algorithm
- In-place algorithm
- The additional space needed is O(1)
- The sorted array is returned in the input array
- Reminder: Insertion-sort is also an in-place algorithm, but Merge-Sort is not in-place.
- Very practical
Quicksort (2)¶
- Divide: Partition the array into 2 subarrays such that elements in the lower part \(\leq\) elements in the higher part
- Conquer: Recursively sort 2 subarrays
- Combine: Trivial (because in-place)
Key: Linear-time \((\Theta(n))\) partitioning algorithm
Divide: Partition the array around a pivot element¶
-
Choose a pivot element \(x\)
-
Rearrange the array such that:
-
Left subarray: All elements \(\leq x\)
- Right subarray: All elements \(\geq x\)
Conquer: Recursively Sort the Subarrays¶
Note: Everything in the left subarray ≤ everything in the right subarray
Note: Combine is trivial after conquer. Array already sorted.
Two partitioning algorithms¶
- Hoare’s algorithm: Partitions around the first element of subarray
- \((pivot = x = A[p])\)
- Lomuto’s algorithm: Partitions around the last element of subarray
- \((pivot = x = A[r])\)
Hoare’s Partitioning Algorithm (1)¶
- Choose a pivot element: \(pivot = x = A[p]\)
- Grow two regions:
- from left to right: \(A[p \dots i]\)
- from right to left: \(A[j \dots r]\)
- such that:
- every element in \(A[p \dots i] \leq\) pivot
- every element in \(A[p \dots i] \geq\) pivot
Hoare’s Partitioning Algorithm (2)¶
Hoare’s Partitioning Algorithm (3)¶
- Elements are exchanged when
- \(A[i]\) is too large to belong to the left region
- \(A[j]\) is too small to belong to the right region
- assuming that the inequality is strict
- The two regions \(A[p \dots i]\) and \(A[j \dots r]\) grow until \(A[i] \geq pivot \geq A[j]\)
H-PARTITION(A, p, r)
pivot = A[p]
i = p - 1
j = r - 1
while true do
repeat j = j - 1 until A[j] <= pivot
repeat i = i - 1 until A[i] <= pivot
if i < j then
exchange A[i] with A[j]
else
return j
Hoare’s Partitioning Algorithm Example (Step-1)¶
Hoare’s Partitioning Algorithm Example (Step-2)¶
Hoare’s Partitioning Algorithm Example (Step-3)¶
Hoare’s Partitioning Algorithm Example (Step-4)¶
Hoare’s Partitioning Algorithm Example (Step-5)¶
Hoare’s Partitioning Algorithm Example (Step-6)¶
Hoare’s Partitioning Algorithm Example (Step-7)¶
Hoare’s Partitioning Algorithm Example (Step-8)¶
Hoare’s Partitioning Algorithm Example (Step-9)¶
Hoare’s Partitioning Algorithm Example (Step-10)¶
Hoare’s Partitioning Algorithm Example (Step-11)¶
Hoare’s Partitioning Algorithm Example (Step-12)¶
Hoare’s Partitioning Algorithm - Notes¶
- Elements are exchanged when
- \(A[i]\) is too large to belong to the left region
- \(A[j]\) is too small to belong to the right region
- assuming that the inequality is strict
- The two regions \(A[p \dots i]\) and \(A[j \dots r]\) grow until \(A[i] \geq pivot \geq A[j]\)
- The asymptotic runtime of Hoare’s partitioning algorithm \(\Theta(n)\)
H-PARTITION(A, p, r)
pivot = A[p]
i = p - 1
j = r - 1
while true do
repeat j = j - 1 until A[j] <= pivot
repeat i = i - 1 until A[i] <= pivot
if i < j then exchange A[i] with A[j]
else return j
Quicksort with Hoare’s Partitioning Algorithm¶
QUICKSORT (A, p, r)
if p < r then
q = H-PARTITION(A, p, r)
QUICKSORT(A, p, q)
QUICKSORT(A, q + 1, r)
endif
Initial invocation: QUICKSORT(A,1,n)
Hoare’s Partitioning Algorithm: Pivot Selection¶
- if we select pivot to be \(A[r]\) instead of \(A[p]\) in H-PARTITION
- Consider the example where \(A[r]\) is the largest element in the array:
- End of H-PARTITION: \(i = j = r\)
- In QUICKSORT: \(q = r\)
- So, recursive call to:
QUICKSORT(A, p, q=r)- infinite loop
Correctness of Hoare’s Algorithm (1)¶
We need to prove \(3\) claims to show correctness:
- Indices \(i\) and \(j\) never reference \(A\) outside the interval \(A[p \dots r]\)
- Split is always non-trivial; i.e., \(j \neq r\) at termination
- Every element in \(A[p \dots j] \leq\) every element in \(A[j+1 \dots r]\) at termination
Correctness of Hoare’s Algorithm (2)¶
-
Notations:
-
\(k\): \(\#\) of times the while-loop iterates until termination
- \(i_m\): the value of index i at the end of iteration \(m\)
- \(j_m\): the value of index j at the end of iteration \(m\)
-
\(x\): the value of the pivot element
-
Note: We always have \(i_1= p\) and \(p \leq j_1 \leq r\) because \(x = A[p]\)
Correctness of Hoare’s Algorithm (3)¶
Lemma 1: Either \(i_k = j_k\) or \(i_k = j_k+1\) at termination
Proof of Lemma 1:
-
The algorithm terminates when \(i \geq j\) (the else condition).
-
So, it is sufficient to prove that \(i_k – j_k \leq 1\)
-
There are \(2\) cases to consider:
-
Case 1: \(k = 1\), i.e. the algorithm terminates in a single iteration
- Case 2: \(k > 1\), i.e. the alg. does not terminate in a single iter.
By contradiction, assume there is a run with \(i_k – j_k > 1\)
Correctness of Hoare’s Algorithm (4)¶
Original correctness claims:
- Indices \(i\) and \(j\) never reference A outside the interval \(A[p \dots r]\)
- Split is always non-trivial; i.e., \(j \neq r\) at termination
Proof:
- For \(k = 1\):
- Trivial because \(i_1 = j_1 = p\) (see Case 1 in proof of Lemma 2)
- For \(k > 1\):
- \(i_k > p\) and \(j_k < r\) (due to the repeat-until loops moving indices)
- \(i_k \leq r\) and \(j_k \geq p\) (due to Lemma 1 and the statement above)
The proof of claims (a) and (b) complete
Correctness of Hoare’s Algorithm (5)¶
Lemma 2: At the end of iteration \(m\), where \(m<k\) (i.e. m is not the last iteration), we must have: \(A[p \dots i_m] \leq x\) and \(A[j_m \dots r] \geq x\)
Proof of Lemma 2:
- Base case: \(m=1\) and \(k>1\) (i.e. the alg. does not terminate in the first iter.)
Ind. Hyp.: At the end of iteration \(m-1\), where \(m<k\) (i.e. m is not the last iteration), we must have: \(A[p \dots i_m-1] \leq x\) and \(A[j_m-1 \dots r] \geq x\)
General case: The lemma holds for \(m\), where \(m < k\)
Proof of base case complete!
Correctness of Hoare’s Algorithm (6)¶
Original correctness claim:
- © Every element in \(A[ \dots j] \leq\) every element in \(A[j+ \dots r]\) at termination
Proof of claim ©
- There are \(3\) cases to consider:
- Case 1: \(k=1\), i.e. the algorithm terminates in a single iteration
- Case 2: \(k>1\) and \(i_k = j_k\)
- Case 3: \(k>1\) and \(i_k = j_k + 1\)
Lomuto’s Partitioning Algorithm (1)¶
- Choose a pivot element: \(pivot = x = A[r]\)
- Grow two regions:
- from left to right: \(A[p \dots i]\)
- from left to right: \(A[i+1 \dots j]\)
- such that:
- every element in \(A[p \dots i] \leq pivot\)
- every element in \(A[i+1 \dots j] > pivot\)
Lomuto’s Partitioning Algorithm (2)¶
Lomuto’s Partitioning Algorithm Ex. (Step-1)¶
Lomuto’s Partitioning Algorithm Ex. (Step-2)¶
Lomuto’s Partitioning Algorithm Ex. (Step-3)¶
Lomuto’s Partitioning Algorithm Ex. (Step-4)¶
Lomuto’s Partitioning Algorithm Ex. (Step-5)¶
Lomuto’s Partitioning Algorithm Ex. (Step-6)¶
Lomuto’s Partitioning Algorithm Ex. (Step-7)¶
Lomuto’s Partitioning Algorithm Ex. (Step-8)¶
Lomuto’s Partitioning Algorithm Ex. (Step-9)¶
Lomuto’s Partitioning Algorithm Ex. (Step-10)¶
Lomuto’s Partitioning Algorithm Ex. (Step-11)¶
Lomuto’s Partitioning Algorithm Ex. (Step-12)¶
Lomuto’s Partitioning Algorithm Ex. (Step-13)¶
Lomuto’s Partitioning Algorithm Ex. (Step-14)¶
Lomuto’s Partitioning Algorithm Ex. (Step-15)¶
Quicksort with Lomuto’s Partitioning Algorithm¶
QUICKSORT (A, p, r)
if p < r then
q = L-PARTITION(A, p, r)
QUICKSORT(A, p, q - 1)
QUICKSORT(A, q + 1, r)
endif
Initial invocation: QUICKSORT(A,1,n)
Comparison of Hoare’s & Lomuto’s Algorithms (1)¶
- Notation: \(n=r-p+1\)
- \(pivot=A[p]\) (Hoare)
- \(pivot=A[r]\) (Lomuto)
- \(\#\) of element exchanges: \(e(n)\)
- Hoare: \(0 \geq e(n) \geq \lfloor \frac{n}{2} \rfloor\)
- Best: \(k=1\) with \(i_1=j_1=p\) (i.e., \(A[p+1 \dots r]>pivot\))
- Worst: \(A[p+1 \dots p+ \lfloor \frac{n}{2} \rfloor - 1] \geq pivot \geq A[p+ \lceil \frac{n}{2} \rceil \dots r]\)
- Lomuto : \(1 \leq e(n) \leq n\)
- Best: \(A[p \dots r -1]>pivot\)
- Worst: \(A[p \dots r-1] \leq pivot\)
Comparison of Hoare’s & Lomuto’s Algorithms (2)¶
-
\(\#\) of element comparisons: \(c_e(n)\)
-
Hoare: \(n+1 \leq c_e(n) \leq n+2\)
- Best: \(i_k=j_k\)
- Worst: \(i_k=j_k+1\)
-
Lomuto: \(c_e(n)=n-1\)
-
\(\#\) of index comparisons: \(c_i(n)\)
-
Hoare: \(1 \leq c_i(n) \leq \lfloor \frac{n}{2} \rfloor + 1 | (c_i(n)=e(n)+1)\)
- Lomuto: \(c_i(n)=n-1\)
Comparison of Hoare’s & Lomuto’s Algorithms (3)¶
-
\(\#\) of index increment/decrement operations: \(a(n)\)
-
Hoare: \(n+1 \leq a(n) \leq n+2 | (a(n)=c_e(n))\)
-
Lomuto: \(n \leq a(n) \leq 2n-1 | (a(n)=e(n)+(n-1))\)
-
Hoare’s algorithm is in general faster
-
Hoare behaves better when pivot is repeated in \(A[p \dots r]\)
-
Hoare: Evenly distributes them between left & right regions
- Lomuto: Puts all of them to the left region
Analysis of Quicksort (1)¶
QUICKSORT (A, p, r)
if p < r then
q = H-PARTITION(A, p, r)
QUICKSORT(A, p, q)
QUICKSORT(A, q + 1, r)
endif
Initial invocation: QUICKSORT(A,1,n)
Assume all elements are distinct in the following analysis
Analysis of Quicksort (2)¶
- H-PARTITION always chooses \(A[p]\) (the first element) as the pivot.
- The runtime of QUICKSORT on an already-sorted array is \(\Theta(n^2)\)
Example: An Already Sorted Array¶
Partitioning always leads to \(2\) parts of size \(1\) and \(n-1\)
Worst Case Analysis of Quicksort¶
- Worst case is when the PARTITION algorithm always returns imbalanced partitions (of size \(1\) and \(n-1\)) in every recursive call.
- This happens when the pivot is selected to be either the min or max element.
- This happens for H-PARTITION when the input array is already sorted or reverse sorted
Worst Case Recursion Tree¶
Best Case Analysis (for intuition only)¶
- If we’re extremely lucky, H-PARTITION splits the array evenly at every recursive call
(same as merge sort)
- Instead of splitting \(0.5:0.5\), if we split \(0.1:0.9\) then we need solve following equation.
“Almost-Best” Case Analysis¶
Balanced Partitioning (1)¶
-
We have seen that if H-PARTITION always splits the array with \(0.1-to-0.9\) ratio, the runtime will be \(\Theta(nlgn)\).
-
Same is true with a split ratio of \(0.01-to-0.99\), etc.
-
Possible to show that if the split has always constant \((\Theta(1))\) proportionality, then the runtime will be \(\Theta(nlgn)\).
-
In other words, for a constant \(\alpha | (0 < \alpha ≤ 0.5)\):
-
\(\alpha–to–(1-\alpha)\) proportional split yields \(\Theta(nlgn)\) total runtime
Balanced Partitioning (2)¶
- In the rest of the analysis, assume that all input permutations are equally likely.
- This is only to gain some intuition
- We cannot make this assumption for average case analysis
- We will revisit this assumption later
- Also, assume that all input elements are distinct.
Balanced Partitioning (3)¶
- Question: What is the probability that H-PARTITION returns a split that is more balanced than \(0.1-to-0.9\)?
Balanced Partitioning (4)¶
Reminder: H-PARTITION will place the pivot in the right partition unless the pivot is the smallest element in the arrays.
Question: If the pivot selected is the mth smallest value \((1 < m ≤ n)\) in the input array, what is the size of the left region after partitioning?
Balanced Partitioning (5)¶
-
Question: What is the probability that the pivot selected is the \(m^{th}\) smallest value in the array of size \(n\)?
-
\(1/n\) (since all input permutations are equally likely)
-
Question: What is the probability that the left partition returned by H-PARTITION has size \(m\), where \(1<m<n\)?
-
\(1/n\) (due to the answers to the previous 2 questions)
Balanced Partitioning (6)¶
- Question: What is the probability that H-PARTITION returns a split that is more balanced than \(0.1-to-0.9\)?
Balanced Partitioning (7)¶
-
The probability that H-PARTITION yields a split that is more balanced than \(0.1-to-0.9\) is \(80\%\) on a random array.
-
Let \(P_{\alpha>}\) be the probability that H-PARTITION yields a split more balanced than \(\alpha-to-(1-\alpha)\), where \(0 < \alpha \leq 0.5\)
-
Repeat the analysis to generalize the previous result
Balanced Partitioning (8)¶
- Question: What is the probability that H-PARTITION returns a split that is more balanced than \(\alpha-to-(1-\alpha)\)?
Balanced Partitioning (9)¶
- We found \(P_{\alpha >}=1-2\alpha\)
- Ex: \(P_{0.1>}=0.8\) and \(P_{0.01>}=0.98\)
- Hence, H-PARTITION produces a split
- more balanced than a
- \(0.1-to-0.9\) split \(80\%\) of the time
- \(0.01-to-0.99\) split \(98\%\) of the time
- less balanced than a
- \(0.1-to-0.9\) split \(20\%\) of the time
- \(0.01-to-0.99\) split \(2\%\) of the time
Intuition for the Average Case (1)¶
-
Assumption: All permutations are equally likely
-
Only for intuition; we’ll revisit this assumption later
-
Unlikely: Splits always the same way at every level
-
Expectation:
-
Some splits will be reasonably balanced
-
Some splits will be fairly unbalanced
-
Average case: A mix of good and bad splits
-
Good and bad splits distributed randomly thru the tree
Intuition for the Average Case (2)¶
- Assume for intuition: Good and bad splits occur in the alternate levels of the tree
- Good split: Best case split
- Bad split: Worst case split
Intuition for the Average Case (3)¶
Compare 2-successive levels of avg case vs. 1 level of best case
Intuition for the Average Case (4)¶
-
In terms of the remaining subproblems, two levels of avg case is slightly better than the single level of the best case
-
The avg case has extra divide cost of \(\Theta(n)\) at alternate levels
-
The extra divide cost \(\Theta(n)\) of bad splits absorbed into the \(\Theta(n)\) of good splits.
-
Running time is still \(\Theta(nlgn)\)
-
But, slightly larger hidden constants, because the height of the recursion tree is about twice of that of best case.
Intuition for the Average Case (5)¶
-
Another way of looking at it:
-
Suppose we alternate lucky, unlucky, lucky, unlucky, \(\dots\)
- We can write the recurrence as:
- \(L(n) = 2U(n/2) + \Theta(n)\) lucky split (best)
- \(U(n) = L(n-1) + \Theta(n)\) unlucky split (worst)
- Solving:
$$ \begin{align*} L(n) & = 2(L(n/2-1) + \Theta(n/2)) + \Theta(n) \ & = 2L(n/2-1) + \Theta(n) \ & = Θ(nlgn) \end{align*} $$
- How can we make sure we are usually lucky for all inputs?
Summary: Quicksort Runtime Analysis (1)¶
- Worst case: Unbalanced split at every recursive call
- Best case: Balanced split at every recursive call (extremely lucky)
Summary: Quicksort Runtime Analysis (2)¶
- Almost-best case: Almost-balanced split at every recursive call
for any constant \(\alpha, 0 < \alpha \leq 0.5\)
Summary: Quicksort Runtime Analysis (3)¶
- For a random input array, the probability of having a split
- more balanced than \(0.1 – to – 0.9 : 80\%\)
- more balanced than \(0.01 – to – 0.99 : 98\%\)
-
more balanced than \(\alpha – to – (1-\alpha) : 1 – 2 \alpha\)
-
for any constant \(\alpha, 0 < \alpha \leq 0.5\)
Summary: Quicksort Runtime Analysis (4)¶
-
Avg case intuition: Different splits expected at different levels
-
some balanced (good), some unbalanced (bad)
-
Avg case intuition: Assume the good and bad splits alternate
-
i.e. good split -> bad split -> good split -> …
- \(T(n) = \Theta(nlgn)\)
- (informal analysis for intuition)
Randomized Quicksort¶
- In the avg-case analysis, we assumed that all permutations of the input array are equally likely.
- But, this assumption does not always hold
- e.g. What if all the input arrays are reverse sorted?
- Always worst-case behavior
- Ideally, the avg-case runtime should be independent of the input permutation.
- Randomness should be within the algorithm, not based on the distribution of the inputs.
- i.e. The avg case should hold for all possible inputs
Randomized Algorithms (1)¶
- Alternative to assuming a uniform distribution:
- Impose a uniform distribution
- e.g. Choose a random pivot rather than the first element
- Typically useful when:
- there are many ways that an algorithm can proceed
- but, it’s difficult to determine a way that is always guaranteed to be good.
- If there are many good alternatives; simply choose one randomly.
Randomized Algorithms (1)¶
- Ideally:
- Runtime should be independent of the specific inputs
- No specific input should cause worst-case behavior
- Worst-case should be determined only by output of a random number generator.
Randomized Quicksort (1)¶
- Using Hoare’s partitioning algorithm:
R-QUICKSORT(A, p, r)
if p < r then
q = R-PARTITION(A, p, r)
R-QUICKSORT(A, p, q)
R-QUICKSORT(A, q+1, r)
- Alternatively, permuting the whole array would also work
- but, would be more difficult to analyze
Randomized Quicksort (2)¶
- Using Lomuto’s partitioning algorithm:
R-QUICKSORT(A, p, r)
if p < r then
q = R-PARTITION(A, p, r)
R-QUICKSORT(A, p, q-1)
R-QUICKSORT(A, q+1, r)
- Alternatively, permuting the whole array would also work
- but, would be more difficult to analyze
Notations for Formal Analysis¶
-
Assume all elements in \(A[p \dots r]\) are distinct
-
Let \(n = r – p + 1\)
-
Let \(rank(x) = |{A[i]: p \leq i \leq r \text{ and } A[i] \leq x}|\)
-
i.e. \(rank(x)\) is the number of array elements with value less than or equal to \(x\)
-
\(A=\{5,9,7,6,8,1,4\}\)
- \(p=5,r=4\)
- \(rank(5)=3\)
- i.e. it is the \(3^{rd}\) smallest element in the array
Formal Analysis for Average Case¶
-
The following analysis will be for Quicksort using Hoare’s partitioning algorithm.
-
Reminder: The pivot is selected randomly and exchanged with \(A[p]\) before calling H-PARTITION
-
Let \(x\) be the random pivot chosen.
-
What is the probability that \(rank(x) = i\) for \(i = 1, 2, \dots n\) ?
-
\(P(rank(x) = i) = 1/n\)
Various Outcomes of H-PARTITION (1)¶
- Assume that \(rank(x)=1\)
- i.e. the random pivot chosen is the smallest element
- What will be the size of the left partition \((|L|)\)?
- Reminder: Only the elements less than or equal to \(x\) will be in the left partition.
\(A=\{\overbrace{2}^{p=x=pivot}\underbrace{,}_{\Longrightarrow|L|=1 } 9,7,6,8,5,\overbrace{4}^r\}\)
\(p=2,r=4\) \(pivot=x=2\)
TODO: convert to image...S6_P9
Various Outcomes of H-PARTITION (2)¶
- Assume that \(rank(x)>1\)
- i.e. the random pivot chosen is not the smallest element
- What will be the size of the left partition \((|L|)\)?
- Reminder: Only the elements less than or equal to \(x\) will be in the left partition.
- Reminder: The pivot will stay in the right region after H-PARTITION if \(rank(x)>1\)
\(A=\{\overbrace{2}^{p}, 4 \underbrace{,}_{\Longrightarrow|L|=rank(x)-1}7,6,8,\overbrace{5,}^{pivot}\overbrace{9}^r\}\)
\(p=2,r=4\) \(pivot=x=5\)
TODO: convert to image...S6_P10
Various Outcomes of H-PARTITION - Summary (1)¶
-
\(x: pivot\)
-
\(|L|: \text{size of left region}\)
-
\(P(rank(x) = i) = 1/n \text{ for } 1 \leq i \leq n\)
-
\(\text{if } rank(x) = 1 \text{ then } |L| = 1\)
-
\(\text{if } rank(x) > 1 \text{ then } |L| = rank(x) - 1\)
-
\(P(|L| = 1) = P(rank(x) = 1) + P(rank(x) = 2)\)
-
\(P(|L| = 1) = 2/n\)
-
\(P(|L| = i) = P(rank(x) = i+1) \text{ for } 1< i < n\)
-
\(P(|L| = i) = 1/n \text{ for } 1< i < n\)
Various Outcomes of H-PARTITION - Summary (2)¶
Average - Case Analysis: Recurrence (1)¶
\(x=pivot\)
Average - Case Analysis: Recurrence (2)¶
for \(k=1,2,\dots,n-1\) each term \(T(k)\) appears twice once for \(q = k\) and once for \(q = n−k\)
Average - Case Analysis -Solving Recurrence: Substitution¶
- Guess: \(T(n)=O(nlgn)\)
- \(T(k) ≤ aklgk\) for \(k<n\), for some constant \(a > 0\)
- Need a tight bound for \(\sum klgk\)
Tight bound for \(\sum klgk\) (1)¶
- Bounding the terms
- \(\ \sum \limits_{k=1}^{n-1}klgk \leq \sum \limits_{k=1}^{n-1}nlgn = n(n-1)lgn \leq n^2lgn\)
- This bound is not strong enough because
- \(T(n) \leq \frac{2a}{n}n^2lgn+\Theta(n)\)
- \(=2anlgn+\Theta(n)\) \(\Longrightarrow\) couldn’t prove \(T(n) \leq anlgn\)
Tight bound for \(\sum klgk\) (2)¶
-
Splitting summations: ignore ceilings for simplicity $$ \sum \limits_{k=1}^{n-1}klgk \leq \sum \limits_{k=1}^{n/2-1}klgk + \sum \limits_{k=n/2}^{n-1}klgk $$
-
First summation: \(lgk < lg(n/2)=lgn-1\)
- Second summation: \(lgk < lgn\)
Splitting: \(\sum \limits_{k=1}^{n-1}klgk \leq \sum \limits_{k=1}^{n/2-1}klgk + \sum \limits_{k=n/2}^{n-1}klgk\) (3)¶
Substituting: - \(\sum \limits_{k=1}^{n-1}klgk \leq \frac{1}{2}n^2lgn-\frac{1}{8}n^2\) (4)¶
- We can choose a large enough so that \(\frac{a}{4}n \geq \Theta(n)\)
Q.E.D.
Medians and Order Statistics¶
-
ith order statistic: \(i^{th}\) smallest element of a set of \(n\) elements
-
minimum: first order statistic
-
maximum: \(n^{th}\) order statistic
-
median: “halfway point” of the set
Selection Problem¶
-
Selection problem: Select the \(i^{th}\) smallest of \(n\) elements
-
Naïve algorithm: Sort the input array \(A\); then return \(A[i]\)
-
\(T(n) = \theta(nlgn)\)
- using e.g. merge sort (but not quicksort)
-
Can we do any better?
Selection in Expected Linear Time¶
-
Randomized algorithm using divide and conquer
-
Similar to randomized quicksort
-
Like quicksort: Partitions input array recursively
-
Unlike quicksort: Makes a single recursive call
- Reminder: Quicksort makes two recursive calls
-
Expected runtime: \(\Theta(n)\)
-
Reminder: Expected runtime of quicksort: \(\Theta(nlgn)\)
Selection in Expected Linear Time: Example 1¶
- Select the \(2^{nd}\) smallest element:
- Partition the input array:
- make a recursive call to select the \(2^{nd}\) smallest element in left subarray
Selection in Expected Linear Time: Example 2¶
- Select the \(7^{th}\) smallest element:
- Partition the input array:
- make a recursive call to select the \(4^{th}\) smallest element in right subarray
Selection in Expected Linear Time (1)¶
R-SELECT(A,p,r,i)
if p == r then
return A[p];
q = R-PARTITION(A, p, r)
k = q–p+1;
if i <= k then
return R-SELECT(A, p, q, i);
else
return R-SELECT(A, q+1, r, i-k);
Selection in Expected Linear Time (2)¶
- All elements in \(L \leq\) all elements in \(R\)
- \(L\) contains:
- \(|L| = q–p+1\) \(=\) k smallest elements of \(A[p...r]\)
- if \(i \leq |L| = k\) then
- search \(L\) recursively for its \(i^{th}\) smallest element
- else
- search \(R\) recursively for its \((i-k)^{th}\) smallest element
Runtime Analysis (1)¶
- Worst case:
- Imbalanced partitioning at every level and the recursive call always to the larger partition
Runtime Analysis (2)¶
- Worst case: Worse than the naïve method (based on sorting)
- Best case: Balanced partitioning at every recursive level
- Avg case: Expected runtime – need analysis T.B.D.
Reminder: Various Outcomes of H-PARTITION¶
-
\(x: pivot\)
-
\(|L|: \text{size of left region}\)
-
\(P(rank(x) = i) = 1/n \text{ for } 1 \leq i \leq n\)
-
\(\text{if } rank(x) = 1 \text{ then } |L| = 1\)
-
\(\text{if } rank(x) > 1 \text{ then } |L| = rank(x) - 1\)
-
\(P(|L| = 1) = P(rank(x) = 1) + P(rank(x) = 2)\)
-
\(P(|L| = 1) = 2/n\)
-
\(P(|L| = i) = P(rank(x) = i+1) \text{ for } 1< i < n\)
-
\(P(|L| = i) = 1/n \text{ for } 1< i < n\)
Average Case Analysis of Randomized Select¶
- To compute the upper bound for the avg case, assume that the \(i^{th}\) element always falls into the larger partition.
- We will analyze the case where the recursive call is always made to the larger partition
- This will give us an upper bound for the avg case
Various Outcomes of H-PARTITION¶
Average-Case Analysis of Randomized Select (1)¶
Upper bound: Assume \(i^{th}\) element always falls into the larger part.
Average-Case Analysis of Randomized Select (2)¶
- \(n\) is odd: \(T(k)\) appears twice for \(k=\lceil n/2 \rceil+1,\lceil n/2 \rceil+2,\dots,n–1\)
- \(n\) is even:\(T(\lceil n/2 \rceil)\) appears once \(T(k)\) appears twice for \(k = \lceil n/2 \rceil +1, \lceil n/2 \rceil+2,\dots,n–1\)
Average-Case Analysis of Randomized Select (3)¶
- Hence, in both cases:
Average-Case Analysis of Randomized Select (4)¶
- By substitution guess \(T(n) = O(n)\)
- Inductive hypothesis: \(T(k) \leq ck, \forall k<n\)
Average-Case Analysis of Randomized Select (5)¶
- since we can choose c large enough so that \((cn/4+c/2 )\) dominates \(O(n)\)
Summary of Randomized Order-Statistic Selection¶
- Works fast: linear expected time
- Excellent algorithm in practise
-
But, the worst case is very bad: \(\Theta(n^2)\)
-
Blum, Floyd, Pratt, Rivest & Tarjan[1973] algorithms are runs in linear time in the worst case.
-
Generate a good pivot recursively
Selection in Worst Case Linear Time¶
//return i-th element in set S with n elements
SELECT(S, n, i)
if n <= 5 then
SORT S and return the i-th element
DIVIDE S into ceil(n/5) groups
//first ceil(n/5) groups are of size 5, last group is of size n mod 5
FIND median set M={m , …, m_ceil(n/5)}
// m_j : median of j-th group
x = SELECT(M,ceil(n/5),floor((ceil(n/5)+1)/2))
PARTITION set S around the pivot x into L and R
if i <= |L| then
return SELECT(L, |L|, i)
else
return SELECT(R, n–|L|, i–|L|)
Selection in Worst Case Linear Time - Example (1)¶
- Input: Array \(S\) and index \(i\)
- Output: The \(i^{th}\) smallest value
Selection in Worst Case Linear Time - Example (2)¶
Step 1: Divide the input array into groups of size \(5\)
Selection in Worst Case Linear Time - Example (3)¶
Step 2: Compute the median of each group (\(\Theta(n)\))
- Let \(M\) be the set of the medians computed:
- \(M = \{11, 27, 32, 17, 19, 10, 29, 24, 35\}\)
Selection in Worst Case Linear Time - Example (4)¶
Step 3: Compute the median of the median group \(M\)
\(x \leftarrow SELECT(M,|M|,\lfloor (|M|+1)/2 \rfloor)\) where \(|M|=\lceil n/5 \rceil\)
-
Let \(M\) be the set of the medians computed:
-
\(M = \{11, 27, 32, 17, 19, 10, 29, \overbrace{24}^{Median}, 35\}\)
-
\(Median = 24\)
-
The runtime of the recursive call: \(T(|M|)=T(\lceil n/5 \rceil)\)
Selection in Worst Case Linear Time - Example (5)¶
Step 4: Partition the input array \(S\) around the median-of-medians \(x\)
Partition \(S\) around \(x = 24\)
Claim: Partitioning around x is guaranteed to be well-balanced.
Selection in Worst Case Linear Time - Example (6)¶
- \(M\) : Median, \(M^*\) : Median of Medians
- About half of the medians greater than \(x=24\) (about \(n/10\))
Selection in Worst Case Linear Time - Example (7)¶
Selection in Worst Case Linear Time - Example (8)¶
Selection in Worst Case Linear Time - Example (9)¶
- Partitioning \(S\) around \(x = 24\) will lead to partitions of sizes \(\sim 3n/10\) and \(\sim 7n/10\) in the worst case.
Step 5: Make a recursive call to one of the partitions
Selection in Worst Case Linear Time¶
//return i-th element in set S with n elements
SELECT(S, n, i)
if n <= 5 then
SORT S and return the i-th element
DIVIDE S into ceil(n/5) groups
//first ceil(n/5) groups are of size 5, last group is of size n mod 5
FIND median set M={m , …, m_ceil(n/5)}
// m_j : median of j-th group
x = SELECT(M,ceil(n/5),floor((ceil(n/5)+1)/2))
PARTITION set S around the pivot x into L and R
if i <= |L| then
return SELECT(L, |L|, i)
else
return SELECT(R, n–|L|, i–|L|)
Choosing the Pivot (1)¶
- Divide S into groups of size 5
Choosing the Pivot (2)¶
- Divide S into groups of size 5
- Find the median of each group
Choosing the Pivot (3)¶
- Divide S into groups of size 5
- Find the median of each group
- Recursively select the median x of the medians
Choosing the Pivot (4)¶
- At least half of the medians \(\geq x\)
- Thus \(m = \lceil \lceil n/5 \rceil /2 \rceil\) groups contribute 3 elements to R except possibly the last group and the group that contains \(x\), \(|R|\geq 3(m–2)\geq \frac{3n}{10}–6\)
Choosing the Pivot (5)¶
- Similarly \(|L| \geq \frac{3n}{10}– 6\)
- Therefore, SELECT is recursively called on at most \(n-(\frac{3n}{10}-6)=\frac{7n}{10}+6\) elements
Selection in Worst Case Linear Time (1)¶
Selection in Worst Case Linear Time (2)¶
- Thus recurrence becomes
- \(T(n) \leq T \big( \lceil \frac{n}{5} \rceil \big) + T\big( \frac{7n}{10}+6 \big) + \Theta(n)\)
- Guess \(T(n)=O(n)\) and prove by induction
- Inductive step:
- Work at each level of recursion is a constant factor \((9/10)\) smaller
References¶
\(-End-Of-Week-3-Course-Module-\)