Due: 11:59 PM, Tuesday, September 18st

Purpose

The goal of this assignment is to simulate the physics of interplanetary motion. You will also get experience producing animated graphical output.

Before Lab

Read this document carefully, and make sure you have read all of chapter 1 in your textbook. Also read pages 382-384 from your textbook, and read the helpful tutorial on debugging in eclipse that is posted at the top of the CS101 Resources webpage.

In Lab

Task 1: [20 minutes] Computer Graphics

In this first part of the exercise, you will learn about two topics: graphics and libraries. When we talk about graphics, we’re talking about programs that present their output in the form of pictures rather than in textual form. Modern computer games, computational photography, and scientific data visualization, as well as many other applications output data in graphical form. When we talk about libraries in computer science, we’re talking about collections of programs that your programs can use, so that you don’t have to write the code yourselves. In this exercise, you will use someone else’s code to actually display graphical output. The way that you’ll use their code is by calling procedures that their code implements. So, let’s get started.

A. [5 minutes] Get the library. Create a new project called Triangle in Eclipse. Add a new file (use File>New>File) called StdDraw.java (you’ll enter this as the name of the file when you create it). This is the file that will contain the Java code for generating graphical output. Now rather than writing that code yourselves (which you’re not quite ready to do) go get it from here: http://www.cs.princeton.edu/introcs/15inout/StdDraw.java.html.  Just copy the contents of this file into your StdDraw.java file. Don’t worry about the details of this code. 

B. [10 minutes] Create a program that uses the library. Libraries are great. Not only don’t you have to write the code. You don’t even have to understand it.All you have to understand are the procedures that the library provides for your use. One of the most important of all concepts in computer science (and in many other disciplines) is thus embodied in the library: the concept  we call abstraction. Abstraction is the ability to ignore inessential details to focus on the essence. With libraries, the code is a detail you can ignore. What matters are the procedures that the code implements. For example, StdDraw provides procedures for doing such things as drawing lines, points, circles and images. The set of procedures that a library implements is often called an application programming interface (or just API). The principle of abstraction allows you to use a library knowing only its API, without having to understand the code that implements the API. Abstraction is the key to the intellectual control of complex software systems. 

Let’s see how it works. Here’s a simple program that uses the StdDraw library. Add a second file to your project. Triangle.java (you can do this with File>New>File or File>New>Class – in fact there are several ways to accomplish this simple task; just pick one). Here’s the code to type in to Triangle.java. Do not run your program yet! Don’t run it until instructed to do so.

public class Triangle {
   public static void main(String[] args) {
      double t = Math.sqrt(3.0) / 2.0;
      StdDraw.line(0.0, 0.0, 1.0, 0.0);
      StdDraw.line(1.0, 0.0, 0.5,   t);
      StdDraw.line(0.5,   t, 0.0, 0.0);
      StdDraw.point(0.5, t/3.0);
   }
}

C. [5 minutes] A note on specifications. What you see in this program are several uses of several libraries. The first library used is Math. The second library used is StdDraw. Now to find out what a library procedure does and how it’s used (or called or invoked), using Eclipse you can hover your mouse pointer over the name of the procedure. So, for example, to find out what the line procedure of the StdDraw library does, just hover your pointer over the procedure name, line. (The text that Eclipse displays here is present as a specially formatted comment in StdDraw.java.) This sort of description of what a procedure does is called its specification. The code that implements the procedure to satisfy the specification is called the implementation. The principle of abstraction says that to use a library we need only know its specifications not its implementations. Congratulations! You have now learned about libraries, abstraction, and the difference between specifications and implementations.

D. [5 minutes] Reason about your program then run your program to test your hypothesis. Next, read the specifications of the procedures again, then read your Triangle program from beginning to end, and see if you can figure out what it does. What you’re doing is one of the most common and important tasks in programming: to develop a hypothesis about what a program does and how it does it. Do this before you run your program. Now, in order to test your hypothesis, run your Triangle program. Were you right? If not, figure out why. Congratulations! You have reasoned about a program, run it to test your ideas, and by the way, you have also written your first computer graphics program. Include your name and the names of any collaborators in a comment at the top of your file and submit your Triangle.java file.

