3.2 Creating Data Types
This section under major construction.
In principle, we could write all of our programs using only the eight builtin primitive types, but, it is much more convenient to write programs at a higher level of abstraction. Accordingly, a variety of data types are built into the Java language and libraries. Still, we certainly cannot expect Java to contain every conceivable data type that we might ever wish to use, so we need to be able to define our own.
Basic elements of a data type.
To illustrate the process of implementing a data type in a Java class, we discuss each component for the Charge.java data type of Section 3.1. Every datatype implementation that you will develop has the same basic ingredients as this simple example. API.
The applications program interface is the contract with all clients
and therefore the starting point for any implementation:
To implement Charge, we need to define the data type values, then implement the constructor that creates objects having specified values, and then implement two methods that can manipulate those values.
 Class. The datatype implementation is a Java class. As usual, we put the code for a data type in a file with the same name as the class, followed by the .java extension. We have been implementing Java classes, but the classes that we have been implementing do not have the key features of data types: instance variables, constructors, and instance methods. Instance variables are similar to the variables that we have been using in our program; constructors and methods are similar to functions, but their effect is quite different. Each of these building blocks is also qualified by an access modifier. We next consider these four concepts, with examples.
 Access modifiers. We designiate every instance variable and method within a class (and the class itself) as either public (this entity is available to clients) or private (this entity is not visible to clients). Our convention is to use public for the constructors and methods in the API (since we are promising to provide them to clients) and private for everything else.
 Instance variables.
To write code for the methods that manipulate data
type values, the first thing that we need is to declare variables that
we can use to refer to the values in code. These variables can be
any type of data. We declare the types and names of these instance
variables in the same way as we declare local variables:
for Charge, we use three double
values, two to describe the charge's position in the plane and
one to describe the amount of charge.
There is a critical distinction between instance
variables and the local variables within a static method or a block that
you are accustomed to using: there is just one value corresponding to each
local variable name, but there are numerous values corresponding to each
instance variable (one for each object that is an instance of the data type).
 Constructors.
A constructor creates an object and provides a reference to
that object. Java automatically invokes a constructor when a client program
uses the keyword new. Java does most of the work: our code only needs to
initialize the instance variables to meaningful values. Constructors always
share the same name as the class.
To the client, the combination of new followed by a constructor name
(with argument values enclosed within parentheses) is the same
as a function call that returns a value of the corresponding type. A
constructor signature has no return type because constructors
always return a reference to an object of its data type.
Each time that a client invokes a constructor) Java automatically
 allocates memory space for the object
 invokes the constructor code to initialize the data type values
 returns a reference to the object
The constructor in Charge is typical: it initializes the data type values with the values provided by the client as arguments.
 Instance methods.
To implement instance methods, we write code that
is precisely like the code that we learned in Chapter 2 to implement static
methods (functions).
Each method has a signature (which specifies
its return type and the types and names of its parameter variables) and a
body (which consists of a sequence of statements, including a return
statement that provides a value of the return type back to the client). When a
client invokes a method, the parameter values are initialized with client
values, the lines of code are executed until a return value is computed,
and the value is returned to the client, with the same effect as if the method
invocation in the client were replaced with that value. All of this action is the
same as for static methods, but there is one critical distinction for instance
methods: they can perform operations on instance values.
 Variable names in methods.
Accordingly, code in instance methods uses three kinds of variables:
 parameter variables
 local variables
 instance variables
The first two of these are familiar: parameter variables are specified in the method signature and initialized with client values when the method is called, and local variables are declared and initialized within the method body, just as for static methods. The scope of parameter variables is the entire method; the scope of local variables is the block where they are defined. Instance variables are completely different: they hold datatype values for objects in a class, and their scope is the entire class. How do we specify which object's values we want to use? If you think for a moment about this question, you will recall the answer. Each object in the class has a value: the code in a class method refers to the value for the object that was used to invoke the method. When we write c1.potentialAt(x, y), the code in potentialAt() is referring to the instance variables for c1. The code in potentialAt() uses all three kinds of variable names:
Summary.
Here is a diagram illustrating all of the basic components that you need to understand to be able to build data types in Java.
Stopwatch.
Stopwatch.java implements the following API:
It is a strippeddown version of an oldfashioned stopwatch.
When you create one, it starts running, and you can ask it how long it has
been running by invoking the method elapsedTime().
Histogram.
Datatype instance variables can be arrays. Histogram.java maintains an array of the frequency of occurrence of integer values in a given interval [0, N) and uses StdStats.java to display a histogram of the values, controlled by this API:
Turtle graphics.
Turtle.java is a mutable type for turtle graphics. Ngon.
Program Ngon.java
takes a commandline argument N and draws a regular Ngon.
By taking N to a sufficiently large value, we obtain a good approximation to a circle. In Cartesian geometry, a circle is the locus of points at distance r from a fixed center point (a, b). Declarative definition describes points on a circle.
(x  a)^2 + (y  b)^2 = r^2
REPEAT GO FORWARD 1 UNIT TURN LEFT 1 UNIT
 Koch curves.
