Spring 2025 CIT 596 - HW3
This homework deals with the following topics
* Mergesort
* Quicksort
• The homework has to be submitted in electronic form as a pdf file. You can use any editing software you want in order to produce the pdf. No pictures of handwritten
solutions.
• For any algorithm that we have done in class that you want to use, you are allowed to say ”using Quicksort” or something like that. You are also allowed to just use its runtime without having to reprove it.
• For a question involving recursion, please express the time taken in the form of a recurrence and then you can use the master theorem (assuming the master theorem is applicable).
• For a question that involves an algorithm that we cover in class, you can use the final big-O result. No need to show the derivation again. For example, if binary search shows up in your algorithm you can just say “we know binary search is O(log n).”
• For all questions in this HW and subsequent HWs the goal is to find algorithms that are most efficient in terms of big-O analysis. You do receive partial credit if your algorithm is less efficient than the best. You do not receive credit though if your algorithm computes an incorrect result. So be sure to check for correctness before you worry about efficiency.
• Unless otherwise specified, you should write your algorithm analysis as “In the worst case, this algorithm is ....” .
• Reminder: Your algorithm should not rely on a fancy data structure in a particular language. Your algorithm needs to be in plain English or in pseudocode.
• You do not have to worry about tiny edge cases like empty arrays, empty lists etc.
Student Name: 〈 Your Name 〉
Collaborator(if any) : 〈 Your Collaborators 〉(at most 2 other collaborators.)
1. (5 points) You are given a huge array of numbers (could be integers or floats) and your task is to see whether the number 9798 is in this array or not. Two of your friends suggest methods to help you do this
• Friend 1 says just loop through the array and try to find the element.
• Friend 2 has heard of this cool thing called binary search so they ask you to first sort the array as quickly as you can and then apply this binary search idea.
Which of your friends are you going to listen to and why? Compare their answers in terms of their big-O run time. You are allowed to directly use results from lecture regarding the runtime of binary search or any other algorithm.
2. (5 points) What is the running time of quicksort if all the elements are identical? To answer this question please use the quicksort partition pseudocode in the textbook that has been copied here. The screenshot of that will be posted to Canvas.
This pseudocode shows you how to partition a subarray that starts from index p and goes all the way to index r. The pivot element being used in this partition is A[r].
Briefly explain your answer.
3. (6 points) Mergesort divides an array into 2 equally sized pieces. Consider modifying it to an algorithm called mergesort3. Instead of dividing into 2 pieces, divide into 3. Recursively sort the 3 pieces and then do a merge of the 3 pieces.
(a) Write pseudocode for a function that takes in 3 sorted arrays and returns a merged completely sorted array. Do this WITHOUT just simply calling the regular 2 argument merge twice.
(b) What is the time complexity of the function that merges 3 sorted arrays ? Give us a big-O expression. We are asking you for the time complexity of the 3 way merge and not of mergesort at this point.
(c) Write a recurrence relation (T(n) = ...) to express how the run time of mergesort with this 3 way merge algorithm can be computed recursively. Now use the master theorem to compute the big O of this mergesort.
(d) Is this new mergesort better than what we covered in class. in pure big-O terms.
4. (6 points) A percentile (or a centile) is a measure used in statistics indicating the value below which a given percentage of observations in a group of observations falls. For example, the 20th percentile is the value (or score) below which 20% of the observations may be found.
We want to take an array and a percentile value x. Then compute the value that will correspond to that percentile.
The way that a lot of statistics texts will do this is this 3 step process (https://goodcalculators.com/percentile-calculator/)
1. Arrange the data such that the entries span from the smallest to the largest values (ascending order).
2. Calculate an index i (the position of the pth percentile) as follows:
i = (p/100) ∗ n
3. If i is not an integer, round it up. The next integer greater than i represents the position of the pth percentile. If i is an integer, the pth percentile is the average of the values in positions i and i + 1.
For example,
computePercentile([1, 8, 2.8, 2, 5], 50) should return 2.8.
The steps from statistics make it seem like you have to do a complete sorting of the array. However, we can do a bit better.
Using the idea of quicksort’s partition, write an efficient algorithm in plain English (just explain the process here) to find percentile(array, x) to find the xth percentile of an array.
The analysis can be a bit tricky here, so you do not need to do that part in this question. You do have to explain why it would work. You can rely on what you have learned in lecture about partition and quicksort.
5. (10 points) For this question you have two types of objects - keys and locks. You can ‘compare’ a key to a lock by trying to fit one into the other. There are 3 possible results for the comparison - the key is too big, the key is too small, or they “match” . You cannot directly compare a key to a key, or a lock to a lock. Suppose you are given n keys and n locks. The keys are all different sizes, and there is a matching key to each lock.
1. Design an algorithm (the usual WEAPARTE stuff) that runs in expected O(nlgn) to correctly match each key to its corresponding lock.
Your algorithm should have O(nlog n) as the expected number of comparisons in its worst case.
2. What is the worst-case runtime of your algorithm? Please justify in 2 lines.