Lab3.doc

Reviving the practice of using elements of popular music in classical composition
, an approach that had been in hibernation in the United States during the 1960's,
composer Philip Glass (born 1937) .... The author's BLANK style renders a
fascinating subject, the role played by luck in everyday life, extraordinarily
BLANK.

Part of the document


Laboratory 3 - Program Correctness and Efficiency

Introduction

Assuring program correctness is one of the major problems of Software
Engineering. Chapter 2 discusses several approaches to this including
program testing and proving program correctness. While we are not able to
mathematically demonstrate correctness of production programs, we are able
to demonstrate correctness of isolated algorithms which do not interact
with parallel phenomenae such as input/output operations. Despite our
inability to mathematically prove program correctness, researchers in this
area have created a number of very useful techniques, tools, and ways of
looking at program fragments which help us develop reliable softare.
Essentially, we use the formalism developed by the correctness proof
movement to specify correct operation of our software components and
systems.
Please understand that this kind of analysis requires that our algorithms
terminate and typically yield a result. Not all useful software components
meet these requirements. and we have already encountered an example of
this in the Life Game project. However, many of the components in the Life
Game project, such as the neighbors method, are are still algorithms
which do terminate and yield a result.
One of these techniques is formally specifiying what are known as
preconditions and post conditions for discrete algorithms. The
preconditions govern the system state required for the alogirthm to run
correctly and describes what parameters or other resources are made
available to the algorithm. The postconditions describe in what ways the
algorithm is allowed to modify system status, and will always describe
allowed side-effects and return values.
We then use these formal specifications to design our test procedures.
There are several important approaches to software testing. Black-Box
testing and White Box testing are both inheritted from general engineering
practice. White-Box tests are designed based on knowledge of the internal
design and function of what is being tested. Black-Box tests are designed
based strictly upon external descriptions of functionality and performance
without any knowledge of internal construction. Generally speaking,
systems undergo both types of testing before they are publicly released.
Public Beta's are one well known example of Black-Box testing.
Software Quality Assurance Engineers have also devised tools and techniques
which may be unique to Software Engineering. One of these is introducing a
known number of random errors into a program. The modified system is then
sent to testing. The test-team then attempts to detect and isolate
errors. The percentage of artificial errors detected and isolated is then
used to estimate the number of actual design errors which have not yet been
detect. This laboratory exercies is restricted to White-Box testing.

Getting Started

Create a new directory for the files of this exercise, and in it, save
copies of the files Trig.java.

Software Testing

Complete writing the Trig class of static trigonometric functions that
computes the sine, cosine, and tangent functions in a specialized
manner. This class is going to be part of an embedded system running on a
processor that does not support floating-point arithmetic or the Java Math
class. This class computes the sine, cosine, and tangent of an angle
expressed in degrees. The result will be an integer representing the sine
or cosine as ten-thousandths. For example, a result of 7071 represents
7071e-4 or 0.7071. The class to be tested is included in Trig.java. Since
this is an embedded applicaiton, the sine values for a single quadrant are
stored as static data inside the method. In a genuine embedded
application, these values would either be stored in a special table in ROM
(Read Only Memory) or approximated in real-time by a polynomial. You will
simulate a ROM-based table by reading the values from a file into an array
when the program starts. For this assignment you will:
. Compute the table of precomputed sine values for angles between 0 and
90 degrees.
. Complete and test the static methods sin, cos, and tan.
. Design and implement a white-box test program for your Trig class.
. Design a set of test data that will exercise each of the if
statements. To do this, look at the boundary conditions and pick
values that are:
o Exactly at the boundary.
o Close to the boundary.
o Between boundaries.
And, compare the values produced by your Trig function to those
produced by the StrictMath Java package.

Completing the Software Testing Problem

