Homework8_Solutions

pdf

School

University of Texas *

*We aren’t endorsed by this school

Course

360C

Subject

Computer Science

Date

Dec 6, 2023

Type

pdf

Pages

Uploaded by ConstableGiraffeMaster829

ECE360C: Algorithms Homework Assignment #8 University of Texas at Austin Due: October 27, 2023 (11:59pm) SOLUTIONS STUDENT CHOICE: Homework Assignment #8 – Solutions Solutions are for individual use only by students registered for ECE 360C in Spring 2023 semester. They should not be otherwise shared or posted. Problem 1: Remember [20 points] Answer the following true/false questions.

Homework Assignment #8: October 27, 2023 (11:59pm) 2 True False ⊠ □ In a divide and conquer algorithm, the conquer step involves a recursive call. □ ⊠ In a divide and conquer algorithm, the combine step is always the most computationally complex. □ ⊠ In a divide and conquer recurrence of the form T ( n ) = aT ( n/b ) + f ( n ), b is the number of sub problems that are created in the divide step. ⊠ □ In a divide and conquer recurrence of the form T ( n ) = aT ( n/b )+ f ( n ), f ( n ) is the total computational costs of the divide and combine steps. ⊠ □ In case 3 of the master method (i.e., when f ( n ) = Ω( n log b a + ϵ )), the divide and combine steps are relatively more expensive than the conquer step. ⊠ □ By the master method, T ( n ) = T ( n/ 2) + O (1) is equal to O (log n ). □ ⊠ The runtime of MergeSort is dominated by the divide step. ⊠ □ The runtime of the closest pair of points algorithm is dominated by the fact that we have to sort the points by both x and y coordinates. □ ⊠ A recurrence of the form T ( n ) = aT ( n/b ) + cT ( n/d ) + f ( n ) can be solved by applying the master method twice and summing the results. ⊠ □ The following alternative code for mergesort still has a runtime of O ( n log n ): MergeSort ( A, p, r ) 1 if p < r + 5 2 then q ← ⌊ ( p + r/ 2) ⌋ 3 MergeSort ( A, p, q ) 4 MergeSort ( A, q + 1 , r ) 5 Merge ( A, p, q, r ) 6 else 7 InsertionSort ( A, p, r )

Homework Assignment #8: October 27, 2023 (11:59pm) 3 Problem 2: Understand [20 points] Calculate the time complexity of the below divide-and-conquer algorithm via a recurrence relation. Assume addition is O (1). Provide the recurrence relation and use the master method to solve it. getResult ( A [0 ...n − 1]) 1 if n = 0 return 0 2 elseif n = 1 return A [0] 3 i ← ⌊ n/ 4 ⌋ 4 R 1 ← getResult ( A [0 ... 2 i − 1]) 5 R 2 ← getResult ( A [ i... 3 i − 1]) 6 R 3 ← getResult ( A [2 i...n − 1]) 7 return R 1 + R 2 + R 3 If T ( n ) denotes the time it takes to run the above algorithm for an array of size n , then we have that T ( n ) = 3 T ( n/ 2) + O (1). Since any function that is O (1) is also O ( n log 2 3 ), we have that T ( n ) = O ( n log 2 3 ) by the Master Theorem.

Your preview ends here

Eager to read complete document? Join bartleby learn and gain access to the full version

Access to all documents
Unlimited textbook solutions
24/7 expert homework help

Homework Assignment #8: October 27, 2023 (11:59pm) 4 Problem 3: Apply [20 points] For many years, school finance has been a topic of debate and discussion in the state of Texas. You can read more about how school funding works in Texas here: https://www.texastribune.org/2019/02/15/texas-school-funding-how-it-works/ One important factor in understanding formulas for school funding is the level of funding per-pupil in a given school district. As a footnote, currently in Texas, per-pupil funding is determined based on attendance rather than on enrollment , which is the current key subject of the debate: https://www.texastribune.org/2023/02/06/texas-senators-school-finances/ From the above: The state gives schools a base amount of $ 6,160 per student, which has not increased since 2019. Districts receive additional funding based on other factors, including the number of students with special instructional needs in the district, such as bilingual students. To keep track of how schools are faring financially, it makes sense to compare statistics related to per-pupil funding between districts, and between regions across the state. In Texas, the state is divided into twenty regions that are each served by an Education Service Center (ESC), which provides regional support for things like student success, efficient operations, etc.: https://tea.texas.gov/about-tea/other-services/education-service-centers Consider the possibility that each ESC tracks the per-pupil funding rate for every district within the ESC by maintaining a list of the ESC’s districts, sorted from lowest per-pupil funding rate to the highest rate. To represent the central tendency of these values, we might compute various statistics like the mean, mode, and median. In this question, we will focus on the median. (a) As a warm-up, describe how to find the median per-pupil funding for all of the districts in a single ESC. Your algorithm should be as efficient as possible. State the runtime of your algorithm. (Seriously, don’t overthink this one.) Find the length of the sorted array, divide the length by two and return the entry in that index. The runtime of the algorithm is O (1).

