Project 3 Solution

$30.00

Category: Tag:

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