HW3. Recurrence and Sorting (22 of Sep, 23.59)
T1: Solve recurrences by Master Theorem. Describe their complexity class Theta( ).
Solve the following recurrences by Master method:
- T(n) = 4T(n/3) + n log(n).
- T(n) = 5T(n/6) + n
- T(n) = 7T(n/6) + n
- T(n) = 6T(n/3)+n**1.5
- T(n) = 6T(n/3)+n**log_3(6)*log(n)
- T(n) = 6T(n/3)+n**2
- T(n) = 2 T( 2/3 n) + n
T2. Explain why Master theorem would fail, for example on
- T(n) = T( n / sqrt(n) ) + n
- T(n) = T(n/2)+T(n/3) + n
- T(n) = T(n−1)+log(n)
Could you solve them by other means?
T3. Use computational means to assess growth of the T(n) functions from T1 and T2.
Your goal is to make recursive functions in code for all 10 functions (T1.1, T1.2 … T2.3) and calculate the actual values T(n). Probe n as powers 10, for example. You can find examples in here: https://colab.research.google.com/drive/11DcPSFi9KNiEwCch2s9TCjaTt_M0f7hQ#scrollTo=_gl2jiiiSdJ5
Calculate for each of the 10 functions the respective values for n from 10 up to 10**10 (10 billion) the average ratio by how much the T(n) grows with each 10-fold increase. How stable is that ratio? Can you relate that ratio to the class observed in T1 and T2?
T4. Find n when T(n) grows above threshold.
Find the smallest n1 for which respective T(n1) exceeds 1,000,000,000 (one billion) and the smallest possible n2 when T(n2) exceeds 1,000,000,000,000 (one trillion). Your goal is to use as few different tests for n as possible. E.g., use binary search or similar approaches to narrow down the search space over n, as T(n) is monotonically growing when n increases. Calculate the number of tests T(n) that you had to perform. Ignore the internal recursive calls, count only the top-level main call. Report nr of trials to find n1, n1, T(n1), nr of trials to identify n2, n2, T(n2).
Make another table with n1, n2 and the ratio of n2/n1 for this approximately 1000-fold increase in T(n). Sort the table in increasing order of n2 (fastest to slowest). Can you relate the n2/n1 and 1000-fold increase in T(n) to the Theta( g(n) ) class that you derived in T1, T2, and T3?
T5: Bucket Sort by distance from origin in 3D volume
Divide 10 000 points that are randomly uniformly distributed within the 3D sphere into 20 “buckets” by the distance from origin. The Sphere is centered at the origin (0,0,0).
Data generator: https://colab.research.google.com/drive/11_cMfMNJYfWrJM9kNIU9aRje-YwfMHVb#scrollTo=PpVVXrF_bpmW
Compare two approaches:
a) equal distance from origin (equal width), and
b) equal volume of the bucket (thinner but same volume slices on the outside)
What would you expect from each method? Report the results in the table and validate that equal volume works “as expected” and “works better”. How much better would expected equal bucket size actually be?
T6 (3p): Study the Akra–Bazzi theorem
The Akra–Bazzi theorem is a generalization of the Master Theorem for divide-and-conquer recurrences.
- Explain why it extends the Master Theorem. (1p)
- Analyze two recurrences where Master Theorem does not apply, but Akra–Bazzi does. (1p)
- Validate the results with the above computational approaches. (1p)