logo Practice-It logo


Related Links:
Author: Robert Baxter

Suppose you have a class Calculator that performs calculations on integers:

Method/Constructor Description
public Calculator(int seed) constructs a Calculator with given seed for random numbers
public boolean isPrime(int n) returns true if n is prime
public int prime(int n) returns the nth prime (assumes n >= 1)
public int fib(int n) returns the nth Fibonacci number (assumes n >= 1)
public int rand(int max) returns a random value between 0 and max

The class correctly computes its results, but it does so inefficiently. In particular, it often computes the same value more than once. You are to implement a technique known as "memoizing" to speed up the computation of primes. The idea behind memoizing is to remember values that have been computed previously. For example, suppose that the value prime(30) is requested 100 times. There is no reason to compute it 100 different times. Instead you can compute it once and store its value, so that the 99 calls after the first simply return the "memoized" value (the remembered value).

Define a new class called MemoCalculator that can be used in place of a Calculator to speed up the prime computation. A MemoCalculator object should behave just like a Calculator object except that it should guarantee that the value of prime(n) is computed only once for any given value n. Your class should still rely on the Calculator class to compute each value for prime(n). It is simply guaranteeing that the computation is not performed more than once for any particular value of n. The isPrime method calls prime, so it does not need to be memoized. You do not need to memoize the Fibonacci computation. You should not make any assumptions about how large n might be or about the order in which the method is called with different values of n.

Your class should also provide the following public methods that will allow a client to find out how many values have been directly computed versus how many calls have been handled through memoization.

Method/Constructor Description
public MemoCalculator(int seed) constructs a MemoCalculator with given seed for random numbers
public int getComputeCount() returns number of values actually computed
public int getMemoCount() returns number of calls handled through memoization
Type your solution here:

This is an inheritance problem. Write a Java class using inheritance. (You do not need to write any import statements.)

You must log in before you can solve this problem.

Log In

If you do not understand how to solve a problem or why your solution doesn't work, please contact your TA or instructor.
If something seems wrong with the site (errors, slow performance, incorrect problems/tests, etc.), please

Is there a problem? Contact a site administrator.