Skip to content

Latest commit

 

History

History
13 lines (7 loc) · 552 Bytes

README.md

File metadata and controls

13 lines (7 loc) · 552 Bytes

Hu-Shing-Algorithm-MCOP

Implementing the fastest Matrix Chain Ordering Problem algorithm (devised by Hu & Shing) to compute the number of operations needed for optimal ordering.

Our Python implementation compares Hu-Shing's O(nlogn) approach with a DP O(n^3) approach.

References

Hu-Shing Algorithm C++ Implementation: https://github.com/junodeveloper/Hu-Shing

Hu-Shing 1981 Paper: http://i.stanford.edu/pub/cstr/reports/cs/tr/81/875/CS-TR-81-875.pdf

Wikipedia: https://en.wikipedia.org/wiki/Matrix_chain_multiplication#Hu_&_Shing_(1981)