Java代写：CS345 Algorithms

分析比较不同算法之间的性能。

About

GitHub Classroom contains the starter code for your programming exercises.

• Click on link and Sign-In to GitHub.
• You Should see the Instructions and Starter Code on GitHub.
• You must submit source code on GitHub for this assignment to be graded.
• You can discuss this with you classmates on Slack.
• Videos for exercise 3 should be in queue and should be expected to be released soon.

Exercise 01

About

The PerformanceTest program in the empirical package, contains three methods that implement the algorithms(solutions) for computing the range of numbers in an array.

For this exercise, we will look at algorithm performance by observing which of the three algorithm runs the fastest. We will compare each algorithm using data sets that increase in size. This performance is determined by running the algorithm and measuring how long it takes to complete each data set in milliseconds (ms).

Range

The range is the difference between the highest and lowest numbers in the array.

Algorithm 1 : Range$1

Description: This algorithm uses nested loops to examine every pair of elements in the array, computing their difference and remembering the largest difference found.

maxDiff = 0;
for (each index i)
  for (each index j)
    update maxDiff, if elements i and j differ more than max.

Algorithm 2 : Range$2

Description: This algorithm reduces the amount of computations performed by disregarding one of the (i, j) and (j, i) pairs, that give identical comparisons. It still uses nested loops to examine every pair of elements in the array but now only once, computes their difference and remembering the largest difference found.

maxDiff = 0;
for (each index i)
  for (each index j = i + 1)
    update maxDiff, if elements i and j differ more than max.

Algorithm 3 : Range$3

Description: This algorithm uses a loop to find the largest value and smallest value in the array, compute their difference and return this difference.

max = element[0]
min = max
for (each index i)
  find max.
  find min.
  return max - min

Analysis/Questions

Instructions: Answer the questions on in a document/spreadsheet and submit to your github repository.
Download and examine the L2_Range_RunTimes EXCEL file, which contains the location to populate the run time data of the three (3) algorithms listed above. There are three (3) different spreadsheets, one for each algorithm. Note the fourth (4th) spreadsheet combines the data for all three algorithms on one graph, however, algorithm 3 uses the secondary scale at top and right of graph.

1. Run the PerformanceTest program and input the out of the show run time for the data sets listed for each of the range algorithms in L2_Range_RunTimes EXCEL file.
2. If you are experiencing an OutOfMemoryError : Java heap space for your PerformanceTest program. This is possibly due to your Java Virtual Machine (JVM) needing more memory to run this application. A quick fix for this might be to do the following: Go to Run > Run Configurations > select PerformanceTest from left window > select (x) = Arguments
   • Type in the box below in the VM arguments window: -Xmx3200m.
   • This sets a 3.2GB allocation, which should be enough, but if you need more you can just replace 3200 with a larger number like 3800 etc…
3. What do observe for each of the algorithms shown with their corresponding data set? Can you tell which algorithm was the most efficient?
4. For algorithms 1 and 2, did reducing the amount of computations by half improve the runtime significantly? Explain your reasoning, if you felt it had a small or large change.
5. For algorithms 2 and 3, did reducing the number of loops improve the runtime significantly? Explain your reasoning, if you felt it had a small or large change.

Exercise 02

About

The Fibonacci sequence/series is a mathematical model that is often used in numeric optimization. It is based on a sequence of numbers in which the first two numbers in the series are 0 and 1, and each subsequent number is the sum of the previous two numbers.

n 0 1 2 3 4 5 6 7 8 9...

value: 0 1 1 2 3 5 8 13 21 34...

1. Update the recursive method fib to compute the Fibonacci value of n, in FibonacciTest of
   L2_AlgorithmsLab. This should be the Fibonacci sequence solution in its most basic form.
2. Modify the program FibonacciTest so that it finds the number of times the fib method is called. Use a static variable to keep track of the calls and increment it every time the method is called.
3. Create a performance test, similar to that shown for the ranges in Activity 1 for the method in Question 1 for fib(50). Plot 5-6 (five to six) data points in your L2_Range_RunTimes EXCEL file , what do you observe? Are the results as expected? How does this fit with the theoretical model of the series?
4. The code in Question 1 was inefficient, because it takes too many recursive calls. It ends up re- computing each Fibonacci number many times. This code runs very slow for even relatively small values of n. It can take minutes or hours to compute even the 40 th or 50 th Fibonacci number on certain computers. Write a new version of the Fibonacci method _fib that is still recursive but is more efficient than the one in Question 1. Do this by creating a helper method that accepts an additional parameter, the storage for the previous Fibonacci numbers, that you can carry through and modify during each recursive call.
5. Write a new version of the Fibonacci method fbn that uses iteration to generate the result for the nth value in the Fibonacci sequence.
6. Update the program FibonacciTest to run a similar empirical tests for the three Fibonacci sequence algorithms in this activity (Q1, Q4, Q5) and update your L2_Range_RunTimes EXCEL file to show the results.

Exercise 03

About

A fractal is a geometric figure that is recursively constructed i.e. it can be divided into parts, each of which is a reduced-size copy of the whole. In fact, when one observes a fractal shape, one observes that the shape contains smaller versions of itself, so that it looks similar at all magnifications.

In this activity, we will describe a recursive method for drawing various levels of a Sierpinski triangle. A Sierpinski triangle (named after a famous Polish mathematician), is a fractal that is composed of infinitely many sub-triangles. We cannot draw the actual fractal, because it is composed of infinitely many sub-triangles, but we can write a method that produces a number of levels that approximates the actual fractal.

Questions

Inspect and run the code in package filled and answer the following questions.

1. How do you obtain the midpoint between two points? State the mathematic formula.
2. What is the end case for the drawFigure method?
3. How many times is the drawFigure method invoked for a Sierpinski triangle of order 4, and 7?