CS100J about the final

The final is Thursday, 8 April, 9AM to 11:30AM, in Barton EAST

You have to know everything that was coverd in the two prelims. The handouts on the two prelims tell you what that is. In addition, you have to know

1. Matlab, only as discussed below

2. Multi-dimensional arrays. For this, know what a type like int[][][] means and how you declare a variable of that type and create (only) its first dimension, e.g.

int[][][] c= new int[5][][];

Then, each element c[i] is has type int[][] and can be handled similarly.

You should be able to draw an element of an array int[][], showing how Java implements it. You should be able write simple program segments that process the elements of a two-dimensional array in row-major order.

This is what you have to know about MATLAB.

0. The notation a:b to denote the row of integers [a (a+1) (a+2) ... b]
The notation a:increment:b

1. The basics of creating arrays, using

(a) row vector notation: [ 10 20 30 ]
(b) column vector notation [10; 20; 30]
(c) rectangular array notation [10 20 30;40 50 60]
(d) stacking rows: if x is [10 20], then [x x] is [10 20 10 20]
(e) stacking columns. if u = [1 2]; v = [3 4] then [u;v;u] is

1 2
3 4
1 2

(f) for a row vector, size(x) gives the number of elements.
for an array, size(x) gives an array giving the number of elements in each row.
for this purpose, a column vector is really an 1-by-n array.

(g) transpose b' of an array or vector b

(h) functions zeros(n) and zeros(n,m)
functions ones(n) and ones(n,m)

(i) addition, subtraction, multiplication, division of an array by a scalar or a scalar by an array, e.g. [10 5 2] + 5.

(j) Elementwise operations on arrays:
addition b + c
subtraction b + c
multiplication b .* c
division b ./ c
exponentiation b .^ c

(k) functions max, min, sum, cumsum, prod, cumprod, median, abs, floor, ceil, sqrt

(l) Defining functions, e.g.

% = the mean and standard deviation of nonempty row vector x
function [mean,stdev] = stat(x)
n = length(x);
mean = sum(x)/n;
stdev = sqrt(sum(x-mean).^2)/n);

(m) if-statements, e.g.

d = sqrt(b^2 -4*a*c;
if d>0
   r1 = (-b+d)/(2*a);
   r2 = (-b-d)/(2*a);
else
   disp(`Complex roots')
end
if (x>y) & (x>z)
   maxval = x;
elseif y>z
   maxval = y;
else
   maxval = z;
end

(n) Be able to put together expressions that calculate a sum or cumulative sum of n terms of a series. For example, we wrote this function for the cumulative sum of n terms of Wallis's formula

2*2/(1*3) + 4*4/(3*5) + 6*6/(5*7) + ...

function answer= wallis(n)
evens= 2*(1..n)
odds= evens - 1
answer= 2*cumprod((evens .^2) ./ (odds .* (odds + 2))

Here are some infinite sums to practice on.

5 + 5 + 5 + 5 + ...

1 - 1 + 1 - 1 + 1 - 1 + ...

1/1 + 1/2 + 1/3 + 1/4 + ...

1/(1*1) + 1/(2*2) + 1/(3*3) + 1/(4*4) + ...

1/1 - 1/2 + 1/3 - 1/4 + 1/5 - 1/6 + ...

1*2/(2*3) + 2*3/(3*4) + 3*4/(4*5) + ...

1/(1*2*3) + 1/(3*4*5) + 1/(4*5*6) + ...

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

Questions on loops:

1. Given an integer matrix (which is a non ragged one) in Java (a[i][j]) with an even number of lines, write a loop that creates a new matrix b[i][j] with its lines being a's lines reflected over its horizontal symmetric axis.
precondition: a.length % 2 == 0
loop invariant: b[i,j] = a[a.length-1-i][j] for each i between 0 and k and j between 0 and m (m=a[0].length-1.)
post condition: b[i,j] = a[a.length-1-][,j] for each i between 0 and a.length-1 and j between 0 and m (m=a[0].length-1.) or
Different invariant:
b[i][j]=a[a.length-1-i][j] for each i between a.length-1 and 0 and j between 0 and m.

2. The Fibonnaci numbers F[0], F[1], ... are 0, 1, 1, 2, 3, 5, 8, 13, 21, ... Write a loop to calculate F[n] for some n. Use this invariant:

0 <= i <= n and b = F[i] and c = F[i-1].

For this purpose, assume that F[-1] is 1.

3. Do the same as 2, except use this invariant: 0 <= i <= n and b = F[i] and c = F[i+1]

4. Write a function with this heading:

// = "x is in array b"
public static boolean isIn(int[][] b, int x)

The invariant should be:

x is not in columns b[][0..c-1]

Write the repetend at a high level, stating what it should so and not writing an inner loop.

5. Same thing as question 4 but use the invariant: x is not in columns b[][c+1..]

6. Same thing as question 4 but use the invariant: x is not in columns b[]c..]

7. Your answer from question 4 contains a high-level statement in the repetend. Refine it. It will be a loop with initialization. Write the invariant of the loop first.

8. Write a loopto fill in a magic square of odd size. This is a square whose row, columns, and diagonals all lead up to the same thing. Suppose it is an n-by-n square b[][]. Here's how one proceeds. Put the number 1 in some square. Each time you have placed an integer in a square (i,j), do the following. Move to the square diagonally up and to the right, (i-1, j+1), and place the next integer there --if that square is already filled, then instead move down to the square (i+1,j) and put the integer there. Things wrap around, e.g. if i-1 is 0, use n-1 for the row number. We'll do this in class.

9. Write a program segment to zip the two arrays b[] and c[] into a third array d[]. b and c need not be the same size. d should contain b[0], c[0], b[1], c[1], b[2], c[2], ... When one array becomes empty and the other doesn't, just append the rest of the other one. This can be done in one loop, but three may make more sense.