Solutions to review questions for Prelim 3
------------------------------------------

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 13.
% 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 17 on characters and strings and implement this function:

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

% Build a string of 'X's of the correct length
Xs= char(zeros(1,ns));  % not necessary, but good practice to 
                        % initialize to correct size and TYPE
for k= 1:ns
    Xs(k)= 'X';
end

% 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
            D(r,c:c+ns-1)= Xs;  % note that this is vectorized code
        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. Transpose

% Refer to Lecture 21 and the function TheDigits:

C = TheDigits();

% C is a length 10 cell array with the property that C{k} is
% a 7-by-5 bitmap of the digit k (regarding 0 as the "tenth" digit.)
% Produce a length 10 cell array D which houses 5-by-7 bitmaps
% of the "transposed" arrays. Thus, since
%
% C{1} looks like
% 00100
% 01100
% 00100
% 00100
% 00100
% 00100
% 01110
% then D{1} should look like
%
% 0000000
% 0100001
% 1111111
% 0000001
% 0000000
%
% Do not use the transpose operator '

D = cell(10,1);
for k=1:10
   % Produce the k-th transposed bit map
   M = C{k};
   % The transpose will be stored in MT...
   MT = zeros(5,7);
   % Examples: M(1,3) --> MT(3,1), M(7,5 )--> MT(5,7) etc
   for i=1:5
      for j=1:7
         MT(i,j) = M(j,i);
      end
   end
   D{k} = MT;
end



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



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



8.  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. TopHalf

function C = topHalf(A)
% Refer to Lecture 21.
% 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.
% 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.

% 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



10. BigTriplets
function N = BigTriplets(A)
% Refer to the Lectures 20 and 21.
% 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



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


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