Questions on sortings and medians

  • 11 févr. 2024
  • 20 nov. 2024
  • 7 min de lecture
  • llms.txt

Problem 1

Consider the following program

"\\begin{algorithm}\n\\caption{Sort$(L[0 \\ldots N])$}\n\\begin{algorithmic}\n\\REQUIRE $L$ is an array.\n \\WHILE{$L$ is not sorted}\n \\STATE $L \\gets$ a random permutation of $L$.\n \\ENDWHILE\n\\ENSURE $L$ is sorted.\n\\end{algorithmic}\n\\end{algorithm}"

Algorithm 18 Sort(L[0…N])(L[0 \ldots N])

Require: LL is an array.

1:while LL is not sorted do

2:L←L \gets a random permutation of LL.

3:end while

Ensure: LL is sorted.

Assume we can test that L is sorted Θ(∣L∣)\Theta(|L|) time, that we can compute a random permutation of L in Θ(∣L∣)\Theta(|L|) time.

P1.1

Does the SORTSORT program sort correctly? If yes, then provide an invariant for the while-loop and provide a bound function that can be used to prove the correctness of the program. If no, then argue why the program is not correct.

Solution

The program does sort correctly, but inefficiently, given enough time. This is known as Bogosort, as there are finite permutation in the list, one of them are the sorted array.

The invariant for the while-loop is as follow:

Invariant: 0<i<S∣Li is a permutation of L0∧S=n!\text{Invariant: } 0 < i < S \mid L_i \text{ is a permutation of } L_0 \land S = n!

This invariant holds through the while-loop because the permutation of the list is a permutation of the original list, and the number of permutations is n!n!.

The bound function for the while-loop is as follow:

  • The algorithm is probabilistic, and the expected number of iterations is n!n!.
  • The probability for get the sorted list is p=1n!p=\frac{1}{n!}.

One can use Bernoulli’s trial to find success probability pp. The cumulative probability of having sorted the list after kk attempts is 1−(1−1n!)k1 - (1 - \frac{1}{n!})^k

P1.2

Assume the program SORTSORT is correct. Is the program stable? Explain why.

Solution

The program is not stable since SORT is non-deterministic.

  • Each iteration generates a random permutation of the list. If the list contains duplicate elements, their relative order is then not reserved between permutations.
  • The algorithm does not consider the original order of elements when determine the list is sorted.

P1.3

What is the worst case runtime complexity of this program? What is the best case runtime complexity of this program? Is this program optimal? Explain your arguments.

Solution

Worst case scenario occurs when the algorithm goes through all n!n! permutations before finding the sorted list. The worst case runtime complexity is Θ(n!⋅n)\Theta(n! \cdot n).

Best case scenario occurs when the first generated permutation is the sorted list, which has the probability of 1n!\frac{1}{n!}, which has the runtime of Θ(n)\Theta(n) as it only needs to generate one random permutation and check for sorted.

No, the program is not optimal, since it is based on random permutation, and the expected number of iterations is n!n!. There are no guarantee that the algorithm is reliable to sort the list. Definitely not as optimal as other sorting algorithm such as merge-sort or heap-sort.

P1.4

What is the expected case runtime complexity of this program? Explain your answer.

Solution

Similar to previous mentioned, one can use Bernoulli’s trial to find success probability pp.

This probability pp of success of each run is 1n!\frac{1}{n!}, where nn is the number of elements in the list.

