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.





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





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?





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





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




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.





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?