Project 2 Solution

Description

Section Readings: 1.2, 1.3, 1.4, 1.5

Problem 1. (Static Set of Comparables) Complete the implementation of StaticSET, which is a generalization of StaticSETofInts in that it is an abstraction for a static set of Comparable objects and not just ints.

• java StaticSET strW.txt < strT.txt

CTCCAATTCTGGCGTG CGTCATTCAGGTTGGA TAGGCTACCCACAAGC GAAATACCCCTAAGAA ACTTCGTAGGTTAGCA

Problem 2. (Josephus Problem) In the Josephus problem from antiquity, N people are in dire straits and agree to the following strategy to reduce the population. They arrange themselves in a circle (at positions numbered from 0 to N 1) and proceed around the circle, eliminating every Mth person until only one person is left. Legend has it that Josephus gured out where to sit to avoid being eliminated. Write a Queue client Josephus that takes N and M from the command line and prints out the order in which people are eliminated (and thus would show Josephus where to sit in the circle).

• java Josephus 7 2

1350426

• java Josephus 20 3

258111417049131831016615711219

Problem 3. (Text Editor Bu er) Develop a data type Buffer for a bu er in a text editor that implements the following API:

public class Buffer

• Create an empty buffer. Buffer()

• Insert c at the cursor position. void insert(char c)

• Delete and return the character at the cursor. char delete()

• Move the cursor k positions to the left.

void left(int k)

// Move the cursor k positions to the right.

CS210 Project 2 Swami Iyer

void right(int k)

• Return the number of characters in the buffer. int size()

• Return a string representation of the buffer with a “|”

• character (not part of the buffer) at the cursor position. String toString()

Hint: Use two stacks left and right to store the characters to the left and right of the cursor, with the characters on top of the stacks being the ones immediately to its left and right.

$ java Buffer

|There is grandeur in this view of life, with its several powers, having been originally breathed by the Creator into a few forms or into one; and that, whilst this planet has gone cycling on according to the fixed law of gravity, from so simple a beginning endless forms most beautiful and most wonderful have been, and are being, evolved. — Charles Darwin, The Origin of Species

Problem 4. (Closest Pair in 1D) Implement the static method closest() in ClosestPair that, given an array a[] of double values, returns a closest pair (two values whose dif-ference is no greater than the di erence of any other pair in absolute value), as an array of two elements. The running time of your program should be linearithmic in the worst case.

• java ClosestPair < numbers.txt [72.0, 73.0]

Problem 5. (Farthest Pair in 1D) Implement the static method farthest() in FarthestPair that, given an array a[] of double values, returns a farthest pair (two values whose dif-ference is no smaller than the di erence of any other pair in absolute value). The running time of your program should be linear in the worst case.

• java FarthestPair < numbers.txt [-289.0, 700.0]

Problem 6. (Random Connections) Complete the implementation of ErdosRenyi (an UF client) that takes integer values N and T from the command line, and prints the average (over T realizations of a random network of N sites) number of connections (pairs of integers between 0 and N 1) that need to be generated until all N sites are connected. Your job is to implement the static method count() that takes N as argument, generates random pairs of integers between 0 and N 1, calls connected() to determine if they are connected, and then union() if not (as in the development client for UF), looping until all sites are connected, and returns the number of connections generated.

CS210 Project 2 Swami Iyer

• java ErdosRenyi 10000 100 48621

Files to Submit:

1. StaticSET.java

2. Josephus.java

3. Buffer.java

4. ClosestPair.java

5. FarthesePair.java

6. ErdosRenyi.java

7. report.txt

Spring 2015 3 of 3