Describing algorithm: In some problems you may be asked to describe an algoritha
ID: 3687565 • Letter: D
Question
Describing algorithm: In some problems you may be asked to describe an algoritham. Your descript should be in the form of s short essay. The essay should include the following: A description of the algorithm in pseudo code How your algorithm works? Demonstrate your algorithm using one worked example or diagram A proof (or indication) of the correctness of the algorithm An analysis of the funning time of the algorithm Given n flies fl, f2,..., f3 of length m1, m2,...m3, the optimal tape-storage problem is to find which order is the best to store them on a tape to get minimum cost of total retrieval time, sisuming that each retrieval starts with the tape rewound, each retrieval takes time equal to the length of the preceding files in the tape plus the length of the retrieval file, and that files are to be retrieved in reverse order. The greedy algorithm put the files on the tape in ascending order of size. Prove that this is the best order. Suppose it is stored the files in order. So, the total retrieval time = sigma^n_k = 1 sigma^k_j = 1 m_ij. Consider a positively weighted directed graph. Describe an efficient algorithm for finding a minimum weight simple cycle in the graph. Be sure to follow the algorithm description guidelines.Explanation / Answer
Problem 2:-
We have many algorithms to find the minimal weight simple cycle in the graph. But I think the Floyd Warshall ALgorithm is one of the
efficient algorithm to find the minimum directed cycle in the graph.
1) Pseudo Code of the Algorithm:-
Run Floyd-Warshall algorithm on the graph
minimum <- infinity
vertex <- None
for each pair of vertices (u,v)
if (distance(u,v) + distance(v,u) < minimum):
minimum <- distance(u,v) + distance(v,u)
pair <- (u,v)
return path(u,v) + path(v,u)
Actually this algorithm finds the smallest weighted path in the graph, but here in this algorithm we check for the cycles which have minimum weight.
2) How does your algorithm works??
The Floyd-Warshall algorithm finds shortest path between all pairs of vertices.
The algorithm is then very simple, go over all pairs (u,v), and find the pair that have the minimized distance(u,v)+distance(v,u), since this pair indicates a cycle from u to u
with weighted distance(u,v)+distance(v,u).This algorithm do not check for the self loops. If you need one then this algorithm needs to be modified accordingly.
3)Proof of Correctness of the Algorithm?
We will take the a bit of code snippet while implementing the algorithm.
void floydWarshall() {
for( int k = 0; k < n; k++ )
for( int i = 0; i < n; i++ )
for( int j = 0; j < n; j++ )
graph[i][j] = minimum( graph[i][j], graph[i][k] + graph[k][j] );
To prove correctness of FloydWarshall, we will demonstrate the following loop invariant:
after the kth iteration of the outer loop has finished, graph[i][j] contains D(k, i, j) for all i and j. Before the start
of the algorithm, the invariant is true because graph[i][j] contains the length of the shortest path from
i to j that only uses vertices i and j, with no intermediate vertices. Suppose the invariant is true after k
1 iterations. Then during iteration k, graph[i][j] will either not change (if the shortest path does not
need to use vertex k), or it will change to graph[i][k] + graph[k][j] if it improves the distance. graph
[i][k] is the length of the shortest path form i to k that uses vertices 0 through k, and graph[k][j] is
the length of the shortest path from k to j that uses vertices 0 through k. Hence, graph[i][j] becomes
the best of two alternatives – its old value (if vertex k does not help) or the shortest path from i to k to
j (if vertex k does help).
By induction, the loop invariant holds during each iteration of the outer loop. Hence, after the outer
loop has finished, graph[i][j] contains the length of the shortest path from i to j that is allowed to use
all existing vertices from 0 to n1. This shows the correctness of FloydWarshall.
4) Analysis of the running time of the algorithm.
As we can see from the below code snippet that, we have to loop thrice to process all the vertices in the graph.
void floydWarshall() {
for( int k = 0; k < n; k++ )
for( int i = 0; i < n; i++ )
for( int j = 0; j < n; j++ )
graph[i][j] = minimum( graph[i][j], graph[i][k] + graph[k][j] );
Since, the loop is run thrice to process the vertices, the complexity for each loop will be O(n), therefore for all the loop the total run time complexity
would be O(n3).
Problem 1:-
For the tape storage problem, we assume that we have 'N' programs that needs to be stored on the computer tape of length 'L' and associated with each program length 'Li'.
The conditions are:- 1<=i<=n and the summation of the program length should be less than 1.This is our problem description.
Now the output should be the permutation of all n! for which the MRT is minimised.
As this algorithm uses the Greedy approach, we have used the Knapsack methodology to solve this problem.The pseudo code for this problem is as under.
1) GREEDY(s, f)
1. n =length[s]
2. A ={a1}
3. i =1
4. for m = 2 to n
5. do if sm >= fi
6. then A A{am}
7. i = m
8. return A
2) How this algorithm works?
We always take the next shortest file and put it on the tape. Also we have more than one tape then we follow up with the same procedure to store the content in the non decreasing order.
The algorithm finds out the possible shortest by summing up the retreival time and finds out the mean time of retreival.
3) Proof of correctness of algorithm.
Consider an optimal activity selection S.
If a1 belongs S, then S is the desired selection.
Otherwise, let aj be the activity in S with the smallest finish time.
Every ak elongs S – {aj} has sk >= fj.
So, S – {aj}{a1} is also a set of compatible activities.
Thus, S – {aj}{a1} is an optimal selection.
4) The run time required for the algorithm.
Ans- on implementing this algorithm programmatically we can see that the main loop is executed n-1 times.
The insert operation happens to traverse the entire list and put the element in the non decreasing order. Thus, the running time is O(n2)