# Project 3 Solution

\$30.00

Category:

## 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

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:

1. MergeQueues.java

1. IndirectSort.java

1. Triplicates.java

1. Ramanujan1.java

1. Ramanujan2.java

1. Country.java

1. report.txt

Spring 2015 3 of 3

error: Content is protected !!