Problem 1: Solving Recurrences (6 points) Derive solutions t…
Problem 1: Solving Recurrences (6 points) Derive solutions to the following recurrences. (a) \(T(n) = 9T\!\left(\tfrac{n}{3}\right) + n^2 \lg n\) (b) \(T(n) = 2T\!\left(\tfrac{n}{2}\right) + n^2\) Problem 2: Asymptotic Notations (4 points) A GPU team implements a blocked algorithm to compute many large dense matrix products in a graphics pipeline. Their algorithm splits an \(n \times n\) matrix pair into 8 independent subproblems of size \(n/3\) each (work on different tiles in parallel). Unfortunately, the tile-assembly and synchronization needed in the combine step are expensive, costing \(\Theta(n^{2.9})\) time per level. Let \(T(n)\) be the runtime (ignoring constant-factor parallel speedups). Does this tiled algorithm run asymptotically faster than Strassen’s algorithm (which runs in \(\Theta(n^{\lg 7}) \approx \Theta(n^{2.81})\))? Congratulations, you are almost done with Quiz 3. DO NOT end the Honorlock session until you have submitted your work to Gradescope. When you have answered all questions: Use your smartphone to scan your answer sheet and save the scan as a PDF. Make sure your scan is clear and legible. Submit your PDF to Gradescope as follows: Email your PDF to yourself or save it to the cloud (Google Drive, etc.). Click this link to go to Gradescope to submit your work: Quiz 3 Return to this window and click the button below to agree to the honor statement. Click Submit Quiz to end the exam. End the Honorlock session.