Data Structures and Algorithms, there are 3 files associated with the assignment, the text of the third is copied below the instruction. I will post the other two as separate questions.

The objectives of this assignment are to:

1. Gain an appreciation for the importance of algorithm analysis
2. Gain a feel of the different performance characteristics
3. Gain experience with improving the performance of algorithms

The zip file Asmt2.zip contains an eclipse project with solutions to three problems, one to generate an array of prime numbers, another to calculate the perfect power, and the last to perform a pair-wise election over a rank ordered set of ballots. All solutions have been set up with test cases in the main method (except that the Primes class currently has the last test case commented out). The test cases will time the execution of the case. All solutions have terrible performance problems as you will find out.

Step 1:

Run each solution and capture the output into text files. Name each output appropriately to identify the problem and indicate before time. Store each file in the project directory.

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.

Step 3:

Run each solution and capture the output into text files. Name each output appropriately to identify the problem and indicate after time. Store each file in the project directory.

File #3 Primes

/**

* 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++) { 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); } }, "Get 1,000 primes", System.out).start(); new TimeExec(new Runnable() { public void run() { int[] primes = getPrimes(10000); } }, "Get 10,000 primes", System.out).start(); new TimeExec(new Runnable() { public void run() { int[] primes = getPrimes(100000); } }, "Get 100,000 primes", System.out).start(); // new TimeExec(new Runnable() { // public void run() { // int[] primes = getPrimes(1000000); // } // }, "Get 1,000,000 primes", System.out).start(); } }