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 ).

&#