CS 5010: Problem Set 12

Out: Monday, 10 April 2017
Due: Monday, 17 April 2017 at 6pm

This is an individual assignment. You are not allowed to discuss this problem set with any other person. You are also not allowed to search for or to view any solutions to similar problems that may be available on the World-Wide Web or in other resources that might otherwise have been available to you.

Use the repository we created for you at the beginning of the semester.

At the end of every work session, you are required to update your log file to record the time you spent in that work session. (Please do not include the time you spent in any previous work sessions, as those times will already have been recorded in previous versions of your log file.)


In this problem set, you will run several benchmarks and report your findings. You will run the benchmarks on a machine that has the following software installed:

gcc, Java 8, and Larceny can be downloaded from the web sites linked above. If you are unable to install one or more of those systems on a machine you own or control, you can use one of the CCIS Linux machines in WVH 102. If you use one of the CCIS Linux machines, you will probably want to add /course/cs5010sp17/bin to your path so you can run larceny more easily.

Please do not run benchmarks on login.ccs.neu.edu. Many other students are using that server. They and the CCIS system staff will be annoyed if you run cpu-intensive benchmarks on that shared server. Because so many other students are using that server, any timings you obtain on that server would be unreliable anyway.

In the first part of this problem set, you will run benchmarks that rely on non-tail recursion (fib) or tail recursion (sumsq), and you will translate one of those benchmarks into an equivalent Java program that uses idiomatic loops instead of tail recursion.

In the second part of this problem set, you will run two benchmarks that were designed to measure the speed of storage allocation and deallocation.

Your deliverables include the Sumsq2.java file you will complete in part 1, and a report.txt file that records the timings you measure in both parts. You will also write your answer to a popular question about explicit deallocation versus garbage collection.


Problem Specification

We are giving you a set12 directory that contains several benchmarks, a tail-recursive Sumsq2.java program you will modify, and a report.txt file you will modify. Unpack that directory and push it to your GitHub repository. Add the interpreter your team wrote in Problem Sets 10 and 11 to that directory and push it again to your repository.

You will then be ready to work on the following questions.

  1. Modify Sumsq2.java as necessary to make it use loop syntax instead of tail recursion, but do not modify it any more than necessary. (In particular, do not use any mathematical formulas that would change its asymptotic running time.) Then run the benchmarks indicated for question 1 in the report.txt file, and add the results you observe to that file.
  2. Run the benchmarks indicated for question 2 in the report.txt file, and add the results you observe to that file. Then answer the question asked at the end of that file.

After you have modified Sumsq2.java and completed report.txt, push your files to your repository.

For debugging: Click here to validate.