Assignment 5

Due on Wednesday 2nd April

You should submit solutions to this h/w via the cms system by 11pm on Wednesday.

Question 1: rotational decryption and interpretation - this question only due in class on Tuesday 1st April

The opening several paragraphs taken from a classic example of British literature has been encrypted via an extremely simple substitution cypher. None of the punctuation or spaces have been encrypted, hyphens which occured at the ends of lines have been removed (but otherwise not encrypted), uppercase letters have remained uppercase (ditto lowercase), and paragraph separation has been maintained. The encrypted text is in this file. You should simply give a brief summary of the meaning of the decrypted text.

Question 2: Induction.

  1. Prove by induction that the following formula for summing the squares of integers between m and n inclusive (for m <=n) is valid.
    m2 + (m+1)2 + . . . + n2 = (1/6) (n(n+1)(2n+1) - m(m-1)(2m-1)).

  2. Suppose that p/q is a fraction in lowest terms such that 1/(n+1) < p/q < 1/n for some positive integer n. Show that (p/q) - (1/(n+1)) is a fraction which in its lowest terms has numerator less than p. Hence by induction, prove that every proper fraction p/q with p < q can be written as a finite sum of distinct reciprocals of positive integers. For example, 19/15 = 1/2 + 1/3 + 1/4 + 1/6 + 1/60. Use this technique to express 5/7 as a sum of reciprocals.
    3. The example given here is correct, though it's not true that all fractions bigger than 1 can be expressed finitely in this way (eg 2) -- you've been asked to prove the statement only when the fraction is less than 1 (which is always true). If you want an example for this case, then 14/17 = 1/2 + 1/4 + 1/14 + 1/476.

Question 3: Sorting

by looking at the code in the notes or otherwise (but not simply snagging it off the web!), write a program to allow sorting of a singly linked list using list iterators which allows the user the option of choosing selection sort, insertion sort, mergesort or heapsort. Use your own list and list iterator classes (not just those from the Java api). You are welcome (if you like) to import the list into a general binary tree for mergesort and heapsort as long as you (again) use your own tree and tree iterator classes (not just those from the Java api).