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
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?
Page: 532
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
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
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.