3.2   Creating Data Types


This section under major construction.


In principle, we could write all of our programs using only the eight built-in 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 data-type implementation that you will develop has the same basic ingredients as this simple example.

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.

Charge anatomy

Stopwatch.

Stopwatch.java implements the following API:


It is a stripped-down version of an old-fashioned 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.

Data-type 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. Turtle graphics was originally developed by Seymour Papert at MIT in the 1960s as part of an educational programming language, Logo. But turtle graphics is no toy, as we have just seen in numerous scientific examples. Turtle graphics also has numerous commercial applications. For example, it is the basis for PostScript, a programming language for creating printed pages that is used for most newspapers, magazines, and books.


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 well-defined 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 object-oriented 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 i2 - 1); and to compute the magnitude, as follows:

For example, if a = 3 + 4i, and b = -2 + 3i, then a + b = 1 + 7i, a * b = -18 + i, and |a| = 5.

With these basic definitions, the path to implementing a data type for complex numbers is clear. We start with an API that specifies the data-type operations:

Complex numbere API
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:

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 (self-similar) 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 zi+1 = (zi)2 + z0. For example, the following table shows the first few entries in the sequence corresponding to z0 = 1 + i:

Mandelbrot iteration
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:

Mandelbrot iteration

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. Zooming in on 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 N-by-N 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 2-by-2 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 self-similarities throughout the plot. For example, the same bulbous pattern with self-similar appendages appears all around the contour of the main black cardioid region. When we zoom in near the edge of the cardioid, tiny self-similar cardioids appear!

Mandelbrot set

Program Mandelbrot.java uses this test to plot a visual representation of the Mandelbrot set. Since our knowledge of the set is not quite black-and-white, 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 (no-argument) 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 no-argument 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 

