20CS110001  Introduction to Computer Science  Fall 2010 


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 C_{origin} and C_{dest}, find
the minimum distance (shortest) path between
C_{origin} and C_{dest} where
distance of a path connecting two cities is defined as the number of
intermediate cities encountered on that path.
An algorithm:
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:
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 i^{th} 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.
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:

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:
