We use java and Eclipse IDE;

Step 2:

Improve the algorithms such that:

1)The Primes will generate a list of 1,000,000 (yes one million) prime numbers in under 2.5s of elapsed execution time. You will need to uncomment the last test case.

2)The Perfect Power completes all test cases in under .01s of elapsed execution time.

3)The pair-wise election completes all test cases in under .01s of elapsed execution time.

PairwiseVote,java:

package edu.www.cosc310.util;

import java.io.FileInputStream;

import java.io.FileNotFoundException;

import java.util.Scanner;

/**

* @author

*

* Utility class to compute the pairwise winner of elections

*/

public class PairwiseVote {

/**

* Get the placement order of a candidate in a rank order list of candidates

*

* @param votersVotes

* an array of rank order candidates. First has the highest rank.

*/

public static int getPlacement(int candidate, int[] votersVotes) {

for (int placement = 0; placement < votersVotes.length; placement++) {

if (candidate == votersVotes[placement]) {

return placement;

}

}

return votersVotes.length + 1;

}

/**

* Get the candidate winner from a set of rank ordered ballots

*

* @param votes

* - a two dimensional array, first dimension is the voter, second

* dimension is the rank ordered ballot of candidates for the given

* voter

*/

public static int getPairwiseWinner(int[][] votes) {

int noVoters = votes.length;

if (noVoters == 0) {

return -1;

}

int noCandidates = votes[0].length;

if (noCandidates == 0) {

return -1;

}

// Compare every pair of candidates

for (int candidate1 = 0; candidate1 < noCandidates; candidate1++) { //get rid of nested for loop

int noTimesCandidate1Wins = 0;

for (int candidate2 = 0; candidate2 < noCandidates; candidate2++) {

// Consider a candidate compared with themselves to be a winner

if (candidate1 == candidate2) {

noTimesCandidate1Wins++;

continue;

}

// Determine count the ballots for each candidate

int candidate1votes = 0;

int candidate2votes = 0;

for (int voter = 0; voter < noVoters; voter++) {

int placement1 = getPlacement(candidate1, votes[voter]);

int placement2 = getPlacement(candidate2, votes[voter]);

if (placement1 < placement2) {

candidate1votes++;

;

} else {

candidate2votes++;

;

}

}

// determine if candidate1 is the winner if so increment the number of wins

if (candidate1votes > candidate2votes) {

noTimesCandidate1Wins++;

}

}

// Determine if candidate 1 wins all

if (noTimesCandidate1Wins == noCandidates) {

return candidate1;

}

}

// No winner

return -1;

}

static int electionNo = 0;

/**

* Main - reads several test elections using the text file votes.txt. Each

* election begins with two number, the number of voters and the number of

* candidates, all followed by the ballots of each voter.

*/

public static void main(String[] args) throws FileNotFoundException {

int noVoters;

int noCandidates;

Scanner in = new Scanner(new FileInputStream("votes.txt"));

// read ballots for each election

for (;;) {

noVoters = in.nextInt();

noCandidates = in.nextInt();

if (noVoters == 0 && noCandidates == 0) {

break;

}

final int[][] votes = new int[noVoters][noCandidates];

// Read the ballots

for (int i = 0; i < noVoters; i++) {

for (int j = 0; j < noCandidates; j++) {

votes[i][j] = in.nextInt();

}

}

new TimeExec(new Runnable() {

public void run() {

int winner = getPairwiseWinner(votes);

if (winner >= 0) {

System.out.printf("Winner of election %d is candidate %d ", electionNo, winner);

} else {

System.out.printf("No winner for election %d ", electionNo);

}

}

}, "Election " + ++electionNo, System.out).start();

}

}

}

PerfectPower.java:

package edu.www.cosc310.util;

/**

* @author

*

* A utlity class to calculate the perfect power of an integer

*/

