CSC 477/677 Problems

Tuesday, October 9, 2013

1. Write pseudo-code for the Floyd Warshall algorithm.
2. Consider the following algorithm for solving the all-pairs shortest path problem in a directed graph of n nodes and m edges. The nodes are the integers from 1 to n. W(i,j) is the weight of the edge from i to j, if there is one; otherwise it is ∞. We assume that there are no negative cycles.
   

   for all i from 1 to n

   for all j from 1 to n

   V[i,j] = W(i,j)

   finished = false
   
   while not finished

   finished = true
   
   for all i from 1 to n

   for all j from 1 to n

   for all k from 1 to n

   if V[i,j]+V[j,k] < V[i,k] Error corrected.

   finished = false
   
   V[i,k] = V[i,j]+V[j,k]

   What is the worst case asymptotic time complexity of this algorithm, written in terms of n and m ?
   
   
3. Step through Dijkstra's algorithm to solve the following single source problem:
4. What is the worst case asymptotic time complexity for Dijkstra's algorithm, written in terms of n and m ?
5. What is the worst case asymptotic time complexity for Johnson's algorithm, written in terms of n and m ?
   
6. Find the longest common subsequence of the following two sequences:
7. You can get from WARM to COLD, using English four-letter words, in only four steps:
   
   WARM
   WARD
   CARD
   CORD
   COLD
   
   Describe an efficient algorithm for finding the smallest number of steps to change any four letter word to any other, using only English four letter words in your steps. You may assume that you have access to a file which contains a list of all four letter words in Engish.