Review questions
-------------------------------------------

1. (Lecture 27)

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

Consider the function

function MeshTriangle(x,y,L)
% x and y are 3-vectors.  L is a nonnegative integer.
% Adds to the current figure window a level-L partitioning of the
%    triangle whose vertices are specified by the 3-vectors x and y.
% Assumes that hold is on.

if L==0
   % No subdivision required...
   fill(x,y,'y','linewidth',1.5)
else
   % A subdivision is called for...
   % Determine the side midpoints (a(1),b(1)), (a(2),b(2)), and (a(3),b(3))
   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];
   % Color the interior triangle magenta...
   fill(a,b,'m','linewidth',1.5)
   % Apply the process to the three "outer" triangles...
   MeshTriangle([x(1) a(1) a(3)],[y(1) b(1) b(3)],L-1)
   MeshTriangle([x(2) a(2) a(1)],[y(2) b(2) b(1)],L-1)
   MeshTriangle([x(3) a(3) a(2)],[y(3) b(3) b(2)],L-1)
end


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





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

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)

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

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?




8. (Lecture 27)

% Let A be a connectivity matrix, i.e.,
% if A(i,j) is one, then there is a link on webpage j
% to webpage i. Write a fragment that prints "yes" if it is
% possible to go from web page #100 to webpage #200 in one or two clicks.
% Assume that the number of webpages is >=200.
% Thus, if A(101,100) = 1 and A(200,101) = 1 then "yes".




9. Questions from "Insight":
      P10.1.5, P10.1.7
      P10.2.2, P10.2.7, P10.2.8, P10.2.10
      M10.3.1, P10.3.5
      P14.1.2, P14.1.3