Your cart is currently empty!
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…
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
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