Algorithms and OOD (CSC 207 2014F) : Assignments

Assignment 5: Numeric Computation

This assignment is currently in draft form!

Due: 10:30 p.m., Tuesday, 23 September 2014

Summary: In this assignment, you will continue to explore general issues in problem solving, while starting to consider some ways in which objects and OOD can help you design programs.

Purposes: To help you think about types in Java. To give you experience reading the Java API. To improve your skills at numeric and string processing in Java. To consider the MVC pattern.

Collaboration: You must do this assignment in groups of three or four students. You may form a group yourself or you may ask me to randomly assign you to a group. If you form your group yourself, you may not choose partners who you worked with on the previous two assignments. You may discuss this assignment with anyone, provided you credit such discussions when you submit the assignment.

Wrapper (Prologue): Individually read through this assignment and make sure that you understand what is required. Then use the form available at to indicate (a) how long you think this assignment will take and (b) what you think will be the most challenging aspect of this assignment.

Wrapper (Epilogue): When you are done with the assignment, fill out the form available at to indicate (a) how long the assignment took, (b) what the most challenging part of the assignment was, and (c) something important you learned from doing the assignment. If you find that the assignment took much less or much more time than you expected, also include (d) a note as to what might have led to that difference.

Submitting: Please put all of your work in a GitHub repository named csc207-hw5. Email the address of that repository to Please use a subject of “CSC207 2014F Assignment 5 (Your Name)”.

Warning: So that this assignment is a learning experience for everyone, we may spend class time publicly critiquing your work.



a. Create a new Eclipse project for this assignment. You can name the project whatever you like, provided it's not in bad taste.

b. Create a new package in the project. You may choose the name (again, provided it's in good taste). I would suggest edu.grinnell.csc207.groupname.utils.

c. Create a new class, Utils.


Part A: Finding Square Roots

As you may have noted, Math.sqrt only accepts values of type double. What happens if we want to compute the square root of a BigDecimal? One possibility is that we could convert the BigDecimal to a double, compute the square root, and then convert back. Unfortunately, that technique essentially eliminates the benefit of BigDecimal values - that they can be more accurate than double values.

The alternative is to write our own procedure. Fortunately, there is a well-known algorithm for computing square roots, the Newton-Raphson method. The algorithm starts with some approximation of the square root and repeatedly improves that approximation until the approximation is “good enough” (less than some specified amount, which we typically call “epsilon”).

Suppose we are computing the square root of a number n, and our current approximation is a. How do we improve a? We take the average of a and n/a. Note that this is a very sensible way to improve approximations because (a) if the approximation is already correct, a and n/a will be the same, so the approximation will remain correct; (b) if a is too small, n/a will be too large, so the average will be closer to the root; (c) similarly, if a is too large, n/a will be too small.

What approximation should we start with? 1.0 or even n while a bit absurd, will work acceptably well.

Write and test Utils.sqrt(BigDecimal d, BigDecimal epsilon). (You need not supply your tests.)

Warning: Unfortunately, division with BigDecimal values is less straightforward than it should be. You may need to take some time to read over (and understand) the different forms of division.

Note: There are at least two ways you can decide whether a value, a, is a reasonable estimate for the square root of n. You can compare the square of a to n. You can also compare a to n/a.

Part B: Exponentiation

Many students write functions to compute xn using loops, which means that they do approximately n multiplications. As algorithm designers, we should ask whether we can solve the problem more efficiently.

The lab on debugging contains a significantly more efficient algorithm for doing exponentation. However, that algorithm is recursive and some companies have policies that strongly discourage the use of recursion. Recursion also adds a bit of additional overhead (unless you use tail recursion and have a competent compiler).

Rewrite the algorithm iteratively.

Are you done? You can be. However, you may earn a bit of extra credit if you can identify an even more efficient way to do exponentiation. (To be more efficient, the number of steps in your algorithms will likely need to be independent of both the value and the exponent. That means you can't use loops or recursion.)

Part C: A Stateful Calculator for Fractions

In a previous assignment, you implemented a simple calculator by writing a method that takes a string as input, parses the string, evaluates the parsed string, and returns the computed value.

While that calculator is useful, there are certainly many opportunities to improve its design. One natural extension is to include “storage elements” (variables, registers), so that you can name the result of a computation and use it in a future computation.

Implement a class, Calculator, that supports simple calculations using fractions and integers. Your calculator should support at least eight storage elements, labeled r0 ... r7.

In particular, you calculator class should support evaluate(String expression), where expression is either an expression over fractions, integers, and storage elements or an “assignment” of the form ri = expression.

Note that evaluate should throw an appropriate exception if the expression is malformed. (Ideally, you should find a way to indicate the location of the error in the expression.)

Since your calculator is stateful, it makes sense to write a template class. That way, we can create multiple independent calculators.

Here's an example of a sequence of calls to evaluate.

  Calculator calc = new Calculator();
  calc.evaluate("2 + 3");               // Output: 5
  calc.evaluate("2 + 3 * 4");           // Output: 20 (or 14)
  calc.evaluate("r0 = 2 + 3");          // Output: 5
  calc.evaluate("r0 + 2");              // Output: 7
  calc.evalaute("r0");                  // Output: 5
  calc.evaluate("r1 = r0 * r0");        // Output: 25
  calc.evaluate("r1 + r0 * 2");         // Output 60 (or 35)

Part D: A User Interface

Create a user interface for the calculator. Your interface will primarily use the read-eval-print loop (aka REPL): read an expression, evaluate that expression, print the result, and do it all over again. You should find a nice way to report errors that the program encounters (e.g., division by 0).

Good designers separate program logic from the underlying computation. Please try to design your program so that it's easy to “swap out” one interface and to “swap in” another one. For example, you might think about what methods should be in the Calculator class so that we could use it with a graphical user interface instead of a textual user interface.

Here's a sample session with one UI.

> 2 + 3
> r0
r0 is currently undefined
> r0 = 2 + 3
> r1 = r0 * r0


The square root problem is taken almost verbatim from one I wrote for the old CSC 152 class. It is available at I've added some notes on deciding when an approximation is close enough.

The exponentiation problem has been part of my arsenal for years, although the particular phrasing is new to this assignment.

The calculator problems are based closely on a similar assignment I wrote for my Spring 2014 section of CSC 207. It is available at The problem is based on similar problems given in previous years I've added some sample calls and some sample output.