Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

EECS 215

Design and Analysis of Algorithms

Homework 3

Due on Friday, December 8, 2023 by midnight

Reading: Chapters 26 and 33

(10 Points) Parallel all-pairs shortest paths

Give pseudocode for an efficient multithreaded implementation of the Floyd-Warshall algorithm, which computes shortest paths between all pairs of vertices in an edge-weighted graph. Analyze your algorithm.

(10 Points) Parallel matrix multiplication

Give pseudocode for a multithreaded algorithm that multiplies two n × n matrices with work O(n3 ) and span O(lg n). Analyze your algorithm.

(10 Points) Parallel quicksort

Give an efficient multithreaded algorithm for quicksort. Make your algorithm as parallel as pos- sible. Analyze your algorithm. Hint: To make your algorithm as parallel as possible, partitioning an array around a pivot also has to be parallel.

(25 Points) Parallel stencil computation

Solve problem 26-5 on page 787 in CLRS.

(25 Points) Gradient descent

Solve problem 33-1 on page 1038 in CLRS.