+971 55 359 3828 vuassassins@gmail.com

## CS502 – Fundamentals of Algorithms

In CS502 Fundamentals of Algorithms we have you covered with Digitized Past Papers From Fall of Mid Term and Final Term.

## NOTE: Tab/Click on Preparation Tab to take the MCQ’s Tests.

FINAL TERM
MID TERM
##### POSTED DATE:25-01-2019                    IDEA SOLUTION

Question # 1:
Consider the following five matrices A, B, C, D and E along with their dimensions;
A     B     C     D     E
(6×5) (5×1) (1×7) (7×4) (4×2)
Determine the Optimal Multiplication Order for above matrices using Dynamic Programming approach and also present the sequence (i.e. optimal order) in Binary Tree.
Question # 2:
List down In and Out- Degrees of vertices of the given directed graph

 Vertex In Degree Out Degree A 3 2 B 3 0 C 2 1 D 1 2 E 0 4

1. How many cycles are there in the given directed graph, list all of them. Further, is there any Hamiltonian cyclein it (yes/no)?

There is one cycles in this graph which are listed below.

1. A.A

Hamiltonian Cycle = no

CS502– Practice Quiz 1 CS502– Practice Quiz 2 1. 66. Compute the shortest-path weights bottom up FLOYD-WARSHALL(W, n)
Ref: Handouts Page No.161
Give a detailed example for 2d maxima problem

The problem with the brute-force algorithm is that it uses no intelligence in pruning out decisions. For example, once we know that a point pi is dominated by another point pj, we do not need to use pi for eliminating other points. This follows from the fact dominance relation is transitive. If pj dominates pi and pi dominates ph then pj also dominates ph; pi is not needed. Ref: Handouts Page No.17.

2. 67. How the generic greedy algorithm operates in minimum spanning tree?