Due on Thursday 2nd April

You may work in pairs for this assignment. For those questions requiring programming, plan and think out carefully before you start programming.

Question 1

1. Prove by induction that the following formula for summing the squares of integers between m and n inclusive (for m <=n) is valid.
   m² + (m+1)² + . . . + n² = (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. Prove that (p/q) - (1/(n+1)) is a fraction which in its lowest terms has numerator less than p. Hence by induction or otherwise, 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. 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.


3. Suppose you are given the recursive definition

   c_n = 2 * c_n/2 + n
   c₁ = 0

   Estimate the numerical value of c_n. Treat the n/2 as integer division.

Question 2

Consider the following problem. You're working for a large company with millions of customers, and have been asked to maintain a queue of customers seeking assistance. However, some of your colleagues frequently want to be able to see who's currently in the queue, but either want to see quickly if a particular customer is there, or want a list of all queued customers sorted by name. Devise a data structure to handle this scenario efficiently, and write a program to show this in action. Your program should demonstrate its prowess by being able to read in data from a file (with your program allowing the naming of a file from which to read in data; the data would be in the format of strings separated by spaces and/or line breaks, each 'name' being just one string of letters without internal spaces). Explain how your program works, why you chose the data structure(s) you did, and make comparisons with other data structures or combinations of data structures which could have been employed. You should treat the customer data as if it were quite extensive for each customer (so have a customer object with attributes, some of which could be quite large) even if in reality much of your computation refers only to the name information or some other customer identifier. (For this question, please only use data structures that you actually build, eg don't use the Java API queues, lists, trees, arraylists, etc.)

Question 3

Write code for a linked list implementation of a self-adjusting list (in such a list, all insertions are performed at the front, plus there is a find operation so that when an element is accessed by a find it's moved to the front of the list without changing the relative order of the other items). What might be the benefits of such a list, and can you quantify your assertions? (You might try testing your code for speed of use compared with a regular linked list.)

Question 4

Using your own nodal implementation of trees and tree iterators (ie you may use material from class, etc, but not simply use the Java API tree and iterator classes), write recursive code to implement mergesort and heapsort for Comparable People (ie People who implement the Comparable interface).