Solutions to final review questions (Set 1)
-------------------------------------------

1. (Lecture 28)

Efficient implementation of Update given the property of P.

function w = Update(P,v)
% P is an n-by-n array of transition probabilities WITH THE
%   PROPERTY THAT P(i,j) IS ZERO IF |i-j|>1 .
% v is an n-by-1 state vector.
% w is the update of v.

n = length(v);
w = zeros(n,1);
for i=1:n
   % Compute the i-th component of the new state vector..
   if i==1
      w(1) = P(1,1)*v(1) + P(1,2)*v(2);
   elseif i==n
      w(n) = P(n,n-1)*v(n-1) + P(n,n)*v(n);
   else
      w(i) = P(i,i-1)*v(i-1) + P(i,i)*v(i) + P(i,i+1)*v(i+1);
   end
end



2. (Lecture 28)

Suppose G is a given n-by-n connectivity array with no columns that are 
zero.  Using the function

function [pR,pRValues] = PageRank0(G)
% G is an n-by-n connectivity array with no columns that are all zeros.
% pR is an n-by-1 array with the property that pR(j) is the page
%   rank of page j.

Write a script that prints the indices of all the webpages that have a 
link pointing to the page with the highest page rank.

[pR,pRValues] = PageRank0(G);
[val, idx]= sort(pR);
i= idx(1);  % Index of the page that has page rank 1
for j=1:n
   % G(i,j) = 1 if there is a link from page j to page i
   if G(i,j)==1
      disp(j)
   end
end



3. (Lecture 27)

Refer to the following function

function C = CensusData
% Packages the data that is in the files Names.dat, Pop.dat, and Rep.dat
%   to facilitate the analysis of US census data and how it is used to
%   determine the number of congressional seats for each state.
% There are 22 census dates: 1790, 1800,..., 2000.
%
% C is a length 22 structure array with these fields:
%
%   year The year of the census. (1790, 1800,...,2000).
%   states k-by-16 char array that names existing states during the census.
%   pop k-by-1 real array that specifies the state populations.
%   reps k-by-1 real array that specifies the state apportionments.

(a) Write a script that sets up a 22-by-1 real array small and assigns to 
small(i) the number of states that have just one representative as a result 
of the i-th census. (b) Write a script that sets up a 22-by-16 character 
array Gipped with the property that Gipped(i,:) is the name of the state 
that has the largest ratio of population to house seats as a result of the 
ith census. (Do these problems using built-in function max but be sure you 
can do them w/o using max.)

% Part a
C = CensusData;
small = zeros(22,1);
for i=1:22  % the ith census
    reps = C(i).reps;
    % Count how many entries of this array equal one..
    s = 0;
    for k=1:length(reps)  % the kth state
        if reps(k)==1
            s = s+1;
        end
    end
    small(i,1)= s;
end

%Part b
C = CensusData;
Gipped = char(zeros(22,16));
for i=1:22  % the ith census
    reps= C(i).reps;
    pop= C(i).pop;
    ratios= pop./reps;
    [val,k] = max(ratios);
    Gipped(i,:)= C(i).states(k,:);
end



4. (Lecture 24, 25)
Consider the following function:

function y = mergeSort(x)
% x is a column n-vector.
% y is a column n-vector consisting of the values in x sorted
%   from smallest to largest.

n = length(x);
if n==1
   y = x;
else
   m = floor(n/2);
   % Sort the first half..
   y1 = mergeSort(x(1:m));
   % Sort the second half...
   y2 = mergeSort(x(m+1:n));
   % merge...
   disp(’Call merge’)
   y = merge(y1,y2);
end

How many lines of output are produced by the call 
  y = mergeSort(rand(7,1))?

Everytime there is a merge, the message is printed. In the following
schematic, we show how the n=7 problem subdivides.  The notation
a:b means "the subproblem involving positions a to b of the original
vector."  We put < > around each subproblem that involves a merge.
So the answer is 6.

        <1:7>
        /    \
       /      \
      /        \
     <1:3>     <4:7>_____
     /   \         |      \
    /     \        |       \
   1:1   <2:3>    <4:5>    <6:7>
         /   \    /   \    /   \
        2:2 3:3  4:4 5:5  6:6 7:7



5. (Lecture 25)

Consider the function

function drawTriangle(x,y,level)
% x and y are length 3-arrays that define the vertices of a triangle.
% Draws recursively colored triangles;
% level is an integer that specifies the level of the recursion

Lmax = 2;  % Maximum recursion level

if level == Lmax
   % Recursion limit reached. Display triangle as yellow.
   fill(x,y,’y’)
else
   % Draw the triangle
     plot([x x(1)],[y y(1)],’k’)
   % Draw and color the interior triangle mauve
     a = [(x(1)+x(2))/2 (x(2)+x(3))/2 (x(3)+x(1))/2];
     b = [(y(1)+y(2))/2 (y(2)+y(3))/2 (y(3)+y(1))/2];
     fill(a,b,’m’)
   % Apply the process to the three "corner" triangles...
     drawTriangle([x(1) a(1) a(3)],[y(1) b(1) b(3)],level+1)
     drawTriangle([x(2) a(2) a(1)],[y(2) b(2) b(1)],level+1)
     drawTriangle([x(3) a(3) a(2)],[y(3) b(3) b(2)],level+1)
