CS502 Assignment Solution 1 2019 | CS502 Assignment 1 Solution 2019

CS502 Assignment #1 Solution 2019

__________

CS502 Assignment

Solution 2019

Q#1) Consider the following five matrices A, B, C, D and E along their

dimensions;

A        B        C        D        E

(6x5)        (5x1)        (1x7)        (7x4)        (4x2)

Determine the Optimal Multiplication Order for the above matrices

using Dynamic Programing approach and also present the sequence

(i.e. optimal order) in binary tree.

Solution: -

First Super diagonal:

The matrix m now look as follows:

Second super diagonal this time, however, we will need to try two possible values for k. for

example, there are two possible splits for computing m [A, C]; we will choose the split that

yields the minimum:

The minimum m [A, C] =72

Occurs with K=1

Similarly, for m [B, D]:

Minimum m [B, D] =48 at K=3

For m [C, E]

Minimum m [C, E] = 36 at K=3

With the second super diagonal computed the matrix:

Repeat process diagonal the number of possible splits values of k increases:

Minimum m [A, D] =100 at k=3

Minimum m [B, E] =46 at k=3

The matrix at this stage is:

That leaves the m [A, E] which can now be computed:

Minimum m [A, E] = 78 at k=3

We thus have the final cost matrix.

Here is the order in which m entries are calculated:

And the split k values that led to a minimum m [I, j] values

Based on the computation, the minimum cost for the multiplying the five matrices is 78 and the

optimal order for multiplication is

((A(BC)) (DE))

This can be represented as a binary tree:

Q#2) CS502 Assignment 1 solution 2019

A. List down in and Out Degree of vertices of the given directed

graph.

Solution:

Vertex In-degree Out-degree

B. How many cycles are there in the given directed graph, list all of

them. Further, is there any Hamiltonian cycle in it(yes/no)?

Answer: -

    There are five cycles in the given directed graph.

______________________________________

DOWNLAOD

_____________________________________