public static Complex plus(Complex a, Complex b) {   
   return new Complex(a.re + b.re, a.im + b.im); 
}
but we avoid such usage so that we can write 
z = z.times(z).plus(z0).
instead of 
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 object-creation 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 non-static 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

  1. 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.

  2. Why does program Bug2.java create a java.lang.NullPointerException when executed?
  3. Implement a data type Die for rolling a fair die, say with 6 sides. Include a mutator method roll() and an accessor method value.
  4. Implement a mutable data type LFSR for a linear feedback shift register.
  5. Implement a mutable data type Counter.
  6. Implement a mutable data type Odometer.
  7. Implement a mutable data type StopWatch.
  8. 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.
  9. 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.

  10. 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.

  11. 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.

  12. 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();

  13. 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);
  14. 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.
  15. 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 no-argument 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;
  16. Add a method minus(Complex b) to Complex that takes a complex argument b and returns the difference between the invoking object and b.
  17. 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.
  18. Add a method conjugate() to Complex that returns the complex conjugate of the invoking object.
  19. 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.
  20. Write a program to read in three real numbers a, b, and c and print out all roots of ax2 + bx + c, including complex ones.
  21. 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).
  22. Write a program ColorMandelbrot.java that plots a color version of the Mandelbrot set. Read in a 256-by-3 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.

    Mandelbrot set           Mandelbrot set
    -1.5 -1.0 2.0 2.0 0.10259 -0.641 0.0086 0.0086
  23. 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 4-by-4 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 256-by-3 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.

    Julia set           Julia set
    -1.25 0.00 -0.75 0.10
  24. 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 L1-distance.
  25. Intervals. Create a data type Interval.java for intervals on the x-axis. 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.
  26. 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) 867-5309. Include a method so that p.equals(q) returns true if the phone numbers p and q are the same, and false otherwise.
  27. 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.

  28. Write a program to draw the field lines for a uniform field. Arrange N evenly-spaced 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

  1. IP addresses. Create a data type for IPv4 (Internet Protocol, version 4) addresses. An IP address is a 32-bit integer.
  2. 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.
  3. 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.
  4. 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 a2 and a 0 with probability b2. 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.
  5. Biorhythms. A biorhythm is a pseudo-scientific 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 (1-12), day (1-31), and year (1900-2100) 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.
  6. 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).
  7. 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.
  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.
  9. Vector3. Include normal vector operations for 3-vectors, 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. (a1, a2, a3) cross (b1, b2, b3) = (a2 b3 - a3 b2, a3 b1 - a1 b3, a1 b2 - a2 b1). 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.
  10. Four-vector. Create a data type for four-vectors. A four-vector is a four-dimensional vector (t, x, y, z) subject to Lorentz transformations. Useful in special relativity.
  11. Euclidean points. Create a data type EuclideanPoint.java that represents a d-dimensional point. Include a method so that p.distanceTo(q) returns the Euclidean distance between points p and q.
  12. 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.
  13. Soda machine. Create a data type SodaMachine that has methods insertCoin(), getChange(), buy(), etc.
  14. 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


  15. Chaos with Newton's method. The polynomial f(z) = z4 - 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) = z4 - 1 and f'(z) = 4z3. 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.

    Newton's method

  16. 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.
  17. Rational numbers. Create a data type Rational.java and BigRational.java for positive rational numbers.
  18. Rational numbers. Modify Rational.java to provide support for negative rationals and zero.
  19. 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 4-tuple 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(a02 + a12 + a22 + a32). 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 is the product of the inverse of (a0, a1, a2, a3) and (b0, b1, b2, b3). Note that ab doesn't equal ba in general.

  20. 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.

    Electric equipotential                Electric equipotential

    It is also interesting to plot the field lines and the equipotential lines simultaneously. The field lines are always perpendicular the the equipotential lines.

  21. Tensors. Create a data type for tensors.
  22. 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.
  23. 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.
  24. 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 FIPS55-DC3 Index: Pennsylvania (2MB) or all 50 states plus DC and 9 outlying areas (30MB).
  25. 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 earth-info.
  26. Astronomy. Data for asteroids, meteors, and comets.
  27. 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.
  28. 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). Fields are separated by one or two "\t" characters. Data from here.
  29. Molecular weight. Write a program so that the user enters a molecule H2 O and the program calculates its molecular weight.
  30. 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.

  31. Student records. Create a data type Student.java to represent students in an introductory computer science course. Each student record object is comprised of four instance variables representing the first name, last name, email address, and section number. Include a toString() method. Also include a method less() to compare students by section.
  32. 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 series-parallel network for RLC circuits with impedances instead of resistance

  33. Diffusion of particles in a fluid. Simulate diffusion of particles in a fluid. See BrownianParticle.java in Section 9.8.
  34. 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 qi is given by Ei = k qi / r2, and the direction points to qi if qi is negative and away from qi it is negative. 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.

    Electric potential      Electric potential

    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 1-pixel circle around the charge, at twelve equally spaced angles. The electric field at a point (x, y) from a point charge qi is given by Ei = k qi / r2, where qi 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 y-components. 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.

    Electric potential and field lines      Electric potential and field lines
  35. 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.

    Koch Snowflake Koch Snowflake Koch Snowflake Koch Snowflake Koch Snowflake
  36. Anti-Koch snowflakes. The anti-Koch 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 anti-Koch snowflake of order N using Turtle graphics.
  37. 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.
  38. Turtle graphics.
    1. Minkowski sausage. (Sausage.java)
    2. Gosper island.
    3. Cesaro broken square.
  39. More turtle graphics. Write a program to produce each of the following recursive patterns.
    1. Levy tapestry. (Levy.java)
    2. Fudgeflake.
  40. 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.
    1. Hilbert space-filling curve. (Hilbert.java or SingleHilbert.java) Informally, a space-filling curve is a continuous curve in the unit square that passes through every point. In 1890, Giuseppe Peano discovered the first such space-filling curve. In 1891, David Hilbert discovered a simpler version, which came to be known as the Hilbert curve.
      Hilbert curve of order 1 Hilbert curve of order 2 Hilbert curve of order 3 Hilbert curve of order 4 Hilbert curve of order 5
    2. Sierpinski arrowhead.
    3. Sierpinski curve.
  41. Dragon curve. Write a program Dragon.java that reads in a command-line 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.

  42. 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.
  43. 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 divide-and-conquer: 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.
  44. 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)
  45. 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.
  46. What is the principle value of ii?

    Answer: e-Π/2 = 0.207879576....

  47. 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.)


Copyright © 2007 Robert Sedgewick and Kevin Wayne. All rights reserved.