Solutions to review questions
-------------------------------------------


1. TopHalf

function C = topHalf(A)
% Refer to Lecture 20.
% Suppose A is a length-50 structure array; each struct has two 
% fields: name and pop.
% Assume A(k).name is a string that names a state and A(k).pop
% is an integer whose value is the states population.
% Assume that the states are ordered alphabetically.
% C is a length-25 cell array of strings that names all the
% states whose populations are above the median state population.
% The states should be ordered alphabetically in C.


% Example solution 1

% Obtain a vector of populations...
pop = zeros(50,1);
for k=1:50
   pop(k) = A(k).pop;
end

% Find the population of the 26th largest state
spop= sort(pop);
big= spop(26);

% Identify the states whose pop is larger than "big"
idx= 0;
for k= 1:length(A)
    if A(k).pop>=big
        idx= idx + 1;
        C{idx}= A(k).name;
    end
end 


% Example solution 2

% Obtain a vector of populations...
pop = zeros(50,1);
for k=1:50
   pop(k) = A(k).pop;
end

[y,idx] = sort(pop);
% Note that idx(k) is the index of the kth smallest state.
% Above-the-median states have indices idx(26),..,idx(50).
% Put these indices in a single, length-25 vector

Above = idx(26:50);
% Without the following step the "big" states wont be assembled in alphabetical
% order...

Above = sort(Above);

% This assembles the state names in C...
C = cell(25,1);
for k=1:25
   j = Above(k);
   str = A(j).name;
   C{k} = str;
end



2. BigTriplets

function N = BigTriplets(A)
% Refer to Lecture 20.
% Suppose A is a length-50 structure array; each struct has two 
% fields: name and pop.
% Assume A(k).name is a string that names a state and A(k).pop
% is an integer whose value is the states population.
% We say that three different states form a "big triplet" if
% the sum of their populations is greater than 15 million.
% N is the number of big triplets.

N = 0;
for i=1:50
   for j=i+1:50
      for k=j+1:50
         if A(i).pop+A(j).pop+A(k).pop > 15000000
            N = N+1;
         end
      end
   end
end



3.  Point struct and sorting

% See Lectures 20 and 26.
% Given a structure array Pts where each structure has two fields, x and y,
% sort Pts so that the structures are in the order of 
% increasing distance from (0,0)
% Write two different scripts to solve this problem:
%  (a) Make effective use of built-in function sort.
%  (b) Use the INSERTION SORT algorithm; do not use built-in function sort.

% (a) Use built-in function sort

n = length(Pts);

% compute the distances
dist = zeros(n, 1);
for i=1:n
    dist(i)=sqrt(Pts(i).x^2+Pts(i).y^2);
end
% sort the distances
[s, idx] = sort(dist);

oldPts = Pts;

for i=1:n
    Pts(i) = oldPts(idx(i));
end


% (b) Use insertion sort

n= length(Pts);
dis= zeros(1,n);  % stores the distance of each point from the origin
dis(1)= sqrt(Pts(1).x^2 + Pts(1).y^2);

for i= 1:n-1
    % Sort dis(1:i+1) given that dis(1:i) is sorted
    dis(i+1)= sqrt(Pts(i+1).x^2 + Pts(i+1).y^2);
    j= i;
    need2swap= dis(j+1) < dis(j);
    while  need2swap
        % swap elements in dis array
        tempd= dis(j);
        dis(j)= dis(j+1);
        dis(j+1)= tempd;
        % swap elements in Pts array
        tempp= Pts(j);
        Pts(j)= Pts(j+1);
        Pts(j+1)= tempp;
        
        j= j-1;
        need2swap= j>0 && dis(j+1)<dis(j);
    end
end

% This version strictly uses insertion sort to deal with the dis and Pts 
% arrays "in parallel".  Another way is to use insertion sort on dis only 
% to determine the ordering and then use that ordering on the Pts array.
 




4. (Lecture 28)
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..
   yL = mergeSort(x(1:m));
   % Sort the second half...
   yR = mergeSort(x(m+1:n));
   % merge...
   disp(’Call merge’)
   y = merge(yL,yR);
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 26)

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?

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. (Lab 15)

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. (Lectures 27 and 28)

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




8. (Matrix)

% 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".

[n,m]= size(A);

if A(200,100)==1
   % One click away...
   disp(’yes’)
else
   % See if it is possible to reach in two clicks.
   % Quit as soon as success.
   Found = 0;
   k =0;
   while k<n && ~Found
      k = k+1;
      if A(k,100)==1
         % There is a link to page k from page 100
         if A(200,k) == 1
            % There is a link on page k to page 200
            disp(’yes’)
            Found = 1;
         end
      end
   end
end




9. (OOP)

Refer to class Interval from Lecture 24.  Implement the following function:

