CSC4520 HW2: Runtime and QuickSort solution

$25.00

Category:

Description

5/5 - (4 votes)

The goal of this homework is to practice what we covered in Lecture This assignment is due on SEP 29, 2022 at 11:59PM Eastern Time. Most of this homework does not require coding, but instead, expects you to analyze existing code. Please read each question carefully. We’ve provided an example question and ideal answer in example.txt to help you get started on the runtime analysis questions. Submitting This Assignment iCollege Grading and Corrections Since this is a written assignment, There are no tests or examples. This assignment will be graded out of 10 points. The point values of each problem are listed in the title. We will use manual inspection and written rubrics to assign points in a fair, standardized way. Academic Integrity Remember that you can consult outside resources and work with other students as long as you write up your own solutions and cite any links or people you received help from within citations.txt. Q1 Mysterious Function (30 point) What’s the worst case runtime of the following function? Please remember to define n, provide a tight upper bound. public static void mystery1(int z) { System.out.println(z); if (z >= 10) { mystery1(z/10); System.out.println(z); } } Q2 Exponentiation (Fast?) (40 points) ● What’s the best case, worst case, and average-case runtime of pow? Assume n = power. Please remember to define n, provide a tight upper bound. algorithm pow Input: positive integer b, non-negative integer p Output: computing b^p (i.e. b raised to power of p) if p = 0 return 1 else if p = 1 return b else if p is even temp = pow(b, p / 2) return temp * temp else return b * b * pow(b, p-2) Q3 QuickSort (30 point) Given the QuickSort implementation from class, provide an 18-element list that will take the least number of recursive calls of QuickSort to complete. As a counter-example, here is a list that will cause QuickSort to make the MOST number of recursive calls: public static List input() { return Arrays.asList(0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0); } And here’s the QuickSort algorithm, for convenience: algorithm QuickSort Input: lists of integers lst of size N Output: new list with the elements of lst in sorted order if N < 2 return lst pivot = lst[N-1] left = new empty list right = new empty list for index i = 0, 1, 2, … N-2 if lst[i] <= pivot left.add(lst[i]) else right.add(lst[i]) return QuickSort(left) + [pivot] + QuickSort(right)