Solve the below question. Show every step you took to get to the answers. a) Fin
ID: 3592133 • Letter: S
Question
Solve the below question. Show every step you took to get to the answers.
a) Find an optimal parenthesization of a matrix-chain product whose sequence of dimension is <5, 2, 4, 7, 7, 3, 9, 7, 8, 8, 6, 3, 7, 5, 5>. Show all your step-by-step answer.
b) How many multiplications does this parenthesization require? Show all your step-by-step answer
c) How many multiplications are required for a parenthesization that multiplies the input matrices in their input order? Show all your step-by-step answer
Explanation / Answer
Input:
5 2 4 7 7 3 9 7 8 8 6 3 7 5 5
A) Parenthezation of Matrices
(A1((((((((((((A2A3)A4)A5)A6)A7)A8)A9)A10)A11)A12)A13)A14))
B) No. of multiplication is required to multiply Matrices
960
C) Matrices Multiplication Table:
0 40 126 224 226 340 446 568 696 772 778 860 910 960
0 0 56 154 196 250 376 488 616 712 748 790 860 910
0 0 0 196 231 339 504 684 876 996 1014 1098 1179 1254
0 0 0 0 147 336 483 672 864 966 957 1104 1149 1224
0 0 0 0 0 189 336 525 717 819 810 957 1002 1077
0 0 0 0 0 0 189 357 549 693 747 810 897 972
0 0 0 0 0 0 0 504 952 1098 693 882 933 1008
0 0 0 0 0 0 0 0 448 720 504 651 714 789
0 0 0 0 0 0 0 0 0 384 336 504 561 636
0 0 0 0 0 0 0 0 0 0 144 312 369 444
0 0 0 0 0 0 0 0 0 0 0 126 195 270
0 0 0 0 0 0 0 0 0 0 0 0 105 180
0 0 0 0 0 0 0 0 0 0 0 0 0 175
0 0 0 0 0 0 0 0 0 0 0 0 0 0
Description:
Minimum multiplication to 1and 2=109890
Minimum multiplication to 2and 3=40
Minimum multiplication to 3and 4=56
Minimum multiplication to 4and 5=196
Minimum multiplication to 5and 6=147
Minimum multiplication to 6and 7=189
Minimum multiplication to 7and 8=189
Minimum multiplication to 8and 9=504
Minimum multiplication to 9and 10=448
Minimum multiplication to 10and 11=384
Minimum multiplication to 11and 12=144
Minimum multiplication to 12and 13=126
Minimum multiplication to 13and 14=105
Minimum multiplication to 14and 15=175
Minimum multiplication to 1and 3=197802
Minimum multiplication to 2and 4=126
Minimum multiplication to 3and 5=154
Minimum multiplication to 4and 6=231
Minimum multiplication to 5and 7=336
Minimum multiplication to 6and 8=336
Minimum multiplication to 7and 9=357
Minimum multiplication to 8and 10=952
Minimum multiplication to 9and 11=720
Minimum multiplication to 10and 12=336
Minimum multiplication to 11and 13=312
Minimum multiplication to 12and 14=195
Minimum multiplication to 13and 15=180
Minimum multiplication to 1and 4=263792
Minimum multiplication to 2and 5=224
Minimum multiplication to 3and 6=196
Minimum multiplication to 4and 7=339
Minimum multiplication to 5and 8=483
Minimum multiplication to 6and 9=525
Minimum multiplication to 7and 10=549
Minimum multiplication to 8and 11=1098
Minimum multiplication to 9and 12=504
Minimum multiplication to 10and 13=504
Minimum multiplication to 11and 14=369
Minimum multiplication to 12and 15=270
Minimum multiplication to 1and 5=263890
Minimum multiplication to 2and 6=226
Minimum multiplication to 3and 7=250
Minimum multiplication to 4and 8=504
Minimum multiplication to 5and 9=672
Minimum multiplication to 6and 10=717
Minimum multiplication to 7and 11=693
Minimum multiplication to 8and 12=693
Minimum multiplication to 9and 13=651
Minimum multiplication to 10and 14=561
Minimum multiplication to 11and 15=444
Minimum multiplication to 1and 6=165061
Minimum multiplication to 2and 7=340
Minimum multiplication to 3and 8=376
Minimum multiplication to 4and 9=684
Minimum multiplication to 5and 10=864
Minimum multiplication to 6and 11=819
Minimum multiplication to 7and 12=747
Minimum multiplication to 8and 13=882
Minimum multiplication to 9and 14=714
Minimum multiplication to 10and 15=636
Minimum multiplication to 1and 7=307942
Minimum multiplication to 2and 8=446
Minimum multiplication to 3and 9=488
Minimum multiplication to 4and 10=876
Minimum multiplication to 5and 11=966
Minimum multiplication to 6and 12=810
Minimum multiplication to 7and 13=810
Minimum multiplication to 8and 14=933
Minimum multiplication to 9and 15=789
Minimum multiplication to 1and 8=264112
Minimum multiplication to 2and 9=568
Minimum multiplication to 3and 10=616
Minimum multiplication to 4and 11=996
Minimum multiplication to 5and 12=957
Minimum multiplication to 6and 13=957
Minimum multiplication to 7and 14=897
Minimum multiplication to 8and 15=1008
Minimum multiplication to 1and 9=286202
Minimum multiplication to 2and 10=696
Minimum multiplication to 3and 11=712
Minimum multiplication to 4and 12=1014
Minimum multiplication to 5and 13=1104
Minimum multiplication to 6and 14=1002
Minimum multiplication to 7and 15=972
Minimum multiplication to 1and 10=286330
Minimum multiplication to 2and 11=772
Minimum multiplication to 3and 12=748
Minimum multiplication to 4and 13=1098
Minimum multiplication to 5and 14=1149
Minimum multiplication to 6and 15=1077
Minimum multiplication to 1and 11=242470
Minimum multiplication to 2and 12=778
Minimum multiplication to 3and 13=790
Minimum multiplication to 4and 14=1179
Minimum multiplication to 5and 15=1224
Minimum multiplication to 1and 12=165613
Minimum multiplication to 2and 13=860
Minimum multiplication to 3and 14=860
Minimum multiplication to 4and 15=1254
Minimum multiplication to 1and 13=264526
Minimum multiplication to 2and 14=910
Minimum multiplication to 3and 15=910
Minimum multiplication to 1and 14=220640
Minimum multiplication to 2and 15=960
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.