function idxs = greatestOverlap(iArray)
% Find the biggest pairwise overlap between Intervals in iArray.
% iArray is an array of Interval references.  iArray has a length greater than 1.
% idxs is a vector of length 2 storing the indices of the two Intervals in
%   iArray that overlap the most.  If there is not a pair of overlapping
%   Intervals in iArray, idxs is the empty vector.
% Write efficient code:  avoid unnecessary iteration.

idxs= [];
maxWidth= 0;  % width of overlap
n= length(iArray);
for i= 1:n-1
    for j= i+1:n
        olap= iArray(i).overlap(iArray(j));
        if ~isempty(olap) && olap.getWidth()>maxWidth
            maxWidth= olap.getWidth();
            idxs= [i j];
        end
    end
end



10. (OOP)

Implement the following class as specified:


classdef LengthUnit < handle
% A LengthUnit represents a length (distance) in imperial units: feet and
% inches.  The values are non-negative and inches must be less than 12.
    
    properties
       feet    % a non-negative integer value
       inches  % a non-negative value 
    end
    
    methods

        function L = LengthUnit(ft, in)
        % Constructor: Create a LengthUnit object with ft feet and in inches.
        % If one or both parameters are negative, halt the program and
        % display an error message.
            if nargin==2
                if ft<0 || in<0
                    error('LengthUnit object must have non-negative properties')
                else
                    % ft --> feet and inches
                    L.inches= 12*(ft - floor(ft));
                    L.feet= floor(ft);
                    % in --> feet and inches
                    in2ft= floor(in/12);  
                    inRemaining= in - in2ft*12;
                    L.feet= L.feet + in2ft;
                    L.inches= L.inches + inRemaining;
                end
            end
        end
        
        function ft = inFeet(self)
        % self references a LengthUnit.  ft is self represented in feet.
            ft= self.feet + self.inches/12;
        end
        
        function L = add(self, other)
        % self and other reference LengthUnits.  L references a new 
        % LengthUnit that is the sum of self and other.
            ft= self.feet + other.feet;
            in= self.inches + other.inches;
            L= LengthUnit(ft,in);
        end
        
        function yesno = isLongerThan(self, other)
        % self and other reference LengthUnits.  yesno is true (1) if
        % self is longer than other; otherwise yesno is false (0).
        % For full credit, make effective use of method inFeet.
            yesno= self.inFeet() > other.inFeet();
        end
        
    end %methods
    
end %classdef




11. (OOP)

Write a script that 

(a) generates 10 valuess, each uniformly random in (0,50). Let these
  random values be lengths in inches and use an array of LengthUnit objects
  to store these lengths.

(b) determines which LengthUnits are shorter than or equal in length to 
  the first LengthUnit in the array; display their indices and their
  lengths in feet.  Make efficient use of available methods in class
  LengthUnit.

%(a)
n= 10;
for k= 1:n
    inches= rand*50;
    array(k)= LengthUnit(0, inches);
end

%(b)
idxs= [];
for k= 2:n
    if array(1).isLongerThan(array(k))
        idxs= [idxs k];
    end
end
if isempty(idxs)
    disp('First LengthUnit is shortest or all LengthUnits have same length.')
else
    disp(' Index   Length')
    for k= 1:length(idxs)
        fprintf(' %4d %10f\n', idxs(k), array(idxs(k)).inFeet()) 
    end
end




----
Selected solutions from Insight problems
----

%Chapter 10  Sec 1  #7
function Q = ThirdVertex(P1,P2)
% P1 and P2 are distinct points with the same y-coordinate.
% Q is a point such that P1, P2, and Q define an equilateral
% triangle. The y-coordinate of Q should be greater than the
% y-coordinate of P1 and P2.

len = GetDist(P1, P2);

Q.x = (P1.x + P2.x) / 2;
Q.y = P1.y + sqrt(3)/2*len;



%Chapter 10  Sec 2  #2
function alfa = IsSquare(R)
% R is a rectangle structure.
% alfa is true if R is a square. Otherwise alfa is false.

alfa = (R.right-R.left) == (R.top-R.bot);



%Chapter 10  Sec 2  #7
function [Square, LeftOver] = Split(R)
% Split rectangle R into a square and a "leftover" rectangle.
% R, Square, and LeftOver are rectangle structures.

if ( (R.right - R.left) > (R.top - R.bot) )
   Square = MakeRect(R.left,R.left + R.top - R.bot, R.bot, R.top);
   LeftOver = MakeRect(R.left + R.top - R.bot, R.right, R.bot, R.top); 
else 
   Square = MakeRect(R.left, R.right, R.bot, R.bot + R.right - R.left);
   LeftOver = MakeRect(R.left, R.right, R.bot + R.right - R.left, R.top);
end



