Due on Tuesday 23rd July (11pm-ish)

You are strongly encouraged to work in pairs. Plan and think out carefully before you start programming. The point of these questions is to get you using Python's modules and classes to build various useful things in a modular and reuseable way. You should start by building something pretty simple, focussing on getting the classes and methods talking to one another correctly, and only then start giving them any real functionality. Don't forget to include a README file!!!

Question 1:

Use proof by induction to prove the following statements:

The sum of the reciprocals of squares from 1 to n is less than or equal to 2 - (1/n).

There are n people in a room and each person want to shake hands once with each other person in the room. How many handshakes occur? Prove this by induction.

Letting x = the square root of n, prove that the sum of the reciprocals of positive square roots from 1 to n lies between x and (2x-1)

Prove that every third Fibonacci number is even.

Prove that each positive integer can be written as a sum of distinct Fibonacci numbers. (This question is a little harder.)

(If you like, you could try showing that the actual sum in the first exercise equals one sixth of the square of pi.)

Question 2:

Consider again a potentially large collection of towns, each of which can hold many people, just as in the previous homework. This time, however, since each person has a unique ID number and a name (possibly not unique), we want to be able to find people as quickly as possible by searching for their ID, or their name, or their town-rank. Each town maintains a queue of the people as they arrive in a town, so a person's town-rank is their position in that town's queue. Do note that having many duplicates of information is a recipe for disaster in attempting to keep all the copies in sync with each other, so having separate lists of people according to their different attributes would be a poor choice.

You should think carefully how you would access people quickly, and build a class to have a data structure which allows fast searching, perhaps via binary trees, bearing in mind that people will be leaving and joining various town queues. It may be that a later homework might have you grant priority treatment to some people, or even have you find efficient ways of having groups of friends meet up in a single town, so do think ahead as you build this structure.

For this question, you should not use lists, tuples, etc. from Python as the core storage components, nor use any Python sorting methods.