The expected case runtime complexity is Θ(n!⋅n)\Theta(n! \cdot n), since the expected number of iterations is n!n!. (since each permutation will take Θ(n)\Theta(n) time to check if array is sorted.

Problem 2

The median of a list LL of distinct values is the middle value v∈L\mathcal{v} \in L: an equal number of values in LL are smaller and larger than v\mathcal{v}. For example, in the list L=[1,5,4,2,3]L = [1,5,4,2,3], the median is 3. Consider two sorted lists A[0…N)\mathcal{A} \lbrack 0 \ldots N) and B[0…M)\mathcal{B} \lbrack 0 \ldots M) with N+MN + M distinct values. You may assume that the total number of values in A\mathcal{A} and B\mathcal{B} is odd (N+MN+M is odd). Hence, there is a value v∈(A∪B\mathcal{v} \in ( \mathcal{A} \cup \mathcal{B} such that an equal amount E=[N+M2]E = \lbrack \frac{N+M}{2} \rbrack of other values smaller and larger than vv.

P2.1

Provide an algorithm Median(A, B) that computes the median of the combined list A∪B\mathcal{A} \cup \mathcal{B} in O(log⁡2(N+M))\mathcal{O}(\log_2(N+M)) time.

Solution

"\\begin{algorithm}\n\\caption{Median$(A[0 \\ldots N), B[0 \\ldots M])$}\n\\begin{algorithmic}\n\\REQUIRE N < M $|A| \\leq |B|$\n\\STATE $N \\gets |A|$\n\\STATE $M \\gets |B|$\n\\STATE $L \\gets A \\cup B$\n\\STATE $low \\coloneqq 0$\n\\STATE $high \\coloneqq N$\n\\WHILE{$low \\leq high$}\n \\STATE $i \\coloneqq \\lfloor \\frac{low + high}{2} \\rfloor \\gets \\text{index of A}$\n \\STATE $j \\coloneq \\lfloor \\frac{N+M+1}{2} \\rfloor - i \\gets \\text{index of B}$\n \\STATE $A_{\\text{left}} = i > 0 \\space ? \\space A[i-1] \\space : \\space -\\infty$\n \\STATE $A_{\\text{right}} = i < N \\space ? \\space A[i] \\space : \\space \\infty$\n \\STATE $B_{\\text{left}} = j > 0 \\space ? \\space B[j-1] \\space : \\space -\\infty$\n \\STATE $B_{\\text{right}} = j < M \\space ? \\space B[j] \\space : \\space \\infty$\n \\IF{$A_{\\text{left}} \\leq B_{\\text{right}} \\land B_{\\text{left}} \\leq A_{\\text{right}}$}\n \\IF{$(N+M) \\mod 2 == 1$}\n \\RETURN $\\max(A_{\\text{left}}, B_{\\text{left}})$\n \\ELSE\n \\RETURN $\\frac{\\max(A_{\\text{left}}, B_{\\text{left}}) + \\min(A_{\\text{right}}, B_{\\text{right}})}{2}$\n \\ENDIF\n \\ELSIF{$A_{\\text{left}} > B_{\\text{right}}$}\n \\STATE $high \\gets i - 1$\n \\ELSE\n \\STATE $low \\gets i + 1$\n \\ENDIF\n\\ENDWHILE\n\\end{algorithmic}\n\\end{algorithm}"

Algorithm 19 Median(A[0…N),B[0…M])(A[0 \ldots N), B[0 \ldots M])

Require: N < M ∣A∣≤∣B∣|A| \leq |B|

1:N←∣A∣N \gets |A|

2:M←∣B∣M \gets |B|

3:L←A∪BL \gets A \cup B

4:low≔0low \coloneqq 0

5:high≔Nhigh \coloneqq N

6:while low≤highlow \leq high do

7:i≔⌊low+high2⌋←index of Ai \coloneqq \lfloor \frac{low + high}{2} \rfloor \gets \text{index of A}

8:j:−⌊N+M+12⌋−i←index of Bj \coloneq \lfloor \frac{N+M+1}{2} \rfloor - i \gets \text{index of B}

9:Aleft=i>0 ? A[i−1] : −∞A_{\text{left}} = i > 0 \space ? \space A[i-1] \space : \space -\infty

10:Aright=i<N ? A[i] : ∞A_{\text{right}} = i < N \space ? \space A[i] \space : \space \infty

11:Bleft=j>0 ? B[j−1] : −∞B_{\text{left}} = j > 0 \space ? \space B[j-1] \space : \space -\infty

12:Bright=j<M ? B[j] : ∞B_{\text{right}} = j < M \space ? \space B[j] \space : \space \infty

13:if Aleft≤Bright∧Bleft≤ArightA_{\text{left}} \leq B_{\text{right}} \land B_{\text{left}} \leq A_{\text{right}} then

14:if (N+M)mod  2==1(N+M) \mod 2 == 1 then

15:return max⁡(Aleft,Bleft)\max(A_{\text{left}}, B_{\text{left}})

16:else

17:return max⁡(Aleft,Bleft)+min⁡(Aright,Bright)2\frac{\max(A_{\text{left}}, B_{\text{left}}) + \min(A_{\text{right}}, B_{\text{right}})}{2}

18:end if

19:else if Aleft>BrightA_{\text{left}} > B_{\text{right}} then

20:high←i−1high \gets i - 1

21:else

22:low←i+1low \gets i + 1

23:end if

24:end while

P2.2

Explain why your algorithm is correct and why the complexity is Θ(log⁡2(N+M))\Theta(\log_2(N+M)).

Solution

The median of combined list A∪B\mathcal{A} \cup \mathcal{B} is the value v\mathcal{v} such that it either the maximum value of left elements or minimum value of right elements (since N+MN+M is odd). Additionally, it partitions the array such that left side will always contains ⌊M+N2⌋\lfloor \frac{M+N}{2} \rfloor elements.

Since it employs binary search on two smaller arrays and adjusting the partition A[i−1],A[i],B[j−1],B[j]A[i-1], A[i], B[j-1], B[j], it halves the search space through each iteration to smaller array.

Thus, one can then achieve the complexity (of binary search) as Θ(log⁡2(N+M))\Theta(\log_2(N+M)).

P2.3

Let P\mathcal{P} be an algorithm with complexity Θ(log⁡2(N+M))\Theta(\log_2(N+M)) that computes the middle value A∪BA \cup B. Argue how we can use PP to break up the Merge-step necessary to merge two sorted lists with N+M=2E+1N+M = 2E + 1 values into two independent Merge-steps that each merge only EE values.

Solution

After using P\mathcal{P} to find median of A∪B\mathcal{A} \cup \mathcal{B}, given that N+M=2E+1N+M = 2E+1, median will split the list into two halves, each with EE elements.

Partition A\mathcal{A} and B\mathcal{B} into two subsets Aleft,Aright\mathcal{A}_{\text{left}}, \mathcal{A}_{\text{right}} and Bleft,Bright\mathcal{B}_{\text{left}}, \mathcal{B}_{\text{right}} such that left subsets contains items ≤\leq median, right subsets contains geegee median.

Proceed with two independent Merge-steps that each merge only EE values for both lower and higher sets. Finally concatenate these two arrays into one sorted lists.

Overall complexity for the merge ops is O(2E)O(2E) as each sub-problem involves merging EE elements.

⌘ '
afficher les raccourcis clavier
raccourcis clavier

Liens retour

  • Aucun lien retour trouvé

Questions on sortings and medians

Problem 1

Consider the following program

"\\begin{algorithm}\n\\caption{Sort$(L[0 \\ldots N])$}\n\\begin{algorithmic}\n\\REQUIRE $L$ is an array.\n \\WHILE{$L$ is not sorted}\n \\STATE $L \\gets$ a random permutation of $L$.\n \\ENDWHILE\n\\ENSURE $L$ is sorted.\n\\end{algorithmic}\n\\end{algorithm}"

Algorithm 18 Sort(L[0…N])(L[0 \ldots N])

Require: LL is an array.

1:while LL is not sorted do

2:L←L \gets a random permutation of LL.

3:end while

Ensure: LL is sorted.

Assume we can test that L is sorted Θ(∣L∣)\Theta(|L|) time, that we can compute a random permutation of L in Θ(∣L∣)\Theta(|L|) time.

P1.1

Does the SORTSORT program sort correctly? If yes, then provide an invariant for the while-loop and provide a bound function that can be used to prove the correctness of the program. If no, then argue why the program is not correct.

Solution

The program does sort correctly, but inefficiently, given enough time. This is known as Bogosort, as there are finite permutation in the list, one of them are the sorted array.

The invariant for the while-loop is as follow:

Invariant: 0<i<S∣Li is a permutation of L0∧S=n!\text{Invariant: } 0 < i < S \mid L_i \text{ is a permutation of } L_0 \land S = n!

This invariant holds through the while-loop because the permutation of the list is a permutation of the original list, and the number of permutations is n!n!.

The bound function for the while-loop is as follow:

  • The algorithm is probabilistic, and the expected number of iterations is n!n!.
  • The probability for get the sorted list is p=1n!p=\frac{1}{n!}.

One can use Bernoulli’s trial to find success probability pp. The cumulative probability of having sorted the list after kk attempts is 1−(1−1n!)k1 - (1 - \frac{1}{n!})^k

P1.2

Assume the program SORTSORT is correct. Is the program stable? Explain why.

Solution

The program is not stable since SORT is non-deterministic.

  • Each iteration generates a random permutation of the list. If the list contains duplicate elements, their relative order is then not reserved between permutations.
  • The algorithm does not consider the original order of elements when determine the list is sorted.

P1.3

What is the worst case runtime complexity of this program? What is the best case runtime complexity of this program? Is this program optimal? Explain your arguments.

Solution

Worst case scenario occurs when the algorithm goes through all n!n! permutations before finding the sorted list. The worst case runtime complexity is Θ(n!⋅n)\Theta(n! \cdot n).

Best case scenario occurs when the first generated permutation is the sorted list, which has the probability of 1n!\frac{1}{n!}, which has the runtime of Θ(n)\Theta(n) as it only needs to generate one random permutation and check for sorted.

No, the program is not optimal, since it is based on random permutation, and the expected number of iterations is n!n!. There are no guarantee that the algorithm is reliable to sort the list. Definitely not as optimal as other sorting algorithm such as merge-sort or heap-sort.

P1.4

What is the expected case runtime complexity of this program? Explain your answer.

Solution

Similar to previous mentioned, one can use Bernoulli’s trial to find success probability pp.

This probability pp of success of each run is 1n!\frac{1}{n!}, where nn is the number of elements in the list.

The expected case runtime complexity is Θ(n!⋅n)\Theta(n! \cdot n), since the expected number of iterations is n!n!. (since each permutation will take Θ(n)\Theta(n) time to check if array is sorted.

Problem 2

The median of a list LL of distinct values is the middle value v∈L\mathcal{v} \in L: an equal number of values in LL are smaller and larger than v\mathcal{v}. For example, in the list L=[1,5,4,2,3]L = [1,5,4,2,3], the median is 3. Consider two sorted lists A[0…N)\mathcal{A} \lbrack 0 \ldots N) and B[0…M)\mathcal{B} \lbrack 0 \ldots M) with N+MN + M distinct values. You may assume that the total number of values in A\mathcal{A} and B\mathcal{B} is odd (N+MN+M is odd). Hence, there is a value v∈(A∪B\mathcal{v} \in ( \mathcal{A} \cup \mathcal{B} such that an equal amount E=[N+M2]E = \lbrack \frac{N+M}{2} \rbrack of other values smaller and larger than vv.

P2.1

Provide an algorithm Median(A, B) that computes the median of the combined list A∪B\mathcal{A} \cup \mathcal{B} in O(log⁡2(N+M))\mathcal{O}(\log_2(N+M)) time.

Solution

"\\begin{algorithm}\n\\caption{Median$(A[0 \\ldots N), B[0 \\ldots M])$}\n\\begin{algorithmic}\n\\REQUIRE N < M $|A| \\leq |B|$\n\\STATE $N \\gets |A|$\n\\STATE $M \\gets |B|$\n\\STATE $L \\gets A \\cup B$\n\\STATE $low \\coloneqq 0$\n\\STATE $high \\coloneqq N$\n\\WHILE{$low \\leq high$}\n \\STATE $i \\coloneqq \\lfloor \\frac{low + high}{2} \\rfloor \\gets \\text{index of A}$\n \\STATE $j \\coloneq \\lfloor \\frac{N+M+1}{2} \\rfloor - i \\gets \\text{index of B}$\n \\STATE $A_{\\text{left}} = i > 0 \\space ? \\space A[i-1] \\space : \\space -\\infty$\n \\STATE $A_{\\text{right}} = i < N \\space ? \\space A[i] \\space : \\space \\infty$\n \\STATE $B_{\\text{left}} = j > 0 \\space ? \\space B[j-1] \\space : \\space -\\infty$\n \\STATE $B_{\\text{right}} = j < M \\space ? \\space B[j] \\space : \\space \\infty$\n \\IF{$A_{\\text{left}} \\leq B_{\\text{right}} \\land B_{\\text{left}} \\leq A_{\\text{right}}$}\n \\IF{$(N+M) \\mod 2 == 1$}\n \\RETURN $\\max(A_{\\text{left}}, B_{\\text{left}})$\n \\ELSE\n \\RETURN $\\frac{\\max(A_{\\text{left}}, B_{\\text{left}}) + \\min(A_{\\text{right}}, B_{\\text{right}})}{2}$\n \\ENDIF\n \\ELSIF{$A_{\\text{left}} > B_{\\text{right}}$}\n \\STATE $high \\gets i - 1$\n \\ELSE\n \\STATE $low \\gets i + 1$\n \\ENDIF\n\\ENDWHILE\n\\end{algorithmic}\n\\end{algorithm}"

Algorithm 19 Median(A[0…N),B[0…M])(A[0 \ldots N), B[0 \ldots M])

Require: N < M ∣A∣≤∣B∣|A| \leq |B|

1:N←∣A∣N \gets |A|

2:M←∣B∣M \gets |B|

3:L←A∪BL \gets A \cup B

4:low≔0low \coloneqq 0

5:high≔Nhigh \coloneqq N

6:while low≤highlow \leq high do

7:i≔⌊low+high2⌋←index of Ai \coloneqq \lfloor \frac{low + high}{2} \rfloor \gets \text{index of A}

8:j:−⌊N+M+12⌋−i←index of Bj \coloneq \lfloor \frac{N+M+1}{2} \rfloor - i \gets \text{index of B}

9:Aleft=i>0 ? A[i−1] : −∞A_{\text{left}} = i > 0 \space ? \space A[i-1] \space : \space -\infty

10:Aright=i<N ? A[i] : ∞A_{\text{right}} = i < N \space ? \space A[i] \space : \space \infty

11:Bleft=j>0 ? B[j−1] : −∞B_{\text{left}} = j > 0 \space ? \space B[j-1] \space : \space -\infty

12:Bright=j<M ? B[j] : ∞B_{\text{right}} = j < M \space ? \space B[j] \space : \space \infty

13:if Aleft≤Bright∧Bleft≤ArightA_{\text{left}} \leq B_{\text{right}} \land B_{\text{left}} \leq A_{\text{right}} then

14:if (N+M)mod  2==1(N+M) \mod 2 == 1 then

15:return max⁡(Aleft,Bleft)\max(A_{\text{left}}, B_{\text{left}})

16:else

17:return max⁡(Aleft,Bleft)+min⁡(Aright,Bright)2\frac{\max(A_{\text{left}}, B_{\text{left}}) + \min(A_{\text{right}}, B_{\text{right}})}{2}

18:end if

19:else if Aleft>BrightA_{\text{left}} > B_{\text{right}} then

20:high←i−1high \gets i - 1

21:else

22:low←i+1low \gets i + 1

23:end if

24:end while

P2.2

Explain why your algorithm is correct and why the complexity is Θ(log⁡2(N+M))\Theta(\log_2(N+M)).

Solution

The median of combined list A∪B\mathcal{A} \cup \mathcal{B} is the value v\mathcal{v} such that it either the maximum value of left elements or minimum value of right elements (since N+MN+M is odd). Additionally, it partitions the array such that left side will always contains ⌊M+N2⌋\lfloor \frac{M+N}{2} \rfloor elements.

Since it employs binary search on two smaller arrays and adjusting the partition A[i−1],A[i],B[j−1],B[j]A[i-1], A[i], B[j-1], B[j], it halves the search space through each iteration to smaller array.

Thus, one can then achieve the complexity (of binary search) as Θ(log⁡2(N+M))\Theta(\log_2(N+M)).

P2.3

Let P\mathcal{P} be an algorithm with complexity Θ(log⁡2(N+M))\Theta(\log_2(N+M)) that computes the middle value A∪BA \cup B. Argue how we can use PP to break up the Merge-step necessary to merge two sorted lists with N+M=2E+1N+M = 2E + 1 values into two independent Merge-steps that each merge only EE values.

Solution

After using P\mathcal{P} to find median of A∪B\mathcal{A} \cup \mathcal{B}, given that N+M=2E+1N+M = 2E+1, median will split the list into two halves, each with EE elements.

Partition A\mathcal{A} and B\mathcal{B} into two subsets Aleft,Aright\mathcal{A}_{\text{left}}, \mathcal{A}_{\text{right}} and Bleft,Bright\mathcal{B}_{\text{left}}, \mathcal{B}_{\text{right}} such that left subsets contains items ≤\leq median, right subsets contains geegee median.

Proceed with two independent Merge-steps that each merge only EE values for both lower and higher sets. Finally concatenate these two arrays into one sorted lists.

Overall complexity for the merge ops is O(2E)O(2E) as each sub-problem involves merging EE elements.