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

1. (Lecture 28, 4/30)

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. (Lectures 25 and 26, 4/21 and 4/23)
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



3. (Lecture 27, 4/28)

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



4. (Lecture 23, 4/14)

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 touchtone phone pad frequencies for the rows...
fR = [ 697 770 852 941];
% The touchtone phone pad 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



5. (Lecture 22, 4/9)

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.)

% Here are the names of some .wav files
PlayList = {’austin’,’noCry’,’Casablanca’};

for k=1:length(PlayList)
   [y,rate] = wavread(PlayList{k});
   sound(y, rate)
   % Let the soundbite play out and add a second...
   pause(1)
end


% Solution
% Plays a sequence of sound bites

% Here are the names of some .wav files
PlayList = {’austin’,’noCry’,’Casablanca’};

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



6. (Lecture 26, 4/23)

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



7. (Lecture 26, 4/23)

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