AMERICAN INTERNATIONAL UNIVERSITY – BANGLASESH                 

                                          Department of computer science

                                           Sub: Algorithm (Section A, B, D )

                                    Course Teacher: Musfiq & Mashiour Rahman           

                                      Mid term: Summer 2003      Total marks: 50

 

  1. Answer any 4 of the following:

            

               a) Why we need to consider decreasing order of Finishing time while we  

                    topologically sort any graph?                       

 

                     b) What is the condition for a vertex to be an articulation point in DFS

                          approach?

 

                      c) Why bellmen-ford Algorithm for finding the single source shortest

                           path in a negative weighted graph works?

 

                      d) Why we call the prime’s Algorithm a greedy algorithm?

 

                      e) What are the basic difference between DFS and BFS approach?

 

  1. Run the Bellmen-Ford Algorithm and simulate the graph …. See Book Core men

      Page: 532

 

  1. Input :

Multiple Character will be inputted. The input will terminated by end of  file .

Process:

Convert each character to its equivalent ASCII character. Convert this ASCII value to its Binary equivalent.

Output:

Output the each of the characters and its corresponding Binary Values ( 8 bits ).

Sample   Input:

 alg

Sample Output:

  a: 01100001

   l: 01101100

  g: 01100111

  

  1. Simulate the algorithm of Topological Sort for the given graph showing the value  

            of Discovery time and Finishing Time for each vertex. After the simulating also

            draw the topological sorted graph.

                 See the page of Core men book: 487

   For the figure-1 draw the DFS Tree and identify the following from the DFS Tree

i)                    Back edge

ii)                  Cross edge

iii)                Forward edge

  1. Problem:

You are given a grid ( m X n ). The grid contains m x n positions. Each position contains either empty or block. A robot is placed at any place empty positions.

Lets call the position Source Position. The robot can move only to an empty position. The robot can move only in four direction: forward, backward , upward

And downward. And they take 1 unit time to travel 1 unit distance. Now your job is to determine the minimum number of time needed for the robot to reach to a given destination position on the grid.

 

Input:

The first line input contains two integers m(1<=m<=50) and n(1<=n<=50). M gives the total number of rows and n gives the total number of columns on the grid. Next b lines contains one integer b(0<=b<=1000),giving the number of blocks on the grid. Next b lines contains two integers r(l<=r<=m) and c(l<=c<=n)- the position of the blocks. Last line of the input will contain 4 integers r1, c1, r2 and c2.

Here r1 = Source row, c1 = source column, r2 = destination row and c2 = destination column.       

 

Output:

Output of the minimum time required to reach destination ( r2, c2 ) from source

( r1, c1 ).

Sample Input

5 5

7

1 4

2 1

2 3

3 1

3 4

4 3

4 4

1 2 2 4

Sample Output

11

 

 

1

2

3

4

5

1

 

S

 

B

 

2

B

 

B

D

 

3

B

 

 

B

 

4

 

 

B

B

 

5

 

 

 

 

 

 

S = Source Position

D = Destination Position

B = Block Position

 

 

a)      Implement the problem with DFS approach.

b)      Implement the problem with BFS approach.

c)      Write the algorithm to print path.

 

6. Write the algorithm to determine cycle in a directed graph. Discuss a method to remove  the cycle from the graph.