CIT 5960 2025 - HW4 (deadlines as per Gradescope)
This homework deals with the following topics
* sorting algorithms that are faster than n log n
* one question on DFS
• The homework has to be submitted in electronic form. as a pdf file. You can use any editing software you want in order to type up and then produce the pdf. No 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.
• Explain all the intermediate mathematical simplification steps.
• 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. Real code that has bugs could easily result in loss of points.
• You do not have to worry about tiny edge cases like empty arrays, empty lists etc.
• For these questions remember that the list of sorting algorithms that we have covered is selection sort, insertion sort, merge sort, quick sort, counting sort, and radix sort.
Student Name: 〈 Your Name 〉
Collaborators(if any) : 〈 Your Collaborators 〉(at most 2 other collaborators)
Questions
1. (3 points) You are giving an array of n 5-digit numbers. Instead of using the usual base 10 representation, you decide to convert all these numbers into a different base. Your new base is going to be m. Assume that to convert a single 5 digit number to base m there is a function that works in constant time.
Now after all numbers are converted to base m, you decide to run radix sort on these new numbers using a counting sort in each of the steps. What is the runtime going to be? Please explain.
2. (7 points) There is an n sized array which contains integers in the range [1, n3]. Which sorting algorithm (among the ones covered in class) should we use and why?
List all the sorting algorithms that we covered in lectures, tell us the big-O run time that each of them could take in this situation. Please explain why they would take that runtime.
No pseudocode needed here. The points are for the discussion of the algorithms.
3. (7 points) Watch this famous obama sorting video.
Bubble sort, an algorithm that we did not cover, is a Θ(n2) algorithm.
We’d like you to help the former president by discussing all the algorithms that we have covered in this class and whether or not they would be applicable in the situation that was provided to him.