EECS215 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(n 3 ) and span O(lgn). 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.
my wechat：_0206girl
Don't hesitate to contact me
