Scribd Logo
Upload

Welcome to Scribd!

  • 37 views

    Solution Assignment No. 5

    Uploaded by

    KhurramSadiq
    This document contains solutions to an assignment with 4 questions on matrix chain multiplication and Huffman coding. For question 1, the solution finds the optimal order of multiplying 6 matrices by using dynamic programming to fill a table with the minimum costs for each subproblem. Question 2 is left unanswered. Question 3 generates a Huffman code table for 10 letters based on their frequencies. It shows the step-by-step process of combining nodes into a Huffman tree. Question 4 provides the binary code for the string "HEADBEAFDEEDHIGH" using the codes from question 3.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    Solution Assignment No. 5

    Uploaded by

    KhurramSadiq
    37 views9 pages
    This document contains solutions to an assignment with 4 questions on matrix chain multiplication and Huffman coding. For question 1, the solution finds the optimal order of multiplying 6 matrices by using dynamic programming to fill a table with the minimum costs for each subproblem. Question 2 is left unanswered. Question 3 generates a Huffman code table for 10 letters based on their frequencies. It shows the step-by-step process of combining nodes into a Huffman tree. Question 4 provides the binary code for the string "HEADBEAFDEEDHIGH" using the codes from question 3.

    Original Description:

    ABC

    Original Title

    Fall2007_CS502_5_SOL

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    This document contains solutions to an assignment with 4 questions on matrix chain multiplication and Huffman coding. For question 1, the solution finds the optimal order of multiplying 6 matrices by using dynamic programming to fill a table with the minimum costs for each subproblem. Question 2 is left unanswered. Question 3 generates a Huffman code table for 10 letters based on their frequencies. It shows the step-by-step process of combining nodes into a Huffman tree. Question 4 provides the binary code for the string "HEADBEAFDEEDHIGH" using the codes from question 3.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    37 views9 pages

    Solution Assignment No. 5

    Uploaded by

    KhurramSadiq
    This document contains solutions to an assignment with 4 questions on matrix chain multiplication and Huffman coding. For question 1, the solution finds the optimal order of multiplying 6 matrices by using dynamic programming to fill a table with the minimum costs for each subproblem. Question 2 is left unanswered. Question 3 generates a Huffman code table for 10 letters based on their frequencies. It shows the step-by-step process of combining nodes into a Huffman tree. Question 4 provides the binary code for the string "HEADBEAFDEEDHIGH" using the codes from question 3.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    of 9

    CS502 (FALL 2007)

    Solution Assignment No. 5


    Q1 Solution: Consider the chain matrix multiplication of 6 matrices:
    A1
    A2
    A3
    A4
    A5
    A6
    (4x3) (3x6) (6x7) (7x5) (5x8) (8x2)
    Using Base case to fill the main diagonal
    0
    0
    0
    0
    0
    0
    First super diagonal can be filled with the following calculations.
    m [1,2]=m[1,1] + m[2,2] + p0.p1.p2 = 0 + 0 + 4.3.6 = 72
    m [2,3]=m[2,2] + m[3,3] + p1.p2.p3 = 0 + 0 + 3.6.7 = 126
    m [3,4]=m[3,3] + m[4,4] + p2.p3.p4 = 0 + 0 + 6.7.5 = 210
    m [4,5]=m[4,4] + m[5,5] + p3.p4.p5 = 0 + 0 + 7.5.8 = 280
    m [5,6]=m[5,5] + m[6,6] + p4.p5.p6 = 0 + 0 + 5.8.2 = 80

    0 72
    0 126
    0 210
    0 280
    0 80
    0

    Virtual University of Pakistan

    CS502 (FALL 2007)

    Second super diagonal can be filled with the following calculations.


    m [1,3]=m[1,1] + m[2,3] + p0.p1.p3 = 0 + 126 + 4.3.7 = 210 at K =1
    m [1,3]=m[1,2] + m[3,3] + p0.p2.p3 = 72 + 0 + 4.6.7 = 240 at K =2
    Minimum m[1, 3] = 210 at k = 1
    m [2,4]=m[2,2] + m[3,4] + p1.p2.p4 = 0 + 210 + 3.6.5 = 300 at K =2
    m [2,4]=m[2,3] + m[4,4] + p1.p3.p4 = 126 + 0 + 3.7.5 = 231 at K =3
    Minimum m[2, 4] = 231 at k = 3
    m [3,5]=m[3,3] + m[4,5] + p2.p3.p5 = 0 +280 + 6.7.8 = 616 at K =3
    m [3,5]=m[3,4] + m[5,5] + p2.p4.p5 = 210+ 0 + 6.5.8 = 450 at K =4
    Minimum m[3, 5] = 450 at k = 4
    m [4,6]=m[4,4] + m[5,6] + p3.p4.p6 = 0 + 80 + 7.5.2 = 150 at K =4
    m [4,6]=m[4,5] + m[6,6] + p3.p5.p6 = 280 + 0 + 7.8.2 = 392 at K =5
    Minimum m[4, 6] = 150 at k = 4
    0 72 210
    0 126 231
    0 210 450
    0 280 150
    0
    80
    0
    Third super diagonal can be filled with the following calculations.

    m[1, 4] = m[1, 1] +m[2, 4] + p0 p1 p4 = 0 + 231 + 4 3 5 = 291, k=1


    m[1, 4] = m[1, 2] +m[3, 4] + p0 p2 p4 = 72 + 210 + 4 6 5 = 402, k=2
    m[1, 4] = m[1, 3] +m[4, 4] + p0 p3 p4 = 210 + 0 + 4 7 5 = 350, k=3
    Minimum m[1, 4] = 291 at k = 1

    Virtual University of Pakistan

    CS502 (FALL 2007)

    m[2, 5] = m[2, 2] +m[3, 5] + p1 p2 p5 = 0 + 450 + 3 6 8 = 594, k=2


    m[2, 5] = m[2, 3] +m[4, 5] + p1 p3 p5 = 126 + 280 + 3 7 8 = 574, k=3
    m[2, 5] = m[2, 4] +m[5, 5] + p1 p4 p5 = 231 + 0 + 3 5 8 = 351, k=4
    Minimum m[2, 5] = 351 at k = 4
    m[3, 6] = m[3, 3] +m[4, 6] + p2 p3 p6 = 0 + 150 + 672=234, k=3
    m[3, 6] = m[3, 4] +m[5, 6] + p2 p4 p6 = 210 + 80 + 652 = 350, k=4
    m[3, 6] = m[3, 5] +m[6, 6] + p2 p5 p6 = 450 + 0 + 682 = 546, k=5
    Minimum m[2, 5] = 234 at k = 3
    0 72 210 291
    0 126 231 351
    0 210 450 234
    0 280 150
    0
    80
    0
    Fourth super diagonal can be filled with the following calculations.
    m[1, 5] = m[1, 1] +m[2, 5] + p0 p1 p5 = 0 + 351 + 4 3 8 = 447, k=1
    m[1, 5] = m[1, 2] +m[3, 5] + p0 p2 p5 = 72 + 450 + 4 6 8 = 714, k=2
    m[1, 5] = m[1, 3] +m[4, 5] + p0 p3 p5 = 210 + 280 + 4 7 8 = 714, k=3
    m[1, 5] = m[1, 4] +m[5, 5] + p0 p4 p5 = 291 + 0 + 4 5 8 = 451, k=4
    Minimum m[1, 5] = 447 at k = 1
    m[2, 6] = m[2, 2] +m[3, 6] + p1 p2 p6 = 0 + 234 + 3 6 2 = 270, k=2
    m[2, 6] = m[2, 3] +m[4, 6] + p1 p3 p6 = 126 + 150 + 3 7 2 = 318, k=3
    m[2, 6] = m[2, 4] +m[5, 6] + p1 p4 p6 = 231 + 80 + 3 5 2 = 341, k=4
    m[2, 6] = m[2, 5] +m[6, 6] + p1 p5 p6 = 351 + 0 + 3 8 2 = 399, k=5
    Minimum m[2, 6] = 270 at k = 2

    Virtual University of Pakistan

    CS502 (FALL 2007)


    0 72 210 291
    0 126 231
    0 210
    0

    447
    351 270
    450 234
    280 150
    0
    80
    0

    Fifth super diagonal can be filled with the following calculations.


    P0
    P1
    P2
    P3
    P4
    4
    3
    6
    7
    5

    P5
    8

    P6
    2

    m[1, 6] = m[1, 1] +m[2, 6] + p0 p1 p6 = 0 + 270 + 4 3 2 = 294, k=1


    m[1, 6] = m[1, 2] +m[3, 6] + p0 p2 p6 = 72 + 234 + 4 6 2 = 354, k=2
    m[1, 6] = m[1, 3] +m[4, 6] + p0 p3 p6 = 210 + 150 + 4 7 2 = 416, k=3
    m[1, 6] = m[1, 4] +m[5, 6] + p0 p4 p6 = 291 + 80 + 4 5 2 = 411, k=4
    m[1, 6] = m[1, 5] +m[6, 6] + p0 p5 p6 = 447 + 0 + 4 8 2 = 511, k=5
    Minimum m[1, 6] = 294 at k = 1

    0 72 210 291
    0 126 231
    0 210
    0

    447
    351
    450
    280
    0

    294
    270
    234
    150
    80
    0

    The optimal order of multiplication is:


    A1[ A2 [A3 [A4 [A5 A6]

    Virtual University of Pakistan

    CS502 (FALL 2007)


    Q2 Solution: -

    Q3 Solution
    A
    200

    B
    210

    C
    511

    D
    131

    E
    971

    F
    833

    G
    677

    H
    594

    I
    748

    J
    147

    D
    131

    J
    147

    A
    200

    B
    210

    C
    511

    H
    594

    G
    677

    I
    748

    F
    833

    E
    971

    A
    200

    B
    210

    C
    511

    H
    594

    G
    677

    I
    748

    F
    833

    E
    971

    C
    511

    H
    594

    G
    677

    I
    748

    F
    833

    E
    971

    DJ
    278
    D
    131

    DJ
    278
    D
    131

    J
    147
    AB
    410

    J
    147

    A
    200

    B
    210

    Virtual University of Pakistan

    CS502 (FALL 2007)

    C
    511

    H
    594

    G
    677

    DJAB
    688

    I
    748

    DJ
    278
    D
    131
    G
    677

    I
    748

    DJ
    278
    D
    131
    I
    748

    F
    833

    J
    147
    E
    971

    A
    200

    F
    833

    B
    210
    E
    971

    H
    594

    H
    594

    G
    677

    CH
    1105
    C
    511

    H
    594

    B
    210

    CH
    1105

    CH
    1105
    C
    511

    A
    200

    AB
    410

    C
    511

    E
    971

    AB
    410
    J
    147

    DJAB
    688

    F
    833

    G
    677

    GDJAB
    1365
    DJAB
    688
    DJ
    AB
    278
    410
    D
    J
    A
    B
    131
    147
    200
    210

    GDJAB
    1365
    DJAB
    688
    DJ
    AB
    278
    410
    D
    J
    A
    B
    131
    147
    200
    210

    Virtual University of Pakistan

    IF
    1581
    I
    748

    F
    833

    E
    971

    CS502 (FALL 2007)

    G
    677

    GDJAB
    1365
    DJAB
    688
    DJ
    AB
    278
    410
    D
    J
    A
    B
    131
    147
    200
    210

    IF
    1581
    I
    748

    ECH
    2076
    E
    971

    F
    833

    E
    971

    CH
    1105
    C
    511

    H
    594

    GDJABIF
    2946

    CH
    1105
    C
    511

    ECH
    2076

    H
    594

    G
    677

    GDJAB
    1365
    DJAB
    688
    DJ
    AB
    278
    410
    D
    J
    A
    B
    131
    147
    200
    210

    IF
    1581
    I
    748

    F
    833

    ECHGDJABIF
    5022
    ECH
    2076
    E
    971

    GDJABIF
    2946

    CH
    1105
    C
    511

    H
    594

    G
    677

    GDJAB
    1365
    DJAB
    688
    DJ
    AB
    278
    410
    D
    J
    A
    B
    131
    147
    200
    210
    Virtual University of Pakistan

    IF
    1581
    I
    748

    F
    833

    CS502 (FALL 2007)

    ECHGDJABIF
    5022
    ECH
    2076
    CODE = 0
    E
    CH
    971
    1105
    CODE
    CODE = 01
    = 00
    C
    H
    511
    594
    CODE CODE
    = 010
    = 011

    GDJABIF
    2946
    CODE = 1
    GDJAB
    1365
    CODE = 10
    G
    677
    CODE
    = 100

    IF
    1581
    CODE = 11

    DJAB
    688
    CODE = 101
    DJ
    278
    CODE = 1010
    D
    J
    131
    147
    CODE CODE
    = 10100 = 10101

    AB
    410
    CODE = 1011
    A
    B
    200
    210
    CODE CODE
    = 10110 = 10111

    Alphabet Frequency Code


    A
    200
    10110
    B
    210
    10111
    C
    511
    010
    D
    131
    10100
    E
    971
    00
    F
    833
    111
    G
    677
    100
    H
    594
    011
    I
    748
    110
    J
    147
    10101
    Virtual University of Pakistan

    I
    748
    CODE
    = 110

    F
    833
    CODE
    = 111

    CS502 (FALL 2007)

    Q4 Solution: HEADBEAFDEEDHIGH = 01100101101010010111001011011110100000010100011110100011

    Virtual University of Pakistan

    You might also like