public class PerfectPower {

public static void main(String[] args) {

new TimeExec(new Runnable() {

public void run() {

System.out.println("Pth of 17 is " + PerfectPower(17));

}

}, "Get Pth of 17", System.out).start();

new TimeExec(new Runnable() {

public void run() {

System.out.println("Pth of 625 is " + PerfectPower(625));

}

}, "Get Pth of 625", System.out).start();

new TimeExec(new Runnable() {

public void run() {

System.out.println("Pth of 1024 is " + PerfectPower(1024));

}

}, "Get Pth of 1024", System.out).start();

new TimeExec(new Runnable() {

public void run() {

System.out.println("Pth of 10000 is " + PerfectPower(10000));

}

}, "Get Pth of 10000", System.out).start();

new TimeExec(new Runnable() {

public void run() {

System.out.println("Pth of 1073741824 is " + PerfectPower(1073741824));

}

}, "Get Pth of 1073741824", System.out).start();

}

/**

* Get the perfect power for a number.

* @param x number for which to calculate the perfect power.

*/

public static int PerfectPower(int x) {

int largestP = 1;

for (int p = 1; p < x; p++) {

for (int b = 1; b < x; b++) {

if (Math.pow(b,p) == x) {

largestP = p;

}

}

}

return largestP;

}

}

Primes.java:

package edu.www.cosc310.util;

/**

* @author

*

* Utility class to create an array of primes

*/

public class Primes {

/**

* Get a set of prime numbers.

*

* @param no

* the number of primes to create

* @return an array containing the requested number of primes

*/

public static int[] getPrimes(int no) {

int[] primes = new int[no];

int primeInx = 0;

int i = 2;

while (primeInx < no) {

boolean prime = true;

for (int j = 2; j < i; j++) { //prime

if (i == i / j * j) {

prime = false;

}

}

if (prime) {

primes[primeInx++] = i;

}

i++;

}

return primes;

}

public static void main(String[] args) {

new TimeExec(new Runnable() {

public void run() {

int[] primes = getPrimes(1000);

System.out.printf("Primes %d, %d, %d, %d, %d .... %d, %d, %d, %d, %d%n", primes[0], primes[1],

primes[2], primes[3], primes[4], primes[995], primes[996], primes[997], primes[998],

primes[999]);

}

}, "Get 1,000 primes", System.out).start();

new TimeExec(new Runnable() {

public void run() {

int[] primes = getPrimes(10000);

System.out.printf("Primes %d, %d, %d, %d, %d .... %d, %d, %d, %d, %d%n", primes[0], primes[1],

primes[2], primes[3], primes[4], primes[9995], primes[9996], primes[9997], primes[9998],

primes[9999]);

}

}, "Get 10,000 primes", System.out).start();

new TimeExec(new Runnable() {

public void run() {

int[] primes = getPrimes(100000);

System.out.printf("Primes %d, %d, %d, %d, %d .... %d, %d, %d, %d, %d%n", primes[0], primes[1],

primes[2], primes[3], primes[4], primes[99995], primes[99996], primes[99997], primes[99998],

primes[99999]);

}

}, "Get 100,000 primes", System.out).start();

new TimeExec(new Runnable() {

public void run() {

int[] primes = getPrimes(1000000);

System.out.printf("Primes %d, %d, %d, %d, %d .... %d, %d, %d, %d, %d%n", primes[0], primes[1],

primes[2], primes[3], primes[4], primes[999995], primes[999996], primes[999997], primes[999998],

primes[999999]);

}

}, "Get 1,000,000 primes", System.out).start();

}

}

TimeExec.java:

package edu.www.cosc310.util;

import java.io.OutputStream;

import java.io.PrintStream;

/**

* @author

*

* A utility class used to time the execution of a Runnable

*/

public class TimeExec {

private Runnable runnable;

private String message;

private OutputStream log;

/**

* Contructor that creates a TimeExec

* @param runnable the runnable to execute

* @param message the message to be displayed when the run completes

* @param log the stream to which the message is logged

*/

public TimeExec(Runnable runnable, String message, OutputStream log) {

this.runnable = runnable;

this.message = message;

this.log = log;

}

/**

* Start the TimeExec. This will execute the runnable and log

* the execution time (in secs) to the log.

*/

public void start() {

PrintStream out = new PrintStream(log);

long startTime = System.currentTimeMillis();

runnable.run();

long stopTime = System.currentTimeMillis();

out.println("TimeExec: " + message + ": " + ((stopTime - startTime) / 1000.0) + "s");

}

}

TimeExec shouldn't need changed it's just included so you can run the program. Also, i don't suggest running the programs "as is" because they take at least 8 hours to execute.