Solved–Project 3– Solution

Description

Section Readings: 2.1, 2.1, 2.3, 2.4, 2.5

Problem 1. (Merge Sorted Queues) Implement the static method merge() in MergeQueues that takes two queues of sorted items as arguments and returns a queue that results from merging the queues into sorted order. Your implementation must be linear and must not alter the input queues.

$ java M e r g e Q u e u e s

ABCDEFGHIJKLMNOPQRSTUVWXYZ

Problem 2. (Indirect Sort) Implement the static method sort() in IndirectSort that indirectly sorts a[] using insertion sort, ie, not by rearranging a[], but by returning an array perm[] such that perm[i] is the index of the ith smallest entry in a[].

$ java I n d i r e c t S o r t

INSERTIONSORTEXAMPLE AEEEIILMNNOOPRRSSTTX

Problem 3. (Triplicates) Implement the static method commonItem() in Triplicates that takes three arrays with N names each and returns the rst name common to all three arrays, or null. Your implementation must be linearithmic.

• java T r i p l i c a t e s Hoare

Problem 4. (Ramanujan’s Taxi) Srinivasa Ramanujan was an Indian mathematician who became famous for his intuition for numbers. When the English mathematician G. H. Hardy came to visit him one day, Hardy remarked that the number of his taxi was 1729, a rather dull number. To which Ramanujan replied, \No, Hardy! It is a very interesting number. It is the smallest number expressible as the sum of two cubes in two di erent ways.” Verify this claim by writing a program Ramanujan1 that takes a command-line argument N and prints out all integers less than or equal to N that can be expressed as the sum of two cubes in two di erent ways. In other words, nd distinct positive integers a, b, c, and d such that a³ + b³ = c³ + d³. Hint: Use four nested for loops. You have to be clever about your choice of the bounds for the loop variables, so your program runs quickly by only considering distinct values for a; b; c, and d.

$ java R a m a n u j a n 1 40000

1729 = 1^3 + 12^3 = 9^3 + 10^3

4104 = 2^3 + 16^3 = 9^3 + 15^3

13832 = 2^3 + 24^3 = 18^3 + 20^3

39312 = 2^3 + 34^3 = 15^3 + 33^3

32832 = 4^3 + 32^3 = 18^3 + 30^3

20683 = 10^3 + 27^3 = 19^3 + 24^3

A much more sophisticated implementation of the same program is using a minimum-or maximum-oriented priority queue | we’ll use the latter. Here’s the idea. Initialize

• minimum-oriented priority queue with pairs (1; 2); (2; 3); (3; 4); : : : ; (i; i + 1) such that p

i < ³ N. Then, while the priority queue is nonempty, remove the pair (i; j) such that

CS210 Project 3 Swami Iyer

i³ + j³ is the smallest (this is easily done since we are using a minimum-oriented priority

Problem 5. (Countries) Implement a data type called Country that stores information about a country, such as its codes, name, and capital, and implements comparators by each of those elds. Here’s the API for the data type:

Implement a test client main() in Country that reads command-line arguments n, orderBy, and order; reads line-oriented information about n countries from standard in-put; and prints them in sorted (by orderBy eld, which can be “code1”, “code2”, “code3”, “name”, or “capital”) order (ascending if order = “+” and descending if order = “-“).

Spring 2015 3 of 3