Midterm Project 3 - CS 3310

Chained Matrix Multiplication: Yao Solution (1982)

10/23/2020
Jordan Bui (BroncoID: 011821368)
CPP Fall 2020
CS 3310 Design and Analysis of Algorithms

Midterm Project 3: Code Implementation

Implementation for Chained Matrix Multiplication using the Yao Solution (1982) with Time Complexity of O(n²).

Chained Matrix Multiplication: Yao Solution (1982)

Chained Matrix Multiplication by dynamic programming, using Yao Solution, should demonstrates faster time complexity than matrix multiplication using the Godble Solution.

Time Complexity:
Yao Solution:

• T(n) = O(n²)

Godbole Solution:

• T(n) = O(n³)

Yao Solution Lecture (Google Docs)

Lecture explaining the process behind the Yao Solution for Chained Matrix Multiplication and analyzinging time and space complexity of the solution. Analysis shows the improvement of the Yao Solution from the Godbole Solution for Chained Matrix Multiplication.

Link:
https://docs.google.com/document/d/16rrxzhGv7-2wGN0f_olVrVS1bfS9ghyS4sgPIsDbK4w/edit?usp=sharing