COS 2105 SET A 2 August2003
AMERICAN INTERNATIONAL UNIVESITY – BANGLADESH ( AIUB)
COS 2105 ALGORITHMS
Final term examination, B.Sc in computer science Summer 2003-2003
Full marks: 40 course teacher: Mashiour Rahman, Musfiq Rahman
Time : 2.0 hrs
Part A:
1. There are three question Answer any three:
the output for the following code
unsign int cost[ 10 ][ 10 ] = { { 0, 0, 0, 0, 0, 0},
9; 9; {0, 0, 3, 8, 10, -4 },
9; 9; {0, 10, 0, 10, 1, 7 }
{0, 10, 4, 0, 10, 10}
{0, 2, 10,-5, 0, 10 }
9; 9; {0, 10, 10, 10, 6, 0 }
};
void main( void )
{
int r, c, k, l, n = 5;
unsigned int c[ 10 ][ 10 ];
for ( l=2; l<n; l++ )
for( r=1; r<=n; r++ )
for( c=1; c<=n; c++ )
for( k=1; k<=n; k++ )
if ( Cost[ r ][ c ] > c[ r ][ k ] + c[ k ][ c ])
Cost[ r ][ c ] = c[ r ][ k ] + c[ k ][ c ];
for( r=1; r<=n; r++ ){
printf ( " \n" );
for ( c=1; c<=n; c++ ){
c[ r ][ c ] = Cost[ r ][ c ];
printf( "%5d" , Cost[ r ][ c ] );
}
}printf( " \n " );
}
}
2.
a) Write down the difference between Dynamic algorithm and Greedy algorithm.
b) Write Down the properties of Dynamic Algorithm.
c) Find out the longest common subsequence for the strings "algorithm" and "altruistic". Show all
of the simulation.
3. Find out the minimum number of required to multiply the matrix chain with following dimension (row, column)-(5,10),(10,3),(3,12),(12,5),(5,6). Show all the calculation, calculated matrix, path matrix, and the order.
Part B
There are three question answer any two:
1. write down the algorithm to find the order of multiplying a given matrix chain such that the number of required multiplication is minimized. Also write down a recursive method to multiply the matrix chain according to that order. Include all necessary data structure and procedures with explanation.
2. Write down the algorithm to find all pair shortest path for a given graph. Also find write down the method to find the path for all pairs. Include all necessary data structure and procedures and explanation.
3. Write down the algorithm to find the longest common subsequence between two given strings. Also write the method to generate the sequence.
Part C
Write complete code for the following problem.
The Problem
// PUSHING BOX PROBLEM WITH THREE DIMENSION .
Consider a 3 dimensional "box" given by its dimensions. In three dimensions the box (4,8,9) can represent a box 4 X 8 X 9 ( length, width, and height ).
In this problem you will analyze a property of a group of 3-dimensional boxes. You are to determine the longest nesting string of box bi nests in box bi+1( 1<= i<k ).