Scribd
Upload
3 views2 pages

CS 514 Homework 3: Graphs & Matrices

The document outlines Homework 3 for the CS 514 (Algorithms) course, instructed by Dr. G. G. Md. Nawaz Ali, due on 11/14/2022. It includes tasks related to a multistage graph, requiring the creation of an adjacency matrix, computation of cost and d arrays, and finding the shortest path, as well as a matrix chain multiplication problem with a cost matrix and parenthesization. The minimum cost for the matrix chain multiplication is stated to be 130.

Uploaded by

azamsyed811
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
3 views2 pages

CS 514 Homework 3: Graphs & Matrices

The document outlines Homework 3 for the CS 514 (Algorithms) course, instructed by Dr. G. G. Md. Nawaz Ali, due on 11/14/2022. It includes tasks related to a multistage graph, requiring the creation of an adjacency matrix, computation of cost and d arrays, and finding the shortest path, as well as a matrix chain multiplication problem with a cost matrix and parenthesization. The minimum cost for the matrix chain multiplication is stated to be 130.

Uploaded by

azamsyed811
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

CS 514 (Algorithms) Course instructor: Dr. G. G. Md.

Nawaz Ali

Homework 3

Please upload your solution file by 11.59 PM, 11/14/2022

1. Consider the following multistage graph, and do the followings:

a) Show the adjacency matrix of the graph

Int c[11][11]=

{{0,0,0,0,0,0,0,0,0,0,0},
{0,0,2,2,3,0,0,0,0,0,0},
{0,0,0,0,0,3,4,0,0,0,0},
{0,0,0,0,0,6,7,0,0,0,0},
{0,0,0,0,0,6,10,7,0,0,0},
{0,0,0,0,0,0,0,0,6,0,0},
{0,0,0,0,0,0,0,0,5,1,0},
{0,0,0,0,0,0,0,0,3,9,0},
{0,0,0,0,0,0,0,0,0,0,4},
{0,0,0,0,0,0,0,0,0,0,3},
{0,0,0,0,0,0,0,0,0,0,0},

b) Compute cost array (minimum cost from a vertex to sink) and d array (via vertex which
gives the minimum cost to sink).
Vertex 1 2 3 4 5 6 7 8 9 10
Cost 10 8 11 14 10 4 7 4 3 0
d 2 6 6 6 8 9 8 10 10 10

c) Finally, find the path with the minimum cost from source node (S) to sink node (t).
Shortest path = d (1,1) = 2
d (2,2) = 6
d (3,6) = 9
d (4,9) = 10
Shortest path is 1->2->6->9->10
Minimum Cost is = 10
2. Assume the following matrix chain multiplication:

A1 x A2 x A3 x A4 x A5 (Matrices)
3x2 2x4 4x5 5x3 3x5 (Dimensions)

a) Find the minimum cost of the above matrix chain multiplication

Cost matrix:
0 24 70 88 130
0 0 40 70 100
0 0 0 60 120
0 0 0 0 75
0 0 0 0 0

K matrix:
01111
00234
00034
00004
00000

Minimum cost = 130


b) Show the parenthesization of matrix chain multiplication based on the computed
minimum cost in 2(a).

A1 x A2 x A3 x A4 x A5
(A1 x ( ( ( A2 x A3) x A4) x A5))

You might also like