20-CS-110-001 Introduction to Computer Science Fall 2010

Lab Number 4

Algorithms Revisited

Due: October 28, 2010
Submit two matlab programs as two separate files via blackboard. See submit page for instructions.

Rationale:
    You will translate to matlab code the results of Lab number 2, namely algorithmic descriptions of solutions to three problems that are restricted to operations that matlab can understand. I will do this for the shortest path problem to demonstrate what is entailed. Then you do something similar with the other two problems.

Submission:
    Please submit two matlab solutions to the problems presented below in two separate files via blackboard. See the submit page for details. The solutions should contain comments on how the input is to be specified.

Problem 1: Shortest Path
    The problem (See lab assignment 2 for background information, if necessary): Given a collection of cities, a listing of pairs of cities that are directly connected, and two distinguished cities Corigin and Cdest, find the minimum distance (shortest) path between Corigin and Cdest where distance of a path connecting two cities is defined as the number of intermediate cities encountered on that path.

An algorithm:

  1. Start out with all cities unassigned and set i to 0
  2. Assign value 0 to Corigin
  3. Repeat the following until Cdest is visited:
        Visit those unassigned cities that are connected directly to cities assigned the number which is the value of i and assign them the value of 1 plus the value of the number i. For each newly visited city record the neighbor from which it was reached in a variable called back. Increment i by 1.
  4. Trace a path from Cdest to Corigin using the path information saved in back of each city - that is the solution.

Restrictions due to computer limitations: Limitations of the computer environment do not allow this algorithm because the computer cannot perform several tasks simultaneously. However, we can use a Queue to simulate this effect. A Queue is a list where objects are added only on the right and removed only on the left. The operations available to a computer for this example are:

  1. Add a neighbor of the current city to the Queue
  2. Remove a city from the Queue and make it the current city

Revised algorithm that uses a Queue: We specify the input to the algorithm as a list of lists called cities. All cities are identified by numbers which correspond to list indices. The ith list in cities (that is, cities(i)) is a list of numbers, each of which is the identity of some city that is a neighbor of city i. Suppose the number of cities is n. Assume that the city of origin has identity 1 and the city of destination has identity n. The Queue will contain numbers that correspond to the identities of cities.

  1. Set current to 1
  2. Initialize the Queue
  3. Repeat the following:
  4.    Set neighbors = cities(current)   %% The list of neighbors of current
  5.    For all 1≤j≤length(neighbors) do the following:
  6.       If neighbors(j) equals n do the following:   %% we have reached the destination
  7.          Trace a path back to the origin
  8.          leave
  9.       end
  10.       If neighbors(j) has never been visited do the following:
  11.          Add neighbors(j) to the Queue
  12.          Record the city we came from (that is current) in some variable belonging to neighbor(j)
  13.       end
  14.    end
  15.    If the Queue is empty, leave
  16.    Otherwise remove a number from the Queue and make it current
  17. end

Now to translate to code. Create a vector called visited with the meaning that visited(i) takes the value 0 if the number i has not yet been placed in the queue and value 1 otherwise. Create another vector called back with the meaning that back(i) will eventually contain the identity of the next city after city i that is encountered on the backward trace of the shortest path from city n. Here is the code:

   output = 'ABCDEFGHIJK';             %% Only for the example shown below
   cities = input('>>> ');             %% so we can use characters as inputs -
   cities = cities-'A'+1;              %% remove "-'A'+1" for general algorithm
   visited = zeros(size(cities,1));   %% - then input will be a matrix of numbers
   back = zeros(size(cities,1));  
   visited(1) = 1;
   current = 1;
   queue = [];
   while 1
      neighbors = cities(current,:);   %% The list of neighbors of current
      for j=1:length(neighbors)        %% Look at every neighbor
         if neighbors(j) <= 0 break; end     %% break if at the end of the list
         if neighbors(j) == size(cities,1)  %% If we reached the destination...
	    fprintf('%c ',output(size(cities,1)));  
            while current != 1                  %% trace the path to origin
               fprintf('%c ',output(current));  %% via back, print the path,
               current = back(current);         %% and leave the program
            end
            fprintf('A\n');
            return;
         end
         if visited(neighbors(j)) == 0       %% If we have never visited the neighbor...
            back(neighbors(j)) = current;    %% save the city we came from,
            visited(neighbors(j)) = 1;       %% mark this neighbor visited,
            queue = [queue neighbors(j)];    %% and put it in the queue.
         end
      end
      if length(queue) == 0            %% If the queue is empty we are done...
         fprintf('No path from 1 to %d\n', size(cities,1));
         return;                       %% but there is not path to the destination
      end                              %% so print a message and leave.
      current = queue(1);              %% Otherwise, remove a city from the queue 
      queue = queue(2:length(queue));  %% and make it current.
   end 

Here is an example input:

   [ 'B' 'C' 'D' 'E'  0   0  ; 
     'A' 'C' 'D' 'E'  0   0  ; 
     'A' 'D' 'F' 'G'  0   0  ; 
     'A' 'B' 'C' 'E' 'F' 'H' ; 
     'A' 'B' 'D' 'F' 'G' 'H' ; 
     'B' 'C' 'D' 'E' 'H' 'I' ; 
     'C' 'E' 'H' 'K'  0   0  ; 
     'D' 'E' 'F' 'G' 'I'  0  ; 
     'F' 'H' 'J'  0   0   0  ; 
     'I' 'K'  0   0   0   0  ; 
     'G' 'J'  0   0   0   0 ]

Problem 2: Topological Sort
    The problem: Given a collection of component types, and a collection of dependencies, each between pairs of component types, produce a (horizontal) list of types so that, from left to right, no type depends on a type that is to its right in the list.

An algorithm: One way to solve this problem is depicted here. Study that description then use the applet below to help develop an algorithm that depends on using a Stack.

A Stack is a list where objects are added only on the left and removed only on the left. The operations available to a computer for this example are:

  1. Add a dependent component type of the current component type (called a neighbor of the current component) to the Stack
  2. Add the current component type to the Stack
  3. Remove a component type from the Stack and make it the current component type

Problem 3: Minimum Cost Network
    The problem: Given a collection of cities and the cost of routing power cables between every pair of cities, find the minimum cost network of cables that connects every pair of cities (as in problem 1 above). Network cost is the sum of the costs of all power cables used. Cables must be erected between cities. Cable junctions exist only at cities (splicing of a crossing pair of cables between cities is not allowed).

An algorithm: Use the applet below to come up with an algorithm for solving this problem. The solution is a collection of power cables, taken from the given collection. Initially, there are no cables in the solution. Your algorithm will add cables to the solution. There are at least the following two operations that are available:

  1. Place a power line in the solution
  2. Test whether the cities at opposite ends of a power line are already connected by power lines that have been added to the solution.
Here is a link to an input matrix where each row contains two city identities and a cost - each row corresponds to one cable.

here is the link