% Spring 2001  CS100m  Solutions to Review Questions for Prelim T2

% ======================================================================
 
% 1. note: both solutions share lots of code, so below is a unified solution,
%          with (b) first since it needs $j$, which is modified by (a)
%
%    note: what should happen for $d=0$?  
%          it turns out my version of matlab returns $[]$, so that's what the
%          code below does.

function i = mycolon(j,d,k)
% i = mycolon(j,d,k): return $i = j:d:k$

i0 = j:d:k; % only used in "part (c)"

% b) vectorized -- answer stored in $i2$ instead of $i$ in anticipation of (c)

    n = 1 + floor((k-j)/d); % length(j:d:k)
    i2 = [];
    if n>0
        i2 = [0 cumsum(ones(1,n-1))]; % 0:n-1
        i2 = j + d*i2; % j:d:k
    end

% a) without $:$ or any pre-defined functions

    i = [];
    % inv: [i j:d:k] = final answer
    while (d > 0 & j <= k) | (d < 0 & j >= k)
        i = [i j];
        j = j + d;
    end

% c) not requested: check $i = i2 = i0$

    if length(i) ~= length(i2) | length(i) ~= length(i0)
        error(sprintf('lengths disagree: %d ~= %d', length(i), length(i2)));
    end
    if any(i ~= i2 | i ~= i0)
        error('elements disagree');
    end

% ======================================================================

% 2. Include a correct and useful loop invariant for (a).

% note: both solutions share lots of code, so below is a unified solution.

function ok = checkisbn(isbn)
% ok = checkisbn(isbn): return "$isbn$ is a valid ISBN string?",
%                        where $isbn$ is any matlab value; case is ignored
%
% try: checkisbn(5), checkisbn(struct('a', 7, 'b', 'there')), checkisbn(1<2),
%      checkisbn('0812544501'), checkisbn('156389016X'),
%       checkisbn(0812544501),
%       checkisbn('812544501'),
%      checkisbn('0712544501')

    ok = 0; % for now, assume $isbn$ is bad
    if ischar(isbn) & length(isbn) == 10
        % now know $isbn$ is string of length 10
        ten = isbn(10); % last (10th) character of $isbn$
        nine = isbn(1:9); % first 9 characters of $isbn$
        isbn = upper(isbn); % remove case distinctions
        if all('0' <= nine & nine <= '9')
            % now know first 9 characters are digits
            if ten == 'X' | ('0' <= ten & ten <= '9')
                % now know last character is 'X' or digit

% a)            unvectorized:

                    i = 0; star = 0;
                    % inv: star = sum of first $i$ out of all 9 terms
                    while i ~= 9
                        i = i+1;
                        star = star + (isbn(i) - '0') * i;
                    end

% b)            vectorized: use $star2$ instead of $star$ for part (c)

                    star2 = sum((nine - '0') .* (1:9));

% "c)"          not requested: check $star == star2$

                    if star ~= star2
                        error('vectorizd and unvectorized disagree')
                    end

%               back to shared code:

                    check = rem(star, 11); % checksum
                    ok = (check == ten - '0') | (check == 10 & ten == 'X');
            end
        end
    end
 

% ======================================================================

% 3. forthcoming...

% ======================================================================

% 4. 