end

Assume that the length-3 vectors x and y define an equilateral triangle 
and that drawTriangle(x,y,0) is executed. What fraction of the original 
triangle is displayed yellow?

Assume that the original triangle has area 1.
The original triangle is partitioned into four sub-triangles, each with
  area 0.25.  (The interior triangle is colored mauve.)
Each of the corner triangles is subdivided just one more time so 
  each of these smaller triangle's area is 0.25*0.25.  The interior
  triangle is colored mauve while the corner triangles are colored yellow.
  There are 3*3 of these yellow triangles.

Thus, the final fraction is    (3*3)*(.25*.25) = 9/16



6. (Lecture 23)

Consider the following script:

% Sampling rate. This many numbers/sec in the digital signal:
Fs = 32768;
% Duration of the tone is .25 sec. So these are the sample times...
t = 0:(1/Fs):.25;
% The touchpad frequencies for the rows...
fR = [ 697 770 852 941];
% The touchpad frequencies for the columns...
fC = [ 1209 1336 1477];
Buttons = { ’1’, ’2’, ’3’; ’4’, ’5’, ’6’; ’7’, ’8’, ’9’; ’*’, ’0’, ’#’};
for i = 1:4
   for j = 1:3
      % Play tone associated with Buttons{i,j}
      % Select the two frequencies and add...
      yR = sin(2*pi*fR(i)*t);
      yC = sin(2*pi*fC(j)*t);
      y = (yR + yC)/2;
      sound(y,Fs);
      pause(1)
   end
end

Now write a script that plays the tones associated with the random phone 
number T = floor(rand(7,1)*10).

Fs = 32768;
t = 0:(1/Fs):.25;
fR = [ 697 770 852 941];
fC = [ 1209 1336 1477];
Buttons = { ’1’, ’2’, ’3’; ’4’, ’5’, ’6’; ’7’, ’8’, ’9’; ’*’, ’0’, ’#’};
T = floor(rand(7,1)*10)
for k=1:7
   m = T(k);
   % Determine the row and column of the button...
   if m==0
      i=4; j = 2;
   else
      i = ceil(m/3);
      r = rem(m,3);
      if r==0
         j=3;
      else
         j=r;
      end
   end
   yR = sin(2*pi*fR(i)*t);
   yC = sin(2*pi*fC(j)*t);
   y = (yR + yC)/2;
   sound(y,Fs);
   pause(1)
end



7. (Lecture 22)

Modify the given script so that it plays a randomly selected 
one-second excerpt from each of the .wav files. (You may assume that 
start to finish, each file plays for longer than one second.)

% Plays a sequence of sound bites

% Here are the names of some .wav files
PlayList = {’austin’,’sp_beam’,’sp_oz6’,’sp_truth’}

for k=1:length(PlayList)
   [y,rate] = wavread(PlayList{k});
   L = length(y);
   % A random integer between and including 1 and L-rate+1
     start = ceil(rand*(L-rate+1))
   sound(y(start:start+rate-1),rate)
   % Let the soundbite play out and add a second...
pause(1)
end



8. (Lecture 26)

Suppose z = MyF(x) is a function that accepts a real value x and 
returns a real value y.  Assume that MyF is very expensive to evaluate. 
Write a script that sets up an n-by-n array Z with the property that 
Z(i,j) is assigned the value of MyF(1+abs(i-j)).  Assume that n is 
initialized.

% Note that there are only n distinct x-values at which we need to
% evaluate MyF given the property of matrix Z.
for k=1:n
   w(k) = MyF(k);
end
for i=1:n
   for j=1:n
      Z(i,j) = w(abs(i-j)+1);
   end
end



9. (Lecture 26)

Assume that insertSort(x) is faster than mergeSort(x) if the length of 
the input vector is less than 500.  How would you modify the mergeSort 
function to make it more efficient?

function y = mergeSort(x)
% x is a column n-vector.
% y is a column n-vector consisting of the values in x sorted
%   from smallest to largest.

n = length(x);
if n<500
   y = insertSort(x);
else
   m = floor(n/2);
   % Sort the first half..
   y1 = mergeSort(x(1:m));
   % Sort the second half...
   y2 = mergeSort(x(m+1:n));
   % Merge...
   y = merge(y1,y2);
end



10. (Lecture 28)

Refer to the function tsp.  "Lazy evaluation" is used for calculating 
the distances between cities, i.e., a distance calculation between two 
cities is made immediately before that distance is needed.  Modify tsp 
to use a pre-computed distance matrix D where D(i,j) is the distance 
between cities i and j.  You may modify and/or add subfunctions as 
necessary.

See the separately posted code tsp2.m.
Compared to the original tsp code, these are the main changes:
  - (Call a subfunction to) calculate the distance matrix.
  - Subfunction nearest is modified to LOOK UP the distance data
    from the distance matrix instead of CALCULATING the distances.