[SOLVED] Cs5800 – algorithms problem set #4 problem #1 quicksort is a powerful divide-and-conquer sorting algorithm that can be described in just four lines of pseudocode.

CS5800 – Algorithms
Problem Set #4
Problem #1
Quicksort is a powerful divide-and-conquer sorting algorithm that can be described in just four lines of
pseudocode.
The key to Quicksort is the PARTITION(A, p, r) procedure, which inputs elements p to r of array A,
and chooses the final element x = A[r] as the pivot element. The output is an array where all elements
to the left of x are less than x, and all elements to the right of x are greater than x.
In class, we saw that there are very many techniques to partition the array. One nice technique covered
in the book was invented by Nico Lomuto (See page 171 of the class textbook). You can also watch a
quick youtube video here: https://www.youtube.com/watch?v=86WSheyr8cM. In this question, we will
use the Lomuto Partition Method. Please assume that the pivot is always the last (right-most) element
of the input array.
For example, if A = [2, 8, 7, 1, 3, 5, 6, 4], then the pivot element is x = A[8] = 4, and PARTITION(A, 1, 8)
returns the array [2, 1, 3, 4, 7, 5, 6, 8]. We then run PARTITION on the sub-arrays [2, 1, 3] and [7, 5, 6, 8].
(a) Demonstrate the Quicksort algorithm on the input array A = [3, 1, 5, 7, 6, 2, 4], showing how eventually the algorithm outputs the sorted array [1, 2, 3, 4, 5, 6, 7]. Clearly show all of your steps.
(b) When PARTITION is called on an array with n elements, we require n − 1 comparisons, since we
must compare the pivot element to each of the other n − 1 elements.
If the input array is A = [1, 2, 3, 4, 5, 6, 7], show that Quicksort requires a total of 21 comparisons.
(c) Determine an input array with 7 elements for which Quicksort requires the minimum number of
total comparisons.
Clearly demonstrate why your input array achieves the minimum number of comparisons, and
explain why there cannot exist a 7-element array requiring fewer comparisons than your array.
(d) Let A be an array with n = 2k − 1 elements, where k is some positive integer. Determine a formula
(in terms of n) for the minimum possible number of total comparisons required by Quicksort, as
well as a formula for the maximum possible number of total comparisons required by Quicksort.
Use your formulas to show that the running time of Quicksort is O(n log n) in the best case and
O(n
2
) in the worst case.

Problem #2
There are are about 44 LeetCode problems on Divide and Conquer techniques.
In this question, you will create a mini-portfolio consisting of two (two) LeetCode problems on Divide and Conquer, chosen from the following website.
Note that you can work with a partner to code up the problem but each person MUST do their own
analysis of the problem
https://leetcode.com/tag/divide-and-conquer/
As always, you may code your algorithms in the programming language of your choice.
Here is how your mini-portfolio will be graded.
(i) (5 points ) For each of the problems you are including in your mini-portfolio, provide the problem
number, problem title, difficulty level, and the screenshot of you getting your solution accepted by
LeetCode.

Note that the total points is 5 points for each problem and those points is dependent on the difficult
level – for each easy problem will be awarded 3 points, each medium problem will be awarded 4
points, and each hard problem will be awarded 5 points.
You may submit as many problems as you wish but you will receive a maximum of 5 points for
each problem and a total of 10 for the two problems.
You will get full credit for any correct solution accepted by LeetCode, regardless of how well your
runtime and memory usage compares with other LeetCode participants.
(ii) (5 points) For one of the problems you are including in your mini-portfolio, provide an analysis of
the run time of your algorithm. Be careful to only analyse what you created (i.e. your own code)
and not a general solution.
(ii) (5 points) For one of the problems you are including in your mini-portfolio, explain the various
ways you tried to solve this problem, telling us what worked and what did not work. Describe
what insights you had as you eventually found a correct solution. Reflect on what you learned from
struggling on this problem, and describe how the struggle itself was valuable for you.
The choice of problems is yours, though you may only include problems that took you a minimum of 30
minutes to solve.