The Koch curve of
order 0 is a line segment.
To draw a Koch curve of order n in turtle graphics
 Draw a Koch curve of order n1
 Rotate 60° counterclockwise
 Draw a Koch curve of order n1
 Rotate 120° clockwise
 Draw a Koch curve of order n1
 Rotate 60° counterclockwise
 Draw a Koch curve of order n1
Below are the Koch curves of order 0, 1, 2, and 3.
Historical context: In 1872 Karl Weierstrass made the shocking discovery a function that is everywhere continuous but nowhere differentiable. Later this would become one of the characteristic properties of fractals. Helge von Koch wanted to find a less abstract example. In 1904, von Koch described the geometric construction, which we now refer to as the Koch curve. Von Koch proved that, in the limit, the Koch snowflake is a curve of infinite length, but it does not have a tangent at any point. From this, he proved that there exist continuous functions f(t) and g(t) such that the Koch snowflake is (f(t), g(t)) for 0 ≤ t ≤ 1, but f(t) and g(t) are nowhere differentiable.
 Spira mirabilis.
Spiral.java
creates a logarithmic spiral (aka equiangular spiral
or growth spiral). Biological principle: as size increases, shape is unaltered.
Radius grows exponentially with the angle.
 Brownian motion. Imagine a disoriented turtle (again following its standard alternating turn and step regimen) turns in a random direction before each step. DrunkenTurtle.java plots the path followed by such a turtle. In 1827, the botanist Robert Brown observed through a microscope that pollen grains immersed in water seemed to move about in just such a random fashion, which later became known as Brownian motion and led to Albert Einstein???s insights into the atomic nature of matter. DrunkenTurtles.java plots many such turtles, all of whom wander around.
Complex numbers.
A complex number is a number of the form x + iy, where x and y are real numbers and i is the square root of 1. The number x is known as the real part of the complex number, and iy is known as the imaginary part. Complex numbers are a quintessential mathematical abstraction: whether or not one believes that it makes sense physically to take the square root of 1, complex numbers help us understand the natural world. They are extensively used in applied mathematics and play an essential role in many branches of science and engineering. They are used to model physical systems of all sorts, from circuits to sound waves to electromagnetic fields. These models typically require extensive computations involving manipulating complex numbers according to welldefined arithmetic operations, so we want to write computer programs to do the computations. In short, we need a new data type.Developing a data type for complex numbers is a prototypical example of the value of objectoriented programming. No programming language can provide implementations of every mathematical abstraction that we might need, but the ability to implement data types give us not just the ability to write programs to easily manipulate abstractions like complex numbers, polynomials, vectors, matrices, and many other basic tools that have been developed by mathematicians over the past several centuries, but also the freedom to think in terms of new abstractions.
The basic operations on complex numbers are to add and multiply them by applying the commutative, associative, and distributive laws of algebra (along with the identity i^{2}  1); and to compute the magnitude, as follows:
 addition: (x+iy) + (v+iw) = (x+v) + i(y+w).
 multiplication: (x + iy) * (v + iw) = (xv  yw) + i(yv + xw).
 magnitude: x + iy = sqrt(x^2 + y^2)
 real and imaginary parts: re(x + iy) = x, and im(x + iy) = y