function [] = spring(x,y,k,dt,T)
% [] = spring(x,y,k,dt,T): plot the evolution of the system described below 
%      for $T$ time steps, using a stepsize of $dt$:
%      + vectors $x,y$ have same length $n>=2$.
%      + there are $n$ balls, numbered $1..n$.
%      + each ball has unit mass and radius 0 (is infinitely small)
%        and initially is at rest
%      + the initial position of ball $i$ is $(x(i),y(i))$, $i=1..n$
%      + ball $i$ is connected to ball $i+1$ ($i=1..n-1$) by 
%        a spring with rest length 0 and spring constant $k$
%
% example: spring(1:5, rand(1,5)*6-3, 1, .1, 100)

    n = length(x);
    vx = zeros(1,n); vy = zeros(1,n); % (vx(i),vy(i)) = velocity of ball i
    clf; hold on
    for t = 0:T
        plot(x,y,'o-')
        % compute accelerations (ax(i),ay(i)) for all balls i
            ax = zeros(1,n); ay = ax; 
            for i = 1:n
                if i > 1
                    ax(i) = ax(i) + x(i-1) - x(i);
                    ay(i) = ay(i) + y(i-1) - y(i);
                end
                if i < n
                    ax(i) = ax(i) + x(i+1) - x(i);
                    ay(i) = ay(i) + y(i+1) - y(i);
                end
            end
            ax = k * ax; ay = k * ay;
        % update positions and velocities -- position *before* velocity
            x = x + vx * dt; vx = vx + ax * dt;
            y = y + vy * dt; vy = vy + ay * dt;
    end

return

% ----------------------------------------------------------------------
% here is an implementation using matrices: observe how much shorter it is!
% ----------------------------------------------------------------------

function [] = spring2(p,k,dt,T)
% [] = spring(p,k,dt,T): plot the evolution of the system described below 
%      for $T$ time steps, using a stepsize of $dt$:
%      + vector $p$ is 2-by-$n$ matrix
%      + there are $n$ balls, numbered $1..n$.
%      + each ball has unit mass and radius 0 (is infinitely small)
%        and initially is at rest
%      + the initial position of ball $i$ is $p(:,i)$, $i=1..n$
%      + ball $i$ is connected to ball $i+1$ ($i=1..n-1$) by 
%        a spring with rest length 0 and spring constant $k$
%
% example: spring([1:5 ; rand(1,5)*6-3], 1, .1, 100)

    n = size(p,2);
    v = zeros(2,n);
    clf; hold on
    for i = 1:T
        plot(x,y,'o-')
        a = k * ([p(2:end) p(end)] + [p(1) p(1:end-1)] - 2*p);
        p = p + v * dt;
        v = v + a * dt;
    end


% ======================================================================

% 5a) no (other) vectors, $break$, or $return$; efficiency counts.

% Given vector $v$ of non-negative integers pre-sorted in ascending order,
% read numbers from $v$ until 1000 appears or run out of elements; print
% a horizontal histogram of the numbers (each "*" = 1 occurrence)
stopping = 1000; % stopping value
i = 1; % position of next element of $v$ to process
prev = 0; % previous number, for which all output has been produced,
          % except for newline
stop = 0; % == "seen $stopping$ in $v$ yet?"
% inv: maintain definitions above; remaining work to be done is for v(i:end)
while ~stop & i <= length(v) % [3/14] fixed: $<=$ was wrongly $<$
    if v(i) == stopping
        stop = 1;
    else
        % print gaps and, if needed, label for $v(i)$
        % inv: still need to print labels for $prev+1:v(i)$
        while prev ~= v(i)
            prev = prev + 1;
            fprintf('\n%3d ', prev);
        end
        fprintf('*'); % print $'*'$ for $v(i)$
        i = i+1;
    end
end
fprintf('\n')

% b) vectors allowed; assume no "gaps".  fill in code for each comment.

    v = [v 1000] ; % concatenate 1000 to the end of $v$
    while v(1) ~= 1000 % loop until done
         k = v(1); % number to print stars for
         n = sum(v == k); % # of stars to print
         fprintf('%3d %s\n', k, char(zeros(1,n)+'*')); % print $k$ and $n$ stars
         v(v == k) = []; % delete all occurrences of $k$ from $v$
     end
    
% ======================================================================

% 6. Suppose $sum(x) == 0$ is used to test whether all elements of
%    vector $x$ are 0.  Explain all the reasons that this doesn't work; 
%    give concrete examples to illustrate your points.

% Answer:

% It can answer "true" when it shouldn't, namely when $x$ has a
% combination of positive and negative values that happen to cancel,
% e.g. $x = [3 -1 0 -2]$.