General remarks first, applicable to future assignments too.

Please include your thoroughly documented/commented code and 
description of methods and results in a Jupyter notebook submitted via 
Quercus to TA Fergus H.

If we find any piece of plagiarized code inside your homework, all of us 
including you are guaranteed to be very unhappy, so please don't scavenge 
those dark corners of the net. 

Every important line needs to be commented to show that you correctly 
understand the algorithm (do not comment "z gets multiplied by y". Yes we can 
read that. We what to know why. For instance "   # time to pt. X".
You can comment using hash in that line or write a separate line starting 
with #, preceding the statement explained. State what the line does as 
concisely as you can; long comments sticking out to next line are ugly and may 
even cause indentation errors depending on the editor.

Some assignments, like the ones below, have analytical solutions. 
You are not required to find them, but if you do, then more power to you! 
We'd like to see it. No points, but the benefits of finding an alternative 
method to numerics are obvious. 




CHANGED DEADLINE: 1 OCTOBER 2019
   
Problem 1 - Speed up Leibniz series
_____________________________________

Series 

pi = 4[ 1 -1/3 +1/5 -1/7 +...] 

converges slowly. Quantify how fast: 
How many term do you need to achieve error less than 0.001? How many to achieve 
double precision accuracy (that's what we call numerical convergence in this 
context)?

The numbers you have obtained are large, which motivates us to speed up the 
convergence. [One way would be to find a better series for pi, but in research 
dealing with other, real problems, that may not be possible, so stay with your 
Leibniz series]. 

There are more sophisticated ways, but you will write a short code that 
simply sums up the original series and at the same time calculates & outputs 
the arithmetically averaged two adjacent intermediate estimates of pi, 
one "overestimated pi" and one "underestimated pi". 
Leibniz series terms have alternating signs, so the iteration 
constantly jumps over the true value of pi, and the amplitude of oscillations 
around the final point is slowly diminishing (do you agree?).
You can use the true value of pi=3.14159265358979... (also known as np.pi 
when importing numpy as np), to judge how far from true pi are your partial sums.
 
Looking at your results (print function works great!) please illustrate the 
convergence of your new series of averages. How many terms are needed, in your
opinion, to converge, i.e. achieve near-float precision pi (otherwise known as
double precision). Consult the book about precision of 8-byte floats. 

Be warned that many algorithms do not achieve results accurate to literally 
last digit, but simply stop converging very close, within a few machine epsilons, 
from the exact answers. 

Please plot the diminishing absolute values of residuals (deviations from true 
pi) on logarithmic axes or, equivalently, plot log10(abs(value)) on a linear 
axes. If you notice a linear trend in a LOG-LOG plot of |residual| vs. number 
of steps N, signifying power law decrease of |residual| with N, 
establish the slope of the dependence - that will be the power law index. 
Graphically or analytically estimate N needed for convergence. 
 
Looking at printouts of how the averaged series behaves, you may 
suspect that there is a way to further speed up the convergence of your new 
series of averages. Implement your idea and describe the results. 



Problem 2 - Refraction at the beach
_____________________________________

A life guard on the beech at position (x,y) = (0,-10) 
sees a swimmer in distress at position (x,y) = (30,10) in the water. The 
shoreline is a straight line y=0 (that is, x-axis). The guard first runs in a 
straight line at speed v1=3 on the land, then swims toward the swimmer at speed 
v2=1 in water. [Units of distance and speed are not important in this problem, 
only v1/v2 matters for the trajectory. Admittedly, in real life it's a bit 
different, speed of life guard IS fairly important for the swimmer. 

At what position does the life guard enter water, to minimize the total time 
of travel to the swimmer?

Solve that problem by iteration in Python, considering as dense a grid of
the sought entrance positions along the shore as necessary to achieve at least 
2 or 3 accurate digits. The range of considered positions of entry (X,0) is also
up to you, but you should not waste computer time by looking at places where the
solution is definitely not going to be found. 
  
On each considered trajectory, find the combined time on sand and in water, 
and minimize it in any way you like - storing and searching for the minimum 
of stored T(X) values, for instance. However, there is an advantage to programs
that do not store partial results unnecessarily. They might be smaller and 
faster. Since there is only one optimal path in this problem, you can step 
through the points on the shore, and break out of the Python loop when you 
detect that the result starts getting worse instead of better, i.e. that you 
have just passed the minimum. (As a final touch, you can assume that the best 
estimate of position is halfway between the last two points considered).

The method is really up to you. No need to plot the result, but if you feel 
like it, please illustrate your solution.

Is the Snell's law obeyed by your optimum trajectory? 

Explanation: for those of you who are not in Physics programs, this calculation 
is analogous to refraction of light rays on the surface of a denser medium 
in which the speed of wave decreases. In fact, the angles of the trajectory 
you find *should* obey the Snell's law of refraction (google it up if you 
haven't heard of it). The implied ratio of refractive indices (speed ratio) 
of the two media in our problem is equal 3. 

In optics of eyeglasses, the ratio for air-glass interface in 
eyeglasses is close to 1.5. Light changes direction so as to minimize time of 
flight (that's Fermat's Principle, see also Maupertuis's Principle). 
That's why the rays run at a shallower angle to air-glass boundary in 
air than in glass. You may expect the same effect in the current problem: 
inclination to shoreline will be smaller on land than in water, so that
slower swimming happens over a smaller distance than in a straight-line 
trajectory. One more thing: the bigger the refractive index of glass 
(or plastic), the thinner and lighter the lens in eyeglasses can 
be made, but that increases the cost of material and of the lens 
(unfortunately not in direct proportion, those two costs!).   




Problem 3 - Aim high
______________________

The pool table is a rectangle with size 4 ft by 8 ft. You are to hit the white 
cue ball (o) positioned at (1,1), that is 1 ft from the boundaries near the 
lower left corner, like so
______________
|             |
|             |
|             |
| o       b   |
|_____________|

so that it strikes the black ball (b), positioned at (6,1), indirectly. 
The direct path is blocked by balls (x) that you cannot touch:

|---------->X
____________.__
|         .  . |
|      .      .|
|   .    xx  . |
| o      x b x |
|_________xxx__|

Dots are trying to show the required path; the figure is schematic. 
The white cue ball elastically strikes the upper boundary first and then the 
right boundary, before heading straight toward (b). It bounces like a light 
ray from a mirror, preserving angles. 

Where should you aim: what is the position of the collision with upper border 
that accomplishes the trick?  Call it X, and count it from left border.

Settle the question by Python iteration, considering a mesh of points
on upper boundary of pool table & choosing the best one. You may repeat the 
calculation a few times with a gradually finer mesh, and see how much more 
precise your resulting location becomes.

The required accuracy is 3 accurate digits in X. We do appreciate your skills, 
but consider it unlikely that you can reproduce more digits while playing pool. 

Comment 1: The exercise is about iterations, not the bisection or other 
search method, so don't use it. Indeed, in real life it is sometimes safer to 
look at a large number of potential solutions than *assume* that a function has 
only one zero in an interval of its argument - which is the assumption that 
bisection makes. 

Comment 2: It's up to you how you define a number characterizing a miss: it
could for instance be the difference between the white and black ball's
x-positions, at time when (o) crosses the line passing through (1,1) and (6,1),
from top to bottom. Or the difference of y-positions. Or something having to do 
with angle of the second reflection if you draw a line through the second bounce
point on the right boundary and (b). In any case, it has to be a variable that 
assumes positive or negative values for near-misses, and has value zero when 
center of (o) passes through center of (b). In other words, you are looking for
a zero of your function, not a minimum. 

Explain your method. Include the commented code, some printouts from iteration,
and the final result with information on how you know that you have obtained 3 
accurate digits. 

Problem 4 - History question
_____________________________


Create a list and in a few brief sentences explain the main differences 
of two computers: K. Zuse's Z3 computer, and Digital PDP-11 computer, 
and the modern computers. Think, for instance, about the number representation,
technical implementation of storage and CPU, and so on.

(Lecture notes should suffice to answer this questions, but you are free to 
do you own research.)