%Chapter 10  Sec 2  #8
function LittleRs = Subdivide(R)
% Divide rectangle R into four equal rectangles by connecting the midpoints
% of the opposite sides.
% R is a rectangle structure; LittleRs is a length 4 array of rectangles.

len1 = R.right - R.left;
len2 = R.top - R.bot;

LittleRs(1) = MakeRect(R.left, R.left + len1 / 2, R.bot,  R.bot + len2 /2);
LittleRs(2) = MakeRect(R.left + len1 / 2, R.right, R.bot, R.bot  + len2 /2);
LittleRs(3) = MakeRect(R.left + len1 / 2, R.right, R.bot + len2 / 2, R.top);
LittleRs(4) = MakeRect(R.left, R.left + len1 / 2, R.bot + len2 / 2, R.top);



%Chapter 10  Sec 2  #10
function area = OverlapArea(R1, R2)
% Return the area of the intersection of rectangles R1 and R2.

R1_Is_Above = R1.bot > R2.top;
R1_Is_Below = R2.bot > R1.top;
R1_Is_Right = R1.left > R2.right;
R1_Is_Left  = R2.left > R1.right;
if (R1_Is_Above || R1_Is_Below || R1_Is_Left || R1_Is_Right)
    area = 0;
else 
    area = (min(R2.top, R1.top) - max(R2.bot, R1.bot)) * ...
           (min(R2.right, R1.right) - max(R1.left, R2.left));
end



%Chapter 10  Sec 3  #1
function A = TriangleArea(T)
% A is the area of triangle T.

a = GetDist(T.A, T.B);
b = GetDist(T.C, T.B);
c = GetDist(T.C, T.A);

s = (a + b + c) /2;
A = sqrt(s * (s - a) * (s - b) * (s - c));



%Chapter 10  Sec 3  #5
function A = PolygonArea(V)
% V is a length n structure array of points with the property that 
% V(1), . . . ,V(n) are arranged clockwise around the unit circle. 
% Return the area of polygon P, which is the n-sided polygon obtained by 
% connecting the neighboring points.

A = 0;
cx = 0;
cy = 0;
for i=1:length(V)
    cx = cx + V(i).x;
    cy = cy + V(i).y;
end

cx = cx / length(V);
cy = cy / length(V);
C = MakePoint(cx, cy);

for i=1:length(V)
    j = i + 1;
    if j > length(V)
        j = 1;
    end
    T = MakeTriangle(V(i), V(j), C);
    A = A + TriangleArea(T);
end



%Chapter 14  Sec 1  #2
% Author: Chin Isradisaikul

function m=FactorialR(n)
% Return the factorial of n.
% n is a nonnegative integer.
% m is the factorial of n.

% base case: 0!=1
if n==0
    m=1;
else    % recursive case
    m=n*FactorialR(n-1);
end




%Chapter 14 Sec 1 #3 
% Author: Chin Isradisaikul

function t=Reverse(s)
% Nonrecursive version of string reversion.
% s is the string to be reversed.
% t is the reverse of s.

% determine the length of s
len=length(s);

% Initialize the reverse as the empty string.
t='';

% Use a for loop to reverse s by starting at the end of s, work backward to
% In general, if the position of s is i, then the position of t is len-i+1;
for i=len:-1:1
    t(len-i+1)=s(i);
end


function t=ReverseR(s)
% Recursive version of string reversion.
% s is the string to be reversed.
% t is the reverse of s.

% determine the length of s
n=length(s);

% base case: (n==1) s is the reverse of itself
if n==1
    % simply assign s (which is the reverse of s) to t
    t=s;
else
    % obtain the reverse of the last n-1 characters of s recursively
    subReverse=ReverseR(s(2:n));
    % append the first character of s to the reverse
    t=[subReverse s(1)];
end


% Script to compare reverse and reverseR:
% To compare the execution times for both versions of string reversion, we
% will reverse a long string many times and take the average of the total
% execution time.

% generate a long string
N=100;  % number of strings

% print table header
fprintf('  len    Nonrecursive       Recursive\n');
fprintf('-------------------------------------\n');

for n=1:N
    s='';
    len=n*10;   % length of string is 10 times the string number
    for i=1:len
        % simply assign a to each position of the string
        % s will be a long string of a's
        s(i)='a';
    end

    numIter=100;    % number of iterations

    % time the nonrecursive version
    tic
    % reverse s repeatedly
    for i=1:numIter
        Reverse(s); % ignore the result
    end
    timeN=toc;

    % time the recursive version
    tic
    % reverse s repeatedly
    for i=1:numIter
        Reverse(s); % ignore the result
    end
    timeR=toc;
    
    % display execution time
    fprintf('%5d %15.5f %15.5f\n',len,timeN/numIter,timeR/numIter);
end

% The recursive version is a little bit faster than the nonrecursive
% version.  However, if we used vectorized code in the nonrecursive
% version, then the nonrecursive version should be faster.