Task 2: [20 minutes] Program Understanding Using a Debugger

Eclipse provides rich support from program debugging. That is, it provides a debugger tool. A debugger is useful for several tasks. First, you can use a debugger to see what a program does as it executes line-of-code by line-of-code. That is, you can use it to help you understand what a program is doing. That’s what we’ll do today. Second, you can use a debugger to help you to test hypotheses about the causes of errors in programs that compile and run but that produce incorrect results. We’ll learn about using a debugger in this way – for debugging (thus the name) – later in the semester.

To start off with, set a breakpoint on the first line of code in the implementation of the Triangle program: the line that says public static void main(String[] args). To set a breakpoint, double-click on the grey panel that is to the left of your program code or right click and then select Toggle Breakpoint. The addition of the breakpoint will be indicated in several ways. First, a blue dot appears where you clicked. Second, the breakpoint will be added to the breakpoints panel, which you don’t see yet but which will appear on your screen after the next step.

Now go to the “Run” menu and select the “Debug” option; or, equivalently, click on the bug-shaped icon next to the run icon on the displayed toolbar.  You may get a message about changing your perspective to the Debug mode.  Select yes to this question.  (An Eclipse perspective is a set of panels useful for a particular task, in this case debugging.) Eclipse will start the Triangle program, and you will notice that many of your windows have changed.  Eclipse has switched you to the Debug perspective. To switch between the Java programming and Debugging perspectives, click on either the “Debug” picture or the “Java” picture on the top-right corner of your screen. For now you should be in the Debug perspective.

In this debugging mode, you can step through your program line by line and see what happens at each step. To begin with, you will need to learn how to use three important tools: Step Into, Step Over, and Step Return.  All three of these command can be found under the Run menu. They are also available as toolbar icons in the Debug toolbar, or as function keys. “Real” computer scientists learn to use the function keys.

• Step Over: This command executes one statement and returns control to the user at the end of the statement; and when the statement being executed is a procedure call, e.g., a call to StdDraw.line(), Step Over executes the whole procedure in one step without displaying the internal details of that procedure’s execution. It stops at the next statement after the procedure call. In this sense, it steps over (or hides and lets you ignore the details of) the procedure’s execution. Step over does not bypass the procedure: it actually does run; but simply does not display the details. Step Over thus implements another form of abstraction.

• Step Into: This command behaves just like step over – in the sense that it  inside either a function call, or a conditional statement, or a loop statement.

• Step Return: This command executes all the necessary commands needed to complete the current function call.  It is often used in combination with the “Step Into” command.

First trace through the execution of the Triangle program by running “Step Over” for all statements in the program.  As you step through your program, take very careful notice of how declared variables and their values appear in the top-right window of Eclipse. To be able to see what’s happening as your program runs is extremely valuable. You cannot do well in CS101 without becoming very proficient with the debugger. It’s really essential as an aid to program understanding. When your program terminates, Eclipse leaves you in a state in which you can debug the program again.

Start up the debugger again. This time, , use the “Step Into” command to step into the first instance of the StdDraw.line procedure. What you’ll see is the execution of the code that implements the line procedure. To get out of this method, keep single stepping (using step over) until the procedure is done. Then once again Step Into the second invocation of the line procedure. This time, use the “Step Return” command to tell the debugger to keep proceed without your intervention until control returns to the Triangle program.

Play around with the three debugging commands until you are comfortable with them.  The Eclipse window in the top-right corner of your screen (it says “Debug”) will tell you what line in your code you are currently executing.  Look for the words “Thread [main]”. After you leave lab, and from now on when you’re writing programs, get in the habit of using the debugger to help you understand what your program is really doing.

Task 3 [20 minutes] For Loops and Statement Blocks

