Project 3 Solution

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 a3 + b3 = c3 + d3. 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 < 3 N. Then, while the priority queue is nonempty, remove the pair (i; j) such that










Spring 2015 1 of 3
CS210 Project 3 Swami Iyer










i3 + j3 is the smallest (this is easily done since we are using a minimum-oriented priority

3
















+ b3 = c3 + d3


N, and then if
queue), print the pairs (a; b) and (c; d) such that a3


j < p






N, insert the pair (i; j + 1) into the queue.
Write a program Ramanujan2 that
implements this idea.


























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










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






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






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






























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






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






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

































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:




public
class Country








private
String
code1 ;
//
UN code








private String
code2 ;
// 2 letter ISO a b b r e v i a t i o n
private String
code3 ;
// 3 letter ISO a b b r e v i a t i o n
private
String
name ;


//
name


private String capital ; // capital


//
Co ns tr uc t a
Country object given the fields (codes , name ,






//
and
capital ) as a line of comma - se pa ra te d values .
public
Country ( String s )






//
Return a string r e p r e s e n t a t i o n of the country .
public
String
toString ()


















//
Code1 c o m p a r a t o r .








public
static
class
Code1
i m p l e m e n t s
Comparator < Country
//
Code2 c o m p a r a t o r .








public
static
class
Code2
i m p l e m e n t s
Comparator < Country












//
Code3 c o m p a r a t o r .








public
static
class
Code3
i m p l e m e n t s
Comparator < Country
//
Name c o m p a r a t o r .








public
static
class
Name i m p l e m e n t s
Comparator < Country










//
Capital C o m p a r a t o r .






public
static
class
Capital i m p l e m e n t s Comparator < Country



















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 2 of 3
CS210


Project 3


Swami Iyer












$ head -5 c ou nt ri es . csv




004
, AF , AFG , Afghanistan , Kabul




008
, AL , ALB , Albania , Tirana




012
, DZ , DZA , Algeria , Algiers




020
, AD , AND , Andorra , Andorra la Vella




024
, AO , AGO , Angola , Luanda










$ java Country 10 capital - < c ou nt ri es . csv




040
AT
AUT
Austria
Vienna


008
AL
ALB
Albania
Tirana


028
AG ATG Antigua and Barbuda
St . John ’ s
024
AO
AGO
Angola
Luanda










004
AF AFG A f g h a n i s t a n
Kabul


036
AU AUS Au st ra li a
Canberra
032
AR ARG Ar ge nt in a
Buenos
Aires
031
AZ AZE A z e r b a i j a n
Baku


020
AD
AND
Andorra
Andorra
la Vella
012
DZ
DZA
Algeria
Algiers

















Files to Submit:




MergeQueues.java



IndirectSort.java



Triplicates.java



Ramanujan1.java



Ramanujan2.java



Country.java



report.txt
















































































Spring 2015 3 of 3