Review questions for final exam
-------------------------------

1. (Lecture 28)

Modify the following function so that it is more efficient.

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..
   for j=1:n
      w(i) = w(i) + P(i,j)*v(j);
   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.



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



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



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?



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



7. (Lecture 22)

Modify the following 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);
   sound(y,rate)
   % Let the soundbite play out and add a second...
   pause(L/rate + 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.



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 following 
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==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...
   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.