The goal for this assignment is to construct a functional Trig class with
static methods sin, cos, and tan along with a test program called Tester
which demonstrates the correctness of the three trigonometric methods.
Recall that tan(?) = sin(?) / cos(?) and that Tan(90) and Tan(270) can
result in a DivideByZeroException. However, throwing this exception might
make our methods more difficult to use and the value Double.NaN (not a
number) is not available, so we will define and throw our own
NoSuchNumberException. You will need to throw this exception not only when
you attempt to divide by zero, also when your division operation would
generate a numeric overflow. An overflow will occur when the result of
your division would exceed the maximum magnitude for your integer values.
Your test method and procedures need to test for properly throwing this
exception. You also need to normalize your divisions as your sine and
cosine methods will be returning integers in the range [-10000 , +10000]
instead of [-1 , +1]. Similarly, your tangent operation will need to
return values such that 1 is represented by 10000.

Efficiency and Optimization


When to Optimize

|"Premature optimization is the root of all |
|evil." -Donald Knuth. |


You should consider optimizing your program only after you have a working
version and only if that version is too slow. Do not optimize as you go.
If your program does not operate correctly, it does not matter how fast it
runs. Do not mistake optimization for debugging; in fact, optimized
programs are usually harder to understand and to debug because they break
abstraction barriers in the name of efficiency. If you do decide to
optimize, it is helpful to comment optimizations in your code and to keep
the original, unoptimized version in source control somewhere. However,
over time you will find yourself writing more efficient code initially.
Often beginners include much unnecessary complexity in their programs.
Generally, cleaner code will be both more reliable and more efficient than
messy code.
Finally, you should always run tests before and after you optimize. Run
your normal test suite (for correctness) to make sure you didn't introduce
any new bugs. Don't become too attached to an algorithm or assume that a
program will always run faster with fewer lines of code. Run performance
tests (described in this lab) to objectively measure if your optimizations
actually resulted in a net speed or size improvement.

Object Creation and Reuse

Creating an object in Java is an expensive operation, roughly equivalent
to a malloc operation in C, or a new operation in C++, and takes anywhere
from a couple hundred to a couple thousand VM ticks to complete, depending
on the size of the object. Although modern VMs have very effective garbage
collection algorithms, even small objects can remain on the heap long
after their last use. Creating a large number of objects not only wastes
memory but reduces the effectiveness of your computer's cache in speeding
up memory accesses.
However, if your program currently works and you want to optimize it, you
should consider moving code which creates objects outside of loops, as
well as replacing small objects with calls to primitive data types.
One way of avoiding the penalty of object creation and garbage collection
is to reuse objects instead of creating new ones. This usually involves
making immutable objects mutable. For example, in the body of a loop it
might be convenient to create an object, use it, and then discard it.
This strategy is really wasteful. A better approach is to add methods to
the object's class which allow you to reset the object's internal
representation. Hence, you create one object which is then modified at
the beginning of each iteration of the loop. However, mutable objects are
susceptible to more bugs than immutable objects. How do you know an object
is in a valid state? What if your program modifies a mutable object in one
method while you are still using it in another? This is a classic tradeoff
between efficiency and maintainability.

Code Profiling

Profiling is the collection of timing and memory usage information from an
executing program. There are several ways to profile programs written in
Java, including the Sun VM's built-in profiler and other, more
sophisticated tools, both free and commercial. However, the quickest and
easiest way to profile your Java program is to manually insert the
following system calls into your code where they are needed:
. System.currentTimeMillis() returns the current time.
. Runtime.freeMemory() returns the amount of free memory in the current
VM.
For example, to measure the time it takes to complete a big loop, you would
augment your code as follows:
long start_time = System.currentTimeMillis();
for (int i = 0; i < somethingBig; i++) {
// get some work done
}
long end_time = System.currentTimeMillis();
Computing the difference of end_time and start_time yields the amount of
time it took to complete the loop. Note that System.currentTimeMillis()
returns absolute system time, not process time, so you must be careful
not to load the machine with o