COMP3600/6466 - Algorithms Semester 2, 2022 Tutorial 4
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
Semester 2, 2022
Tutorial 4
COMP3600/6466 - Algorithms
Exercise 1 Randomized Algorithms and Its Analysis
1. Recall RandQuickSort from the lecture. What value would the function Partition(A, p, r) returns if all elements of A[p, ··· ,r] have the same value? How should we change Partition(A, p, r) if we want this function to return「
⌋ when all elements of A[p, ··· ,r] have the same value?
2. Is it useful to analyse the worst case analysis of a randomized algorithm? Please explain why or why not.
3. Suppose A is an array of integers. Will the algorithms below return a random permutation of the input array? Please explain why or why not.
|
Algorithm 1 Permutation1(A) |
|
(a) 1: n = A.length 2: Let B[1 ··· n] be a new array 3: offset = Random(1, n) 4: for i = 1 to n do 5: dest = i + offset 6: if dest > n then 7: dest = dest − n 8: B[dest] = A[i] 9: return B |
|
Algorithm 2 Permutation2(A) |
|
(b) 1: n = A.length 2: for i = 1 to n do 3: Swap A[i] with A[Random(1,n)] |
2022-09-21