Homework Assignment #8: October 27, 2023 (11:59pm) 5 (b) If two neighboring ESCs decide to collaborate on some programs, they may need to know the median across the union of their school districts’ per-pupil funding rates. Describe an efficient divide and conquer algorithm for finding the joint median of these two sorted arrays. Your algorithm should be as efficient as possible (hint: it should be more efficient than sorting the two lists together). Write and solve the recurrence for your algorithm. Assume both arrays are the same size. Consider the two sorted arrays, called them A and B . Find the median of A , call it m A , and the median of B , call it m B . All of this can be done in O (1). If m A = m B , we are done and we return m A . Otherwise, suppose WLOG m A < m B , find the median of the second half of A and the first half of B . The median of those two subarrays combined is equal to the median of the whole original array. The recurrence is T ( n ) = T ( n 2 ) + O (1). (c) [ This is a challenge problem. We’re interested in how you think about approaching this problem, so imagine it’s an interview question, where the goal is to think out loud rather than write the correct answer. ] How would you start to think about extending these ideas to find the median of three sorted arrays? More than three sorted arrays? Answers will vary.

Homework Assignment #8: October 27, 2023 (11:59pm) 6 Problem 4: Analyze [20 points] Use the Master Theorem to give a tight asymptotic bound for each of the following recurrences, or argue why it doesn’t apply. (a) T ( n ) = 3 T ( n/ 2) + Θ( n ) a = 3, b = 2. We compare f ( n ) = Θ( n ) with n log 2 3 = n 1 . 58 . Since the second is polynomially larger(with ϵ = 1 . 58 − 1), we have Case 1: T ( n ) = Θ( n log 2 3 ). (b) T ( n ) = 3 T ( n/ 2) + Θ( n 2 ) a = 3, b = 2. We compare f ( n ) = Θ( n 2 ) with n log 2 3 = n 1 . 58 . The second is polynomially smaller (with ϵ = 2 − 1 . 58), so we are candidates for Case 3. (We also check the technical condition: 3( n/ 2) 2 ≤ cn 2 for c = 3 / 4 < 1.) Thus: T ( n ) = Θ( n 2 ). (c) T ( n ) = 16 T ( n/ 2) + Θ( n 3 lg n ) a = 16, b = 2. We compare f ( n ) = Θ( n 3 lg n ) to n log 2 16 = n 4 . The second is polynomially larger so Case 1 applies: T ( n ) = Θ( n 4 ) (d) T ( n ) = 8 T ( n/ 2) + Θ( n 3 lg n ) a = 8, b = 2. We compare f ( n ) = Θ( n 3 lg n ) with n log 2 8 = n 3 . Since neither is polynomially larger, our version of the Master Theorem is not applicable. (The second version of the Master Theorem can give the result T ( n ) = Θ( n 3 (log n ) 2 ).)

Your preview ends here

Eager to read complete document? Join bartleby learn and gain access to the full version

Access to all documents
Unlimited textbook solutions
24/7 expert homework help

Homework Assignment #8: October 27, 2023 (11:59pm) 7 Problem 5: QuickSort Watch the following video for a quick overview of Quicksort: https://youtu.be/Hoixgm4-P4M?si=obDuS8wPqTjBoqzF The running time of Quicksort depends on both the data being sorted and the rule used to select the pivot element. Although Quicksort is Θ( n log n ) on average, certain combinations of data and pivots can cause Quicksort to take Θ( n 2 ). For each of the following, state whether the running time of Quicksort is Θ( n ), Θ( n log n ), or Θ( n 2 ), given a sorted input array. For each, provide a brief statement of your reasoning. (a) [5 points] Partition picks the pivot element to always be the last element in the subarray. Solution Θ( n 2 ). This is the worst possible choice; the recurrence is T ( n ) = T ( n − 1) + T (1) + Θ( n ) which is Θ( n 2 ). (b) [5 points] Partition picks the pivot element to always be the middle element in the subarray. Solution Θ( n log n ). This is the best possible choice; since the array is sorted, the element in the middle is also in the middle numerically; half of the elements will be to its left and half will be to its right. the recurrence is T ( n ) = 2 T ( n/ 2) + Θ( n ) which is Θ( n log n ). (c) [5 points] Partition picks the pivot element to always be the median of the first three keys of the subarray. Solution Θ( n 2 ). This is also the worst possible choice; there will only be one thing to the left of the pivot (the first element in the subarray) and everything else will be to the right. The recurrence is T ( n ) = T ( n − 1) + T (1) + Θ( n ) which is Θ( n 2 ). (d) [5 points] Partition picks the pivot element to always be the median of the first, last, and middle elements of the subarray. Solution Θ( n log n ). This is the best possible choice; since the array is sorted, the median of the array is also in the middle numerically; half of the elements will be to its left and half will be to its right. the recurrence is T ( n ) = 2 T ( n/ 2) + Θ( n ) which is Θ( n log n ).

Homework Assignment #8: October 27, 2023 (11:59pm) 8 Problem 6: Create [20 points] You are the agent for a band for which you would like to book a gig at a particular venue. You’ve found publicly available information about the popular times of the venue. Specifically, for every hour of a particular day of the festival, you know the estimated number of people expected at the venue. Assume that the popularity of the venue is unimodal on the given day, that is, the number of expected people increases up to a certain time, after which it only decreases. You would obviously like to schedule your band for the peak popular time. Assume that the popularity values for a given day are provided to you in an array, ordered by time. Give an efficient algorithm to find the peak popular time for the given venue on the given day. Write the recurrence for your algorithm and give its solution (e.g., using the Master Method). So this is basically a fancy binary search. Grab the middle value in the array. Look at the middle value, the one before, and the one after. If both the one before and the one after are both smaller, return the middle one since you’ve found your peak. If the one before is smaller and the one after is larger, recurse on the second half of the array. If the one before is larger and the one after is smaller, recurse on the first half of the array. This makes a single subproblem, one that is half the size of the original subproblem. Since the other work (divide and combine) are both O (1), giving a recurrence of T ( n ) = T ( n/ 2) + O (1)

Homework8_Solutions

Related Documents