A. On your own, without help from your fellow students, write a new Java program called Loops.java. The program should have a single for loop, with an index variable j thatruns from 0 to 9. On each iteration of the loop, output the value of the variable j followed by a single space.  Set a breakpoint at the start of your program and run the whole program in the debugger. As your program runs, watch carefully both the pane that shows the variables and their values as well as the console output pane at the bottom of your screen. Wait for your TA to discuss this program before moving to the next step.

B. Continuing on your own, modify the program that you just wrote in the following way. Enclose the loop that you just wrote so that it becomes the body of an outer for loop. The outer loop should have an index variable i that again runs from 0 to 9. Before you run this new program, figure out exactly what it’s going to do. Run the program to test your ideas. If you were right, great. If you were wrong, figure out why and do not procedure until you understand what’s happening. ASK THE TA A QUESTION if you don’t understand.

C. Add a println(); statement in the right place (figure this out) so that the program prints ten separate lines of output, each containing the numbers from 0 to 9 separated by spaces. One of the challenges here is to make sure that you put curly braces in the right places! Be sure you understand where they go and why they go there. Run you program as a way to test the hypothesis that it will behave as you intend and expect.

D. Now change the line of code that prints the value of j so that it instead prints the value of i*10+j. Before you run your program, figure out what it’s going to do. It’s extremely important that you be able to figure this one out. If you can’t then we guarantee that you will have problems in the remainder of this course. Take this opportunity to make sure you know what’s going on. Next, run your program to test your idea. If you were wrong, figure out why. Finally, run your program in the debugger, watching very carefully three things: (1) exactly which lines of code are being executed an in what order, (2) how the values of the index variables are changing, and (3) the output that’s being produced.

E. Finally, modify your program as follows, then (without running it) reason about what it is going to do, then run it to test your understanding. The change you will make is to output not the value of i*10+j but the value of (i*10+j)%2. What do you expect to see? Once you’ve done this, change the 2 to 3. What do you expect to see. Go ahead and see if you were right. Submit your Loops.java program.

Task 4 [15 minutes]: Discuss

The discussion section will have two important themes:

• statements vs. blocks, and
• variable scope.

You may follow along, we will be using the following example to facilitate discussion: https://www.cs.virginia.edu/~ms6ep/cs101/lab02/Discussion.java.

Time permitting, we will also answer any questions you had on the work you just did.

Post-Lab

Again we urge you to start early. The assignment this week is quite a bit more demanding that last week’s.

Background

In 1687 Sir Isaac Newton formulated the principles governing the the motion of two particles under the influence of their mutual gravitational attraction in his famous Principia. However, Newton was unable to solve the problem for three particles. Indeed, in general, systems of three or more particles can only be solved numerically. Write a program to simulate the motion of N particles, mutually affected by gravitational forces, and animate the results. Such methods are widely used in cosmology, semiconductors, fluid dynamics and to study complex physical systems. Scientists also apply the same techniques to other pairwise interactions including Coulombic, Biot-Savart, and van der Waals.

The physics

We review the equations governing the motion of the particles according to Newton's laws of motion and gravitation. Don't worry if your physics is a bit rusty; all of the necessary formulas are included below. We'll assume for now that the position (r_x, r_y) and velocity (v_x, v_y) of each particle is known. In order to model the dynamics of the system, we must know the net force exerted on each particle.

Pairwise force.

Newton's law of universal gravitation asserts that the strength of the gravitational force between two particles is given by the product of their masses divided by the square of the distance between them, scaled by the gravitational constant G (6.67 × 10^-11 N m² / kg²). The pull of one particle towards another acts on the line between them. Since we are using Cartesian coordinates to represent the position of a particle, it is convenient to break up the force into its x and y components (F_x, F_y) as illustrated below.

Net force.

The principle of superposition says that the net force acting on a particle in the x or y direction is the sum of the pairwise forces acting on the particle in that direction.

Acceleration.

Newton's second law of motion postulates that the accelerations in the x and y directions are given by: a_x = F_x / m, a_y = F_y / m.

The numerics