With these basic definitions, the path to implementing a data type for complex numbers is clear. We start with an API that specifies the datatype operations:
Program Complex.java is an immutable class that implements this API. It has all of the same components as did Charge (and every Java data type implementation): instance variables (re and im), a constructor, instance methods, and a test client.
The code that implements the arithmetic methods makes use of a new mechanism for accessing object values:
 Accessing values in objects of this type. Both plus() and times() need to access values in two objects: the object passed as a parameter and the object used to invoke the method. If the method is called with a.plus(b). we can access the values of a using the instance variable names re and im, as usual, but to access the values of of b we use the code b.re and b.im. However, since we keep the instance variables private, you cannot access directly instance variables in another class (but you can access any object's instance variables wihin the same class). This policy reduces flexibility but improves design when developing modular programs.
 Chaining. Observe the manner in which main() chains two method calls into one compact expression: the expression z.times(z).plus(z0) evaluates to z^{2} + z0. This usage is convenient because we do not have to invent a variable name for the intermediate value. If you study the expression, you can see that there is no ambiguity: moving from left to right, each method returns a reference to a Complex object, which is used to invoke the next method. If desired, we can use parentheses to override the precedence order (for example, z.times(z.plus(z0)) evaluates to z(z + z0)).
 Creating and returning new objects. Observe the manner in which plus() and times() provide return values to clients: they need to return a Complex value, so they each compute the requisite real and imaginary parts, use them to create a new object and then return a reference to that object. This arrangement allow clients to manipulate complex numbers by manipulating local variables of type Complex.
Mandelbrot set.
The uses complex numbers to plot a gray scale version of the The Mandelbrot set is a specific set of complex numbers with many fascinating properties. It is a fractal pattern that is related to the Barnsley fern, the Sierpinski triangle, the Brownian bridge, and oth er recursive (selfsimilar) patterns and programs that we have seen in this book. Patterns of this kind are found in natural phenomena of all sorts, and these models and programs are very important in modern science. The set of points in the Mandelbrot set cannot be described by a single mathematical equation. Instead, it is defined by an algorithm, and therefore a perfect candidate for a Complex client: we study the set by writing programs to plot it.The rule for determining whether or not a complex number z0 is in the Mandelbrot set is simple: Consider the sequence of complex numbers z0, z1, z2, ..., zi, ..., where z_{i+1} = (z_{i})^{2} + z0. For example, the following table shows the first few entries in the sequence corresponding to z0 = 1 + i:
Now, if the sequence zi diverges to infinity, then z0 is not in the Mandelbrot set; if the sequence is bounded, then z0 is in the Mandelbrot set. For many points, the test is simple; for many other points, the test requires more computation, as indicated by the examples in the following table:
Is a complex number in the set? In some cases, we can prove whether or not numbers are in the set: for example, 0 + 0i is certainly in the set (since the magnitude of all the numbers in its sequence is 0) and 2 + 0i is certainly not in the set (since its sequence dominates the powers of 2, which diverges). Given a complex point, we can compute the terms at the beginning of its sequence, but may not be able to know for sure that the sequence remains bounded. Remarkably, there is a test that tells us for sure that a point is not in the set: if the magnitude of any number in the sequence ever gets to be greater than 2 (like 3 + 0i), then the sequence will surely diverge.
Plotting the Mandelbrot set. A visual representation of the Mandelbrot set is easy to define. Just as we plot a real function by sampling points in an interval, we plot the Mandelbrot set by sampling complex points. Each complex number x + iy corresponds to a point (x, y) in the plane so we can plot the results as follows: for a specified resolution N, we define a regularly spaced NbyN pixel grid within a specified square and draw a black pixel if the corresponding point is in the Mandelbrot set and a white pixel if it is not. This plot is a strange and wondrous pattern, with all the black dots connected and falling roughly within the 2by2 square centered on the point 1/2 + 0i. Large values of N will produce higher resolution images, at the cost of more computation. Looking closer reveals selfsimilarities throughout the plot. For example, the same bulbous pattern with selfsimilar appendages appears all around the contour of the main black cardioid region. When we zoom in near the edge of the cardioid, tiny selfsimilar cardioids appear!
Program Mandelbrot.java uses this test to plot a visual representation of the Mandelbrot set. Since our knowledge of the set is not quite blackandwhite, we use grayscale in our visual representation. It is based on the following function (a Complex client), which computes the sequence starting at a given number and returns the number of iterations for which the magnitude stays less than 2, up to a given maximum:
public static int mand(Complex z0, int d) { Complex z = z0; for (int t = 0; t < d; t++) { if (z.abs() >= 2.0) return t; z = z.times(z).plus(z0); } return d; }
For each pixel, the method main() in Mandelbrot computes the point z0 corresponding to the pixel and computes 255  mand(z0, 255) to represent the grayscale value of the pixel. Any pixel that is not black corresponds to a point that we know to be not in the Mandelbrot set because the magnitude of the numbers in its sequence grew past 2 (and therefore will go to infinity); the black pixels (grayscale value 0) correspond to points that we assume to be in the set because the magnitude stayed less than 2 for 255 iterations, but we do not necessarily know for sure. The complexity of the images that this simple program produces is remarkable, even when we zoom in on a tiny portion of the plane. For even more dramatic pictures, we can use use color (see exercise 3.2.33).
Q + A
Q. Do instance variables have initial values that we can depend upon?
A. Yes. They are automatically set to 0 for numeric types, false for the boolean type, and the special value null for all reference types.
Q. What is null?
A. It is a literal value that refers to no object. Invoking a method using the null reference is meaningless and results in a NullPointerException.
Q. Can we initialize instance variables to other values when declaring them?
A. Yes, you can initialize instance variables using the same conventions as you have been using for initializing local variables. Each time an object is created by a client with new, its instance variables are initialized with those same values, then the constructor is called.
Q. Must every class have a constructor?
A. Yes, but if you do not specify a constructor, Java provides a default (noargument) constructor automatically. When the client invokes that constructor with new, the instance variables are initialized as usual. If you do specify a constructor, the default noargument constructor disappears.
Q. Suppose I do not include a toString() method. What happens if I try to print an object of that type with StdOut.println()?
A. The printed output is an integer: the object's hash code. Most objects that do not have an explicit toString() implementation also do not have an explicit hashCode() implementation. The default value is "typically implemented by converting the internal address of the object into an integer. "
Q. Can I have a static method in a class that implements a data type?
A. Of course. All of our classes have main(). But it is easy to get confused when static methods and instance methods are mixed up in the same code. For example, it is natural to consider using static methods for operations that involve multiple objects where none of them naturally suggests itself as the one that should invoke the method. For example, we say z.abs() to get z, but saying a.plus(b) to get the sum is perhaps not so natural. Why not b.plus(a)? An alternative is to define a static method within Complex, like
but we avoid such usage so that we can write
public static Complex plus(Complex a, Complex b) { return new Complex(a.re + b.re, a.im + b.im); }
instead of
z = z.times(z).plus(z0).
z = Complex.plus(Complex.times(z, z), z0)
Q. These computations with plus() and times() seem rather clumsy. Is there some way to use symbols like * and + in expressions involving objects where they make sense, like Complex and Vector, so that we could write expressions like z = z * z + z0 instead?
A. Some languages (notably C++) support this feature, which is known as operator overloading, but Java does not do so (except that there is language support for overloading + with string concatenation). As usual, this is a decision of the language designers that we just live with, but many Java programmers do not consider this to be much of a loss. Operator overloading makes sense only for types that represent numeric or algebraic abstractions, a small fraction of the total, and many programs are easier to understand when operations have descriptive names such as plus and times.
Q. Are there other kinds of variables besides parameter, local, and instance variables in a class?
A. If you include the keyword static in a class declaration (outside of any type) it creates a completely different type of variable, known as a static variable. Like instance variables, static variables are accessible to every method in the class; however, they are not associated with any object. In older programming languages, such variables are known as global variables, because of their global scope. In modern programming, we focus on limiting scope and therefore rarely use such variables.
Q. Is there a relationship between the Vector in this section and the Vector class in the Java library?
A. No. We use the name because the term vector properly belongs to phyiscs and linear algebra.
Q. Mandlebrot creates hundreds of millions of Complex objects. Doesn't all that objectcreation overhead slow things down?
A. Yes, but not so much that we cannot generate our plots. Our goal is to make our programs readable and easy to maintain  limiting scope via the complex number abstraction helps us achieve that goal. You certainly could speed up Mandelbrot by bypassing the complex number abstraction or by using a different implementation of Complex.
Q. What does the error message "can't make a static reference to a nonstatic variable" mean?
A.
public class Test { private static int M; // class variable private int N; // instance variable public static int getM() { return M; } // OK public static int getN() { return N; } // ERROR }
Exercises

Why does program Bug1.java create a
java.lang.NullPointerException when executed?
public class Bug1 { private String s; public void Bug1() { s = "hello"; } public String toString() { return s; } public static void main(String[] args) { Bug1 x = new Bug1(); StdOut.println(x); } }
Answer: the programmer probably intended to make the no argument constructor set the string to hello. However, it has a return type (void) so it is an ordinary instance method instead of a constructor. It just happens to have the same name as the class.
 Why does program Bug2.java create a java.lang.NullPointerException when executed?
 Implement a data type Die for rolling a fair die, say with 6 sides. Include a mutator method roll() and an accessor method value.
 Implement a mutable data type LFSR for a linear feedback shift register.
 Implement a mutable data type Counter.
 Implement a mutable data type Odometer.
 Implement a mutable data type StopWatch.
 Implement a data type VotingMachine for tabulating votes. Include mutator methods voteRepublican(), voteDemocrat(), and voteIndependent(). Include an accessor method getCount() to retrieve the total number of votes.

What happens when you try to compile and execute the following code fragment?
Student x; StdOut.println(x);
Answer: it complains that x may not be initialized, and does not compile.

Suppose you want to add a constructor to Complex that takes one
real argument and initializes a complex object with that value.
You write the following code
public void Complex(double real) { re = real; im = 0.0; }
Why does the statement Complex c = new Complex(1.0) given a compiler error? Answer: constructors do not have return types, not even void. So the code above is actually a method named Complex not a constructor. Remove the keyword void and it will work. This is a common gotcha.

What happens when you try to compile and execute the following code fragment?
Student[] students = new Student[10]; StdOut.println(students[5]);
Answer: it compiles and prints out null.

What is wrong with the following code fragment?
int N = 17; Dog[] dogs = new Dog[N]; for (int i = 0; i < N; i++) { dog.bark(); dog.eat(); }
Answer: it produces a NullPointerException because we forgot use new to create each individual Dog object. To correct, add the following loop after the array initialization statement.
for (int i = 0; i < N; i++) dogs[i] = new Dog();

What does the following code fragment print?
Complex c = new Complex(2.0, 0.0); StdOut.println(c); StdOut.println(c.mul(c).mul(c).mul(c)); StdOut.println(c);
 Modify the toString method in Complex.java so that it prints 3  i as 3  i instead of 3 + i, and prints 3 as 3 instead of 3 + 0i.

What's wrong with the following code fragment that swaps
the Student objects x and y?
Student swap = new Student(); swap = x; x = y; y = swap;
Answer: First, the data type Student does not have a noargument constructor. If it did, then it would technically be correct, but the new Student() line is unnecessary and wasteful. It allocates memory for a new student object, sets swap equal to that memory address, then immediately sets swap equal to the memory address of x. The allocated memory is no longer accessible. The following version is correct.
Student swap = x; x = y; y = swap;
 Add a method minus(Complex b) to Complex that takes a complex argument b and returns the difference between the invoking object and b.
 Add a method divides(Complex b) to Complex that takes a complex argument b and returns the quotient of the invoking object divided by b.
 Add a method conjugate() to Complex that returns the complex conjugate of the invoking object.
 Write a program RootsOfUnity.java that takes a command line argument N and uses Complex to compute and print out the N Nth roots of unity.
 Write a program to read in three real numbers a, b, and c and print out all roots of ax^{2} + bx + c, including complex ones.
 Find inputs to the Mandelbrot update formula that make it converge (z0 = 1/2 + 0i), cycle with a period of 1 (z0 = 2 + 0i), cycle with a period of 2 (z0 = 1 + 0i), or stay bounded without converging (z0 = 3/2 + 0i).

Write a program ColorMandelbrot.java
that plots a color version of the Mandelbrot set. Read in a 256by3
array of color values from standar input into an array,
and then use the ith color if the Mandelbrot function takes i iterations.
Use the data file mandel.txt as an example.
1.5 1.0 2.0 2.0 0.10259 0.641 0.0086 0.0086  Julia sets.
The Julia set for a given complex number c is a set of points
related to the Mandelbrot function. Instead of fixing z and varying c,
we fix c and vary z.
Those points z for which the modified Mandelbrot function stays
bounded are in the Julia set; those for which the sequence diverges
to infinity are not in the set. All points z of interest lie in the
the 4by4 box centered at the origin. The Julia set for c
is connected if and only if c is in the Mandelbrot set!
Write a program ColorJulia.java
that takes two command line parameters a and b, and plots a color version of
the Julia set for c = a + ib. Read in a 256by3
array of color values from standar input into an array,
and then use the ith color if the Julia function takes i iterations.
Use the data file mandel.txt as an example.
1.25 0.00 0.75 0.10  Point3D. Create a data type for points in 3 dimensional space. Include a constructor that takes three real coordinates x, y, and z. Include methods distance, distanceSquared, and distanceL1 for the Euclidean distance, Euclidean distance squared, and the L1distance.
 Intervals. Create a data type Interval.java for intervals on the xaxis. An interval is the set of points in the range [left, right]. Include methods for a constructor (including a check that the left endpoint is no greater than the right endpoint) and a method intersects so that a.intersects(b) returns true if the intervals a and b intersect, and false otherwise.
 Create a data type PhoneNumber.java that represents a US phone number. The constructor should take three string arguments, the area code (3 decimal digits), the exchange (3 decimal digits) and the extension (4 decimal digits). Include a toString method that prints out phone numbers of the form (800) 8675309. Include a method so that p.equals(q) returns true if the phone numbers p and q are the same, and false otherwise.
 Redo PhoneNumber.java
but implement it using three integer fields. Make the
constructor take three integer arguments. Comment on the advantages
and disadvantages of this approach over the string representation.
Answer: more efficient with time and memory. More hassle to handle leading 0s correct in constructor and toString method.
 Write a program to draw the field lines for a uniform field. Arrange N evenlyspaced particles with charge e in a vertical column, and arrange N particles with charge e in a vertical column so that each charge on one side is lined up with a corresponding charge on the other side. This simulates the field inside a plane capacitor. What can you say about the resulting electric field? A. Almost uniform.
Creative Exercises
 IP addresses. Create a data type for IPv4 (Internet Protocol, version 4) addresses. An IP address is a 32bit integer.
 Dates. Create a data type Date that represents a date. You should be able to create a new Date by specifying the month, day, and year. It should supports methods to compute the number of days between two dates, return the day of the week that a day falls on, etc.
 Time bombs. UNIX represents the date with a signed integer measuring the number of seconds since January 1, 1970. Write a client program to calculate when this date will occur. Add a static method add(Date d, int days) to your date data type that returns a new date which is the specified number of days after the date d. Note that there are 86,400 seconds in a day.
 Qubits. In quantum computing, a qubit plays the role of a bit. It is a complex number a + bi such that a + bi = 1. Once we measure a qubit, it "decides" to be a 1 with probability a^{2} and a 0 with probability b^{2}. Any subsequent observations will always yield the same value. Implement a data type Qubit that has a constructor Qubit(a, b) and a boolean method observe that returns true or false with the proscribed probabilities.
 Biorhythms. A biorhythm is a pseudoscientific profile of the three natural cycles of your body: physical (23 days), emotional (28 days), and intellectual (31 days). Write a program that takes six command line inputs M, D, Y, m, d, and y where (M, D, Y) is the month (112), day (131), and year (19002100) of your birthday and (m, d, y) is today's month, day, and year. It should then print out your biorhythm on a scale of 1.0 to 1.0 according to the formula: sin (2 π age / cycle length). Use the date data type created in the previous exercise.
 Particle. Create a data type for elementary or composite particles (electron, proton, quark, photon, atom, molecule). Each particle should have an instance variable to store its name, its mass, its charge, and its spin (multiple of 1/2).
 Quark.
Quarks are the smallest known building blocks of matter.
Create a data type for quarks.
Include a field for its type (up, down, charm, strange, top, or bottom)
and its color (red, green, or blue).
The charges are +2/3, 1/3, +2/3, 1/3, +2/3, 1/3, respectively.
All have spin 1/2.
Diffusion of particles in a fluid.
Simulate diffusion of particles in a fluid. See BrownianParticle.java in Section 9.8.  Biorhythms. Plot your biorhythm in turtle graphics over a 6 week interval. Identify critical days when your rhythm goes from positive to negative  according to biorhythm theory, this is when you are most prone to accident, instability, and error.
 Vector3. Include normal vector operations for 3vectors, including cross product. The cross product of two vectors is another vector. a cross b = a b sin(theta) n, where theta is angle between a and b, and n is unit normal vector perpendicular to both a and b. (a_{1}, a_{2}, a_{3}) cross (b_{1}, b_{2}, b_{3}) = (a_{2} b_{3}  a_{3} b_{2}, a_{3} b_{1}  a_{1} b_{3}, a_{1} b_{2}  a_{2} b_{1}). Note that a cross b = area of the parallelogram with sides a and b. Cross product arises in definition of torque, angular momentum and vector operator curl.
 Fourvector. Create a data type for fourvectors. A fourvector is a fourdimensional vector (t, x, y, z) subject to Lorentz transformations. Useful in special relativity.
 Euclidean points. Create a data type EuclideanPoint.java that represents a ddimensional point. Include a method so that p.distanceTo(q) returns the Euclidean distance between points p and q.
 Vector field. A vector field associates a vector with every point in a Euclidean space. Widely used in physics to model speed and direction of a moving object or or strength and direction of a Newtonian force.
 Soda machine. Create a data type SodaMachine that has methods insertCoin(), getChange(), buy(), etc.
 Months.
Write a data type Month that represents one of
the twelve months of the year. It should have fields for
the name of the month, the number of days in the month,
and the birthstone.
MONTH DAYS BIRTHSTONE January 31 Garnet February 28 Amethyst March 31 Aquamarine April 30 Diamond May 31 Emerald June 30 Alexandrite July 31 Ruby August 31 Peridot September 30 Sapphires October 31 Opal November 30 Topaz December 31 Blue Zircon
 Chaos with Newton's method.
The polynomial f(z) = z^{4}  1 as 4 roots at 1, 1, i, and i.
We can find the roots using Newton's method over the complex
plane: z_k+1 = z_k  f(z_k)/f'(z_k).
Here f(z) = z^{4}  1 and f'(z) = 4z^{3}.
The method converges to one of the 4 roots depending on the starting
point z_0.
Choose each point in the complex plane with coordinates between
1 and 1 and determine which of the four roots it converges to,
and plot the point either white, red, green, or blue accordingly.
If Newton's method doesn't converge after 100 iterations, color
the point black. Name your program NewtonChaos.java.
 Gauss multiplication. Implement complex multiplication using only 3 floating point multiplications (instead of 4). You may use as many as 5 floating point additions. Answer: Gauss gave the following method to multiply (a + bi)(c + di). Set x1 = (a + b)(c + d), x2 = ac, x3 = bd. Then the product is given by x + yi where x = x2  x3, y = x1  x2  x3.
 Rational numbers. Create a data type Rational.java and BigRational.java for positive rational numbers.
 Rational numbers. Modify Rational.java to provide support for negative rationals and zero.
 Quaternions.
In 1843, Sir William Hamilton discovered an extension to complex
numbers called
quaternions.
Quaternions
extend the concept of rotation in three dimensions to
four dimensions. They are used in computer graphics, control theory,
signal processing, and orbital mechanics, e.g., command for
spacecraft attitude control systems.
are related to Pauli spin matrices in physics.
Create a date type Quaternion.java
to represent quaternions.
Include operations for adding, multiplying, inverting, conjugating,
and taking the norm of quaternions.
A quaternion can be represented by a 4tuple of real numbers (a0, a1, a2, a3), which represents a0 + a1 i + a2 j + a3 k. The funadmental identity is i^2 = j^2 = k^2 = ijk = 1. The quaternion conjugate is (a0, a1, a2, a3). The quaternion norm is sqrt(a0^{2} + a1^{2} + a2^{2} + a3^{2}). The inverse of a quaternion is (a0/d, a1/d, a2/d, a3/d) where d is the square of the quaternion norm. The sum of two quaternions (a0, a1, a2, a3) and (b0, b1, b2, b3) is (a0+b0, a1+b1, a2+b2, a3+b3), the product is (a0b0  a1b1  a2b2  a3b3, a0b1 + a1b0 + a2b3  a3b2, a0b2  a1b3 + a2b0 + a3b1, a0b3 + a1b2  a2b1 + a3b0), and the quotient a/b is the product of (a0, a1, a2, a3) and the inverse of (b0, b1, b2, b3). Note that ab doesn't equal ba in general.
 Equipotential surfaces.
An equipotential surface is the set of all
points that have the same electric potential V. Given a group of N
point charges, it is useful to visualize the electric potential
by plotting equipotential surfaces (aka countour plots).
Program Equipotential.java
draws a line every 5V by computing the potential at each
gridpoint and checking whether the potential is within 1 pixel of a multiple of
5V. Since the electric field E measures how much the potential changes,
E * eps is the range that the potential changes in a distance of 1 pixel.
It is also interesting to plot the field lines and the equipotential lines simultaneously. The field lines are always perpendicular the the equipotential lines.
 Tensors. Create a data type for tensors.
 UN Countries. Create a data type Countryfor UN countries. Include fields for 3 digit UN Code, 3 letter ISO abbreviation, country name, and capital. Write a program Country.java that reads in a list of countries and stores them in an array of type Country. Use the method String.split to help parse the input file.
 Area codes. Create a data type for telephone area codes in North America. Include fields for the area code, the city, and state, and the two letter state abbreviation. Or for international phone codes. Include a field for zone, code, and country.
 Congressional districts. Create a data type for places, counties, and congressional districts. Include fields for place name, county name, county code, zip code, congressional district, etc. Use the data sets from the 1998 FIPS55DC3 Index: Pennsylvania (2MB) or all 50 states plus DC and 9 outlying areas (30MB).
 Latitudes and longitudes. For USA latitudes and longitudes, use the TIGER database or www.bcca.org or gazetteer. For the rest of the world, use earthinfo.
 Astronomy. Data for asteroids, meteors, and comets.
 Fortune 1000 companies. Create a data type the for Fortune 1000. Include fields for company name and sales revenue in millions of dollars. Data taken from April 15, 2002 issue of Fortune. Note: currently need to parse data.
 Elements. Create a data type Element.java for the Periodic Table of Elements. Include fields for element, atomic number, symbol, and atomic weight. (Ignore fields for boiling point, melting point, density (kg/m3), Heat vapour (kJ/mol), heat fusion (kJ/mol), thermal conductivity (W/m/K), and specific heat capacity (J/kg/K) since it's not know for all elements). The file is in CSV format (fields separated by commas).
 Molecular weight. Write a program so that the user enters a molecule H2 O and the program calculates its molecular weight.
 Some potentially useful datafiles: aroma therapies, nutritional information, meteorological glossary, psychiatric disorders, words translated in 15 languages, dictionary of emoticons, meanings of common names, World Almanac facts about countries.
 Student records.
Create a data type Student.java
to represent students in an introductory computer science course.
Each student record object should represent a first name,
last name, email address, and section number.
Include a toString() method that returns a string representation
of a student and a less() method that compares two students by section number.
To do so, implement the following API:
public class Student  public Student(String first, String last, String email, int section) public boolean less(Student s2) // true if this student's section is smaller than that of s2 String toString() // string representation of student (section, first name, last name, and email)
 Impedance.
Impedance is the generalization of resistance from DC circuits
to AC circuits.
In an AC circuit, the impedance of a component
measures its opposition to the flow of electrons at a given
frequency ω. The impedance has two components: the resistance
and the reactance.
The resistance R of a circuit component measures its
opposition to the movement of electrons (friction against
motion of electrons) when a given voltage is applied.
The reactance X of a circuit component measures its
ability to store and release energy as the current and voltage
fluctuate (inertia against motion of electrons).
In circuits with resistors only, the current is directly proportional to the voltage. However, with capacitors and inductors, there is a + 90 degree "phase shift" between the current and voltage. This means that when the voltage wave is at its maximum, the current is 0, and when the current is at its maximum the voltage is 0. To unify the treatment of resistors (R), inductors (L), and capacitors (C) it is convenient to treat the impedance as the complex quantity Z = R + iX. the impedance of an inductor is iwL and the impedance of a capacitor is 1/iwC. To determine the impedance of a sequence of circuit elements in series, we simply add up their individual impedances. Two important quantities in electrical engineering are themagnitude of the impedance and the phase angle. The magnitude is the ratio of the RMS voltage to the RMS current  it equals the magnitude of the complex impedance. The phase angle is the amount by which the voltage leads or lags the current  it is the phase of the complex impedance. Program CircuitRLC.java does a computation involving complex numbers and impedance of circuits with resistors, inductors, and capacitors in series.
Exercise: RLC circuit in parallel. 1/Z = 1/Z1 + 1/Z2 + ... 1/Zn.
Exercise (for objects): repeat seriesparallel network for RLC circuits with impedances instead of resistance
 Diffusion of particles in a fluid. Simulate diffusion of particles in a fluid. See BrownianParticle.java in Section 9.8.
 Electric field lines.
Michael Faraday introduced an abstraction called electric field lines
to visualize the electric field.
By Coulombs law, the electric field at a point induced by a point
charge q_{i} is given by E_{i} = k q_{i} / r^{2},
and the direction points to q_{i} if q_{i} is negative and
away from q_{i} it is positive.
If there are a group of n point charges, the electric field at a point is
the vector sum of the electric fields induced by the n individual
point charges. We can compute it by summing up the components in the x and y
directions. The figure below illustrates the field lines for two equal
positive point charges (left) and two point charges of opposite signs (right).
The second configuration is called an electric dipole:
the charges cancel each other out, and the electric field weakens very
quickly as you move away from the charges. Examples of dipoles can be found
in molecules where charge is not evenly distributed. Oscillating dipoles
can be used to produce electromagnetic waves to transmit radio and television signals.
Program FieldLines.java draws 10 electric field lines coming out of each charge. (We take some liberties since traditionally the number of field lines per unit area should be proportional to the magnitude of the field strength.) Each line starts on a 1pixel circle around the charge, at twelve equally spaced angles. The electric field at a point (x, y) from a point charge q_{i} is given by E_{i} = k q_{i} / r^{2}, where q_{i} is the magnitude of the charge i and r is the radial distance from it. The field due to several charges is the vector sum of the field due to each, and can be found by adding the x and ycomponents. After calculating the electric field strength, we move in the direction of the vector field and draws a spot. We repeat this process until we reach the boundary of the region or another point charge. The figures below illustrate the electric potential and field lines for several random charges of equal magnitude.
 Koch snowflake with rainbow of colors.
The Koch snowflake of order n consists of three copies of the Koch curve of over n. We draw the three Koch curves one after the other, but rotate 120° clockwise in between. Below are the Koch snowflakes of order 0, 1, 2, and 3. Write a program KochRainbow.java that plotsthe Koch snowflake in a continuous spectrum of colors from red, to orange, yellow, green, blue, and indigo, and violet.
 AntiKoch snowflakes.
The antiKoch snowflake is generated exactly like
the Koch snowflake, except that clockwise and counterclockwise
are interchanged. Write a program AntiKoch.java that
takes a command line parameter N and plots the antiKoch snowflake
of order N using Turtle graphics.
 Randomized Koch snowflakes. A randomized Koch snowflake is generated exactly like the Koch snowflake, except that we flip a coin to generate the clockwise and counterclockwise direction at each step.
 Turtle graphics.
 Minkowski sausage. (Sausage.java)

Gosper island.

Cesaro broken square.
 Minkowski sausage. (Sausage.java)
 More turtle graphics.
Write a program to produce each of the following recursive patterns.
 Levy tapestry. (Levy.java)
 Fudgeflake.
 Levy tapestry. (Levy.java)

Turtle graphics (hard).
Write a program to produce each of the following recursive patterns
without lifting the pen or tracing over the same line segment more
than once.

Hilbert spacefilling curve. (Hilbert.java or
SingleHilbert.java)
Informally, a spacefilling
curve is a continuous curve in the unit square that passes through every point.
In 1890, Giuseppe Peano discovered the first such spacefilling curve.
In 1891, David Hilbert discovered a simpler version, which came to be known
as the Hilbert curve.

Sierpinski arrowhead.

Sierpinski curve.

Hilbert spacefilling curve. (Hilbert.java or
SingleHilbert.java)
Informally, a spacefilling
curve is a continuous curve in the unit square that passes through every point.
In 1890, Giuseppe Peano discovered the first such spacefilling curve.
In 1891, David Hilbert discovered a simpler version, which came to be known
as the Hilbert curve.
 Dragon curve.
Write a program Dragon.java that
reads in a commandline parameter N and plots the order N dragon
curve using turtle graphics. The dragon curve was first discovered
by three NASA physicists (John E. Heighway, Bruce A.
Banks, and William G. Harter) and later popularized by Martin Gardner in Scientific
American (March and April 1967) and Michael Crichton in Jurassic Park.
This is a sophisticated program that uses two mutually recursive functions.
Program SequentialDragon.java is an iterative version of the dragon curve. It is a hacker's paradise.
 Mandelbrot trajectory. Write an interactive program Trajectory.java that plots the sequence of points in the Mandelbrot iteration in the complex plane. If the user clicks on (x, y), plot the sequence of iterates for z = x + iy.
 Faster Mandelbrot. Speed up Mandelbrot by performing the computation directly instead of using Complex. Compare. Incorporate periodicity checking or boundary tracing for further improvements. Use divideandconquer: choose 4 corners of a rectangle and a few random points inside; if they're all the same color, color the whole rectangle that color; otherwise divide into 4 rectangles and recur.
 More Complex methods.
Add methods to Complex.java
to support trigonometric and exponential functions on complex numbers.
 exp(a + ib) = e^a cos(b) + i e^a sin(b)
 sin(a + ib) = sin(a) cosh(b) + i cos(a) sinh(b)
 cos(a + ib) = cos(a) cosh(b)  i sin(a) sinh(b)
 tan(a + ib) = sin(a + ib) / cos(a + ib)
 Add a method power to Complex so that a.power(b) returns the result of taking the complex number a and taking it to the complex power b.

What is the principle value of i^{i}?
Answer: e^{Π/2} = 0.207879576....
 Random walker. Write a data type RandomWalker that simulates the motion of a random walker in the plane that starts at the origin and makes a random step (left, right, up, or down) at each step. Include a method step() that moves the random walker one step and a method distance() that returns the distance the random walker is from the origin. Use this data type to formulate a hypothesis as to how far (as a function of N) the random walker is from the origin after N steps. (See also Exercise 1.x.)
 Turtle graphics. Extend Turtle in various ways. Make DeluxeTurtle that adds color, etc. Add a version that supports error checking. For example, throw a TurtleOutOfBounds exception if turtle goes outside designated boundary.