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.
Read DetailsHonorlock requires a small file to be downloaded before the…
Honorlock requires a small file to be downloaded before the assessment, but it does not collect personal information or data from you except for what is needed to proctor the assessment. The software is compliant with FERPA, which is a federal law protecting student privacy. Students have two options for taking the assessment: Option 1: Use a personal computer. Option 2: Use an RVC computer, preferably in the ERC. This option requires you to plan your assessment during normal business hours. Which option do you plan to use for the assessments in this course? NOTE: EAGLE will mark any answer you submit as “incorrect” because there is no way to program it to understand your preference. Scoring will be updated manually as I review the submissions.
Read Details