Solutions to review questions for Prelim 2
------------------------------------------

1. allInterval

function B = allInterval(x,a,b)
% x is a length-n vector.
% B is assigned the value of 1 (true) if every x-value is in the
%   interval [a,b].
% B is assigned the value of 0 (false) if at least one of the x-values
%   is not in the interval [a,b].
% Your implementation should make effective use of a while-loop.

n = length(x);
B = (a <= x(1)) && (x(1) <= b);
k = 1;
% B is true if x(1),...,x(k) are in the interval...
while k<n && B
   k = k+1;
   % B "turns false" if x(k) not in [a,b]...
   B = (a <= x(k)) && (x(k) <= b));
end



2. TotalValue

% Refer to the Cost-Inventory application in Lecture 14.
% Complete the following function...

function T = totalValue(Inv,Cost)
% T is the total value of all the inventory in all the factories

[nFact,nProd] = size(Inv);
T = 0;
for i=1:nFact
   % Compute the value of factory i’s inventory
   S = 0;
   for j=1:nProd
      S = S + Inv(i,j)*Cost(i,j);
   end
   T = T + S;
end



3. Censoring text
% Refer to Lec 18 on characters and strings and implement the function
% censor WITHOUT "pre-building" the string of 'X's.  That is, replace the
% censored word one character at a time.

function D = censor(str, A)
% Replace all occurrences of string str in character matrix A, regardless
% of case, with 'X's.
% A is a matrix of characters.
% str is a string.  Assume that str is never split across two lines in A.
% D is A with 'X's replacing the censored string str.
%
% Example:   A = ['Use MATLAB  '; ...
%                 'in that lab.']
%
%   and      str = 'lab'
%
%   Then     D = ['Use MATXXX  '; ...
%                 'in that XXX.']

D= A;
B= lower(A);
s= lower(str);
ns= length(str);
[nr,nc]= size(A);

% Traverse the matrix to censor string str
for r= 1:nr
    for c= 1:nc-ns+1
        if  strcmp(s,B(r,c:c+ns-1))==1
            for k= 1:ns
                D(r,c+k-1)= 'X';
            end
        end
    end
end



4. TwoClicks

% Refer to Lecture 13 and the function RandomLinks(n).

A = RandomLinks(1000);

% Note that 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.
% Thus, if A(101,100) = 1 and A(200,101) = 1 then "yes".

if A(200,100)==1
   % One click away...
   disp(’yes’)
else
   % See if it is possible to reach in two clicks
   % Idea: Check the "1-click" pages to see if they link
   % to page 200. Quit as soon as success.
   Found = 0;
   k =0;
   while k<1000 && ~Found
      k = k+1;
      % Is page k a 1-click page?
      if A(k,100)==1
         % Is there a link to page k
         if A(200,k) == 1
            % There is a link on page k to page 200
            disp(’yes’)
            Found = 1;
         end
      end
   end
end



5. Checking for numbers in a vector/matrix

function B = vecHasNegAndPos(x)
% x is a length-n vector and n>=2
% B is assigned the value of 1 (true) if x has at least one component
%   that is strictly negative and at least one component that is
%   strictly positive.
% Otherise B should be assigned the value of 0.
% Your implementation should make effective use of a while-loop.

nPos = 0; % Number of positive components found so far.
nNeg = 0; % Number of negative components found so far;
k = 0;
while k<length(x) && (nPos==0 || nNeg==0)
    k = k+1;
    if x(k) > 0
        nPos = nPos + 1;
    end
    if x(k) < 0
        nNeg = nNeg + 1;
    end
end
B = (nPos>=1 && nNeg>=1);


function B = matHasNegAndPos(A)
% A is an m-by-n real array with M>=2 and n>=2
% B is assigned the value of 1 (true) if A has at least one component
%   that has a strictly negative value and at least one component that has a
%   strictly positive value.
% Otherise B should be assigned the value of 0.
% Your implemention should make effective use of VecHasNegAndPos

[m,n] = size(A);
% Place all the values in A into a 1-dimensional array...
aVec = []
for i =1:m
   aVec = [aVec A(i,:)];
end
B = VecHasNegAndPos(aVec);



6. Reduce

function B = Reduce(A)
% A is an n-by-n array with n odd and at least 3 in value.
% B is obtained by deleting all the even-indexed rows and columns.
% Thus if
% A = [ 1  2  3  4  5 ;...
%       6  7  8  9 10 ;...
%      11 12 13 14 15 ;...
%      16 17 18 19 20 ;...
%      21 22 23 24 25 ]
% then
% B = [ 1  3  5;...
%      11 13 15;...
%      21 23 25]