We use the leapfrog finite difference approximation scheme to numerically integrate the above equations: this is the basis for most astrophysical simulations of gravitational systems. In the leapfrog scheme, we discretize time, and update the time variable t in increments of the time quantum Δt. We maintain the position and velocity of each particle, but they are half a time step out of phase (which explains the name leapfrog). The steps below illustrate how to evolve the positions and velocities of the particles.

1. Calculate the net force acting on each particle at time t using Newton's law of gravitation and the principle of superposition.

2. For each particle:

   1. Calculate its acceleration (a_x, a_y) at time t using its force at time t and Newton's second law of motion.

   2. Calculate its velocity at time t + Δt / 2 by using its acceleration at time t and its velocity (v_x, v_y) at time t - Δt / 2. We assume the acceleration remains constant in this interval: the updated velocity is (v_x + Δt a_x, v_y + Δt a_y).

   3. Calculate its position at time t + Δt by using its velocity at time t + Δt / 2 and its position at time t. We assume the velocity remains constant in the interval from t to t + Δt: the resulting position is (r_x + Δt v_x, r_y + Δt v_y). Note that because of the leapfrog scheme, the constant velocity we are using is the one estimated at the middle of the interval rather than either of the endpoints.

3. Draw each particle.

As you would expect, the simulation is more accurate when Δt is very small, but this comes at the price of more computation. Use Δt = 25,000 for a reasonable tradeoff.

Creating an animation

Draw each particle at its current position using standard draw, and repeat this process at each time step. By displaying this sequence of snapshots (or frames) in rapid succession, you will create the illusion of movement. After each time step (i) draw the background image starfield.jpg, (ii) redraw all the bodies in their new positions, and (iii) control the animation speed using StdDraw.show().

Input format

The input file is a text file that contains the information for a particular universe. The first value is an integer N which stores the number of particles. The second value is a real number R which represents the radius of the universe: assume all particles will have coordinates that remain between -R and R. Finally, there are N rows, and each row contains 6 elements. The first two are the x and y coordinates of the initial position; the second two are the x and y coordinates of the initial velocity; the third is the mass; the last is a String that is the name of an image file used to display the particle. As an example, the input file planets.txt contains data for our solar system in MKS units.

5
2.50e11
1.496e11 0.000e00 0.000e00 2.980e04 5.974e24 earth.gif
2.279e11 0.000e00 0.000e00 2.410e04 6.419e23 mars.gif
5.790e10 0.000e00 0.000e00 4.790e04 3.302e23 mercury.gif
0.000e00 0.000e00 0.000e00 0.000e00 1.989e30 sun.gif
1.082e11 0.000e00 0.000e00 3.500e04 4.869e24 venus.gif

There are additional data files here. You can either download everything in that directory or download nbody.zip which contains all the files that you will need. This directory also contains the corresponding images.

Your program

Write a program NBody.java that reads in the universe from standard input using StdIn, simulates its dynamics using the leapfrog scheme described above, and animates it using our StdDraw. Maintain several arrays to store the data. To make the computer simulation, write an infinite loop that repeatedly updates the position and velocity of the particles. When plotting, consider using StdDraw.setXscale(-R, +R) and StdDraw.setYscale(-R, +R) to scale the physics coordinates to the screen coordinates.

Optional finishing touch

For a finishing touch, play the theme to 2001: A Space Odyssey using StdAudio and the file 2001.mid. It's a one-liner using the method StdAudio.play().

Extra credit

Submit a universe in our input format along with the necessary image files. If its behavior is sufficiently interesting, we'll award extra credit. In order to submit, put your universe, along with any necessary images, into a zipped file called "extracredit.zip", and submit it using the normal submission procedure.

Challenges for the bored

There are limitless opportunities for additional excitement and discovery here. Try adding other features, such as supporting elastic or inelastic collisions. Or, make the simulation three-dimensional by doing calculations for x, y, and z coordinates, then using the z coordinate to vary the sizes of the planets. Add a rocket ship that launches from one planet and has to land on another. Allow the rocket ship to exert force with consumption of fuel.

Submission

Go to the CS101 submission page and follow the instructions provided.