CS100M Spring 2001                Prelim T1 Solutions                   Feb. 14

===============================================================================

Question 1: (14 points) Final Box Diagram Snapshot

Not required, but we show two intermediate snapshots in case you find them
helpful.

  +---+---+---+
x | 1 | 3 | 5 |                         x = 1:2:5;
  +---+---+---+

  +----+
y | [] |                                y = 5:2:1;
  +----+

  +-------------------+
  |     +---+---+---+ |
z | foo | 1 | 3 | 5 | |                 z.foo = x;
  |     +---+---+---+ |
  +-------------------+
_______________________________________________________________________________

  +---+---+---------+
x | 1 | 3 | -5- -18 |                     x(3) = -18;  (5 is crossed out)
  +---+---+---------+

  +----+
y | [] |
  +----+

  +-------------------------+
  |     +---+---+---+       |
z | foo | 1 | 3 | 5 |       |
  |     +---+---+---+       |
  +-------------------------+
  |     +---+---+-----+---+ |
  | bar | 1 | 3 | -18 | 8 | |           z.bar = [x 8];
  |     +---+---+-----+---+ |
  +-------------------------+

  +-------------------------------+
  |   +---+                       |
w | a | 7 |                       |     w = struct('a', 7, 'b', z);
  |   +---+                       |
  |                               |
  |   +-------------------------+ |
  | b |     +---+---+----+      | |
  |   | foo | 1 | 3 | 5  |      | |
  |   |     +---+---+----+      | |
  |   |                         | |
  |   |     +---+---+-----+---+ | |
  |   | bar | 1 | 3 | -18 | 8 | | |
  |   |     +---+---+-----+---+ | |
  |   +-------------------------+ |
  +-------------------------------+
_______________________________________________________________________________

  +---+---+--------+
x | 1 | 3 |-5- -18 |
  +---+---+--------+

  +----+
y | [] |
  +----+

  +-------------------------+
  |     +---+---+---+       |
z | foo | 1 | 3 | 5 |       |
  |     +---+---+---+       |
  +-------------------------+
  |     +---+---+-----+---+ |
  | bar | 1 | 3 | -18 | 8 | |
  |     +---+---+-----+---+ |
  +-------------------------+

  +------------------------------------+
  |   +---+                            |
w | a | 7 |                            |
  |   +---+                            |
  |                                    |
  |   +------------------------------+ |
  | b |     +---+---+---+ +---+---+  | |
  |   | foo +-1-+-3-+-5-+ | 3 | 1 |  | |        w.b.foo = [3 1];
  |   |     +---+---+---+ +---+---+  | |        ( [1 3 5] is crossed out)
  |   |                              | |
  |   |     +---+---+-----+---+      | |
  |   | bar | 1 | 3 | -18 | 8 |      | |
  |   |     +---+---+-----+---+      | |
  |   +------------------------------+ |
  +------------------------------------+

===============================================================================

Question 2: (30 points)

Capitalize the first letter in each word of $str$,
which contains only letters and spaces.

up = upper(str);                        | $upper$ leaves non-letters unchanged,
if str(1) ~= ' '                        | so it is safe to always apply
    str(1) = up(1);                     | $upper$ after a space:
end                                     |
for i = 2:length(str)                   | str(1) = upper(str(1));
    if str(i-1) == ' ' & str(i) ~= ' '  | for i = 2:length(str)
        str(i) = up(i);                 |     if str(i-1) == ' '
    end                                 |         str(i) = upper(str(i));
end                                     |     end
                                        | end
________________________________________|______________________________________

Unfortunately $|$ is not short-circuiting:
the code below has a subscript error when $i$ is 1.

    for i = 1:length(str)
        if (i == 1 | str(i-1) == ' ') & str(i) ~= ' '
            str(i) = upper(str(i));
        end
    end
_______________________________________________________________________________

This question can be solved using $findstr$, but in general, you
should ASK before using functions we haven't explicitly covered in the
class.

===============================================================================

                                   N
                                 -----     k  (2 k + 1)
                                  \    (-1)  2
Questions 3: (25 points) Compute   )   ----------------
                                  /       (2 k + 1)!
                                 -----
                                 k = 0

Using loops:

    total = 0;
    for k = 0:N
        total = total + (-1)^k * 2^(2*k+1) / factorial(2*k+1);
    end
    total

No loops:

    fact = cumprod(1:2*N+1);
    fact = fact(1:2:end);
    2 * sum ( (-1 * 2^2) .^ (0:N) ./ fact )
_______________________________________________________________________________

BONUS: Print the vector x = [0 0 2 2 4 4 6 6 \ldots~2N 2N]

Using loops:              |      Avoiding recomputation of 2i:
                          |
x = [];                   |      x = [];
for i = 0:N               |      for j = 2*(0:N)  % or:  0:2:2*N
    x = x = [x 2*i 2*i];  |          x = [x j j];
end                       |      end
x                         |      x
                          |
__________________________|__________________________________________
                          |
Avoiding loops:           |      Most efficient:
                          |
x = 0:2:2*N;              |      x = 0:2*N+1;
x = sort([x x])           |      x = x - rem(x,2)

===============================================================================

Question 4: (36 points)

Part (a):(25 points)

Roll 3 (bonus: $D$) fair dice $N$ times;
count frequencies $counts(j)$ of outcomes.

sides = 6;                          |   More concisely:
counts = zeros(1, D*sides);         |
for i = 1:N                         |   sides = 6;
    j = 0;                          |   counts = zeros(1, D*sides);
    for k = 1:D                     |   for i = 1:N
        j = j + ceil(rand*sides);   |       j = sum( ceil( rand(1,D)*sides ) );
    end                             |       counts(j) = 1+counts(j);
    counts(j) = 1+counts(j);        |   end
end                                 |
____________________________________|__________________________________________

You can also use $1+floor(rand*sides)$, but using $round$ is wrong: it does
not produce equally likely rolls.  It is also wrong to simply generate
uniformly random numbers D..D*sides.  For example, if D=2, outcome
7=1+6=2+5+3+4=4+3=5+2=6+1 is much more likely than 2=1+1.
_______________________________________________________________________________

Part (b): (11 points)

Use only variable $counts$ from part~(a) to compute the mean outcome.
Straight from lecture:

    sum( counts .* (1 : length(counts)) ) / sum(counts)

Strange version using $cumsum$ (thought question: why does it work?)

    sum(cumsum(fliplr(counts))) / sum(counts)