[n,n] = size(A);
% Assemble all the odd rows
D = [];
for i=1:m
   if rem(i,2)==1
      D = [D ; A(i,:)];
   end
end
% Now assemble all the odd columns of D...
B = [];
for j=1:n
   if rem(j,2)==1
      B = [B D(:,j)];
   end
end



7.  Longest

function [len, ind] = longest(C)
% Find the longest string(s) in cell array C.
% C is an n-by-1 cell array of strings, n>=1.
% len is the length of the longest string in C.
% ind is a vector, possibly of length one, containing the index number(s) 
% of the string(s) with length len

% len records the length of the longest string from C{1} to C{k}
len = -1;
% ind records indicies of strings whose lengths are len
ind = [];

for k=1:length(C)
    l = length(C{k});
    if l == len
        ind = [ind k];
    elseif l > len
        ind = k;
        len = l;
    end
end





9. BigTriplets
function N = BigTriplets(A)
% Refer to Lectures 19 and 20.
% Suppose A is a length-50 structure array with two fields.
% 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



10.  Point struct

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

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



11.  Insight questions

--------------------
% Sec 7.1 #3
function [p,q] = maxEntry(A)
% A is m-by-n matrix
% p and q are indices with the property that |A(p,q)|>=|A(i,j)| for 
% all i and j that satisfy 1<=i<=m, 1<=j<=n

p = 1;
q = 1;
[m,n] = size(A);

for i =1:m
    for j=1:n
        if (A(i,j) > A(p,q))
            p = i;
            q = j;
        end
    end
end


--------------------
% Sec 9.1 #4
function s = Compress(t)
% t is a string
% s is obtained by deleting all the blanks in t.
% Thus, if t = 'ab cd efg ', the s should be assigned 'abcdef'

s= '';
k= 0;
for i= 1:length(t)
   if t(i)~=' '
      k= k+1;
      s(k)= t(i);
   end
end


--------------------
% Sec 9.1 #7
function k = FindSubstring(S1, S2)
%Find the first occurrence of string S1 in string S2.
%If S1 is a substring of S2 then k is the position of the first
%   matching character of the first match in S2.
%If s1 is not a substring of S2, then k is zero.

len1 = length(S1);
len2 = length(S2);
lastPos2Check= len2-len1+1;
k = 1;
while k <= lastPos2Check && strcmp(S1, S2(k:k+len1-1))==0
   k= k+1;
end
if k>lastPos2Check
   k= 0;
end


--------------------
% Sec 9.1 #9
% Frequencies of letters in a string

str = input('input a string:', 's');

x = CountLetters(str);
bar(x(1:26));
axis([0 27 0 1.1*max(x)]);
set(gca,'xTick',1:26)
xNames= cell(1,26);
for k= 1:26
   xNames{k}= char('a'+k-1);
end
set(gca,'xTickLabel',xNames)
shg


--------------------
function x = CountLetters(s)
% s is a string.
% x is a 26-by-1 vector with the property that x(1) is the number occurences
% of 'a' n s,x(2) is the number of occurences of 'b' is s, etc.

s= lower(s);
x= zeros(26,1);
for k = 1:length(s)
   binNumber= s(k)-'a'+1;
   if binNumber>=1 && binNumber<=26
      x(binNumber)= x(binNumber)+1;
   end
end


--------------------
% Sec 9.2  #5
function a = compare1(s1,s2)
% s1 and s2 are strings
% If s1 comes before or is equal to s2 in the ASCII dictionary order then a
% is 1. otherwise, a is 0. Case is ignored.

if (length(s1) < length(s2))
    for i = 1:length(s2)-length(s1)
        s1 = [s1 ' '];
    end
end

if (length(s2) < length(s1))
    for i = 1:length(s1)-length(s2)
        s2 = [s2 ' '];
    end
end

k = 1;
while (k < length(s1)) && (s1(k) == s2(k))
    k = k + 1;
end

if s1(k) <= s2(k) 
    a = 1;
else
    a = 0;
end


--------------------
%Chapter 10  Sec 1  #5
function P = RandomPointSet(n,a,b,c,d)
% P is a structure array of points selected randomly from the rectangle
% with vertices (a,c), (b,c), (a,d), and (b,d).

if a > c
    t = a;
    a = c;
    c = t;
end

if b > d
    t = b;
    b = d;
    d = t;
end

x = rand(n,1); 
y = rand(n,1);

for i=1:n
    P(i) = MakePoint(a + x(i)*(c - a), b + y(i)*(d - b));
end


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