ArsDigita Archives
 
 
   
 
spacer

Java Programming Language Training Exercises

Compiled and maintained by Ravi Jasuja, Bill Schneider, Tracy Adams, and Shan Shan Huang.

  • Objectives:
    • Give programmers new to Java a quick introduction to the Java development process, the Java language and object oriented (OO) design.
    • Give a quick review for programmers with past Java experience.
    • Provide a quick introduction to JSP.
    • Certify ArsDigita programmers so that they can work on Java projects.
  • Audience:
    • Mainly programmers with little or no Java and JSP experience.
    • Object Orientated design experience is not necessary.
  • Time required:
    • New to Java and OO - 40+ hours (depends on programming skills)
    • New to Java - 30-40 hours
    • Experience with Java - ~10 hours
  • Training setup requirements
  • Maintainers
  • Please send email to all of us. (We are setting up an alias)
  • Last Updated
    • March 13, 2001, by Shan Shan Huang
  • Reading material and related documents

    Now get to work.

    Exercise 0: Background reading

    Read an overview of the Java and object oriented programming in one of the following:

    Exercise 1: Getting comfortable with the environment

    Learn how to write your first program. Read one of the following: Compile and run the "Hello World" or "HelloDate" program on your system. (These instructions assume you are working with Unix - see Your First Cup of Java for other platforms.
    • Create a directory named java in your home directory.
    • Set up your CLASSPATH variable. The CLASSPATH variable is one way to tell Java applications where to look for needed class files.
      • Check your environment variables to see if CLASSPATH contains ~/java 
        
<$ bash
$ env

PWD=/home/teadams/java
ORACLE_SID=ora8i
TZ=US/Eastern
HOSTNAME=dev0103-001.arsdigita.com
LD_LIBRARY_PATH=/ora8/m01/app/oracle/product/8.1.6/lib:/usr/lib:/usr/
local/lib:/ora8/m01/app/oracle/product/8.1.6/ctx/lib:/ora8/m01/app/or
acle/product/8.1.6/jdbc/lib
CLASSPATH=/ora8/m01/app/oracle/product/8.1.6/jdbc/lib/classes111.zip:
/ora8/m01/app/oracle/product/8.1.6/jdbc/lib/classes12.zip:/ora8/m01/a
pp/oracle/product/8.1.6/jdbc/lib/nls_charset12.zip
NLS_DATE_FORMAT=YYYY-MM-DD
MANPATH=/usr/share/man:/usr/openwin/share/man:/usr/local/man
USER=teadams
      • update the CLASSPATH to add ~/java if it is not there already 
        
$ export CLASSPATH=$CLASSPATH:~/java
      • This will only update your CLASSPATH for the current session. If you would like this change to be permanent, put the last line in your ~/.profile file.
    • Cut and paste HelloWorldApp or HelloDate into your text editor. Save the program as HelloWorldApp.java or HelloDate.java.
    • Compile the program: 
      
$ javac HelloWorldApp.java
    • Break a line of code and try compiling again to see what happens. Fix your code and recompile.
    • Run the program 
      
$ java HelloWorldApp
    • Read about JavaDoc in one of the following:
    • Add Javadoc comments to your program.
    • Make your class public.
    • Create a directory name documentation in your java directory.
    • Run javadoc to generate your documentation. 
    • javadoc -d documentation <classname.java>
    The documentation directory will contain documentation similar in format to JavaTM 2 Platform, Standard Edition, v 1.3 API Specification. You can view the html files in the documentation directory. If you are curious, move your files to a web server and view the documentation for your class.
Note: ACS makes use of javadoc in several places (tcl, jsp, adp, ajb scripts and procedures) to generate documentation for the API browser.

Exercise 2: Recursion and Iteration

Dig deeper into the language by reading either: Write a class named Fib whose main method computes the nth number in the Fibonacci sequence (1, 1, 2, 3, 5, 8, 13, etc.) both iteratively and recursively. The fibonacci sequence is defined by the recurrence: 
fib(n) = fib(n-1) + fib(n-2)
and the base cases: 
fib(0) = 0
fib(1) = 1
This class, as well the rest of the classes in this problem set, should be put in a package called pset.

To create a package pset:

  • Create a directory in ~/java called pset.
  • Put your java files in the pset directory.
  • The following should be the first non-comment line in each of your java files. 

package pset;

In addition, they all should be commented using javadoc.

Your main should take two command line arguments. The first is a string with values "I" or "R" to select the Interative or Recursive versions, respectively. The second is an integer, which is the argument to fib() (Remember to convert this from String to int. Hint: Use Integer.parseInt).

You should be able to run your fibonacci program as follows (note the package name): 

$ java pset.Fib R 10

Use the UNIX time command to time both versions on fib(10) and fib(40). Is there a lesson to be learned here?

Exercise 3: A Polynomial Class

Add a class Polynomial to your pset package representing polynomials (mathematical expressions of the form a0 + a1*x + a2*x^2 + a3*x^3 + ... + an*x^n) with integer coefficients. Implement the following methods: 

/** Constructor from an array of coefficients c[] where c[i] is the 
coefficient of the x^i term */
public Polynomial(int[] coef) { 

}

/** returns the power of the highest-order non-zero term. */
public int degree() {
  
}

/** returns a string representation of the polynomial (use 
"x" as the dummy variable and format high-order to low-order powers */
/** Your string should be in the following form:
  * x+2*x^2-5*x^5+x^6
  *
  * NOTE: if your string does not follow the above format, the provided
  * parser functions will not work for you!
  */
public String toString() {


}

/** operations on Polynomials returns this + a */
public Polynomial add(Polynomial a) {

} 

/** returns this - a */
public Polynomial sub(Polynomial a) {

} 

/** returns this * a*/
public Polynomial mul(Polynomial a)  {

}

/** returns this * c */
public Polynomial scale(int c)  {

}
Note that you don't have to implement subtraction directly, you can implement it as p1.add(p2.scale(-1)).

Comment your class with Javadoc compatable comments.

Use the following process to write your classes.

  • Create ~/java/pset/Polynomial.java
  • Cut and paste the start from this problem set.
  • Fill in class with dummy variables, casts, and return statements. Fill in your javadoc documenation. Make sure this framework compiles. This will help you make sure you understand what Polynomial is supposed to do, what object types you will need to deal with, and how these relate to other classes.
  • Write a drive class to test the implementation. Try to think of test cases that will implement every type of situation. When you write your driver, make sure each test returns a definitive indication of whether or not it worked. For example, the test case should return "Failure: 2+2=4 - returned value was 5" instead of "2+2 = 5" or "5". This will make your harness more convenient to use and more useful for regression tests. (In ACS, we will be using a regression test harness, JUnit, for this purpose. We will consistently be emphasizing javadoc commenting and writing unit tests as you go.)
  • Fill in your methods one by one, testing as you go.

Questions:

  • This is an immutable implementation of polynomials. Unary operators like scale are called "producers" since they return new polynomials. What are the advantages and disadvantages of this choice?
  • the Polynomial class is a data abstraction because classes that use it, like your test driver, don't need to know about its internal representation to use it's methods. Give examples of ways that you might change the Polynomial class internally without changing the public interface that is shown to other classes.
Submit the source to Polynomial.java, your test driver, and your answers to the questions.

Exercise 4: Polynomials as Functions

Since polynomials are functions of a variable x, add the following methods to return the value of a Polynomial evaluated at x. Update your test driver accordingly. 


/** Given an integer x, return the value of a Polynomial evaluated at x. */
public int evaluate(int x);

/** Given a string representation of a Polynomial, and an integer x,
 *  evaluate the polynomial at x
 */
public static int evaluate(String s, int x);

NOTE: for your convenience, we are providing you with a string parsing method that returns you an integer array, given a string representation of a Polynomial. Paste the following code into your class definition of Polynomial.

To use this method (stringToCoefs(String s)), you must have your string representation of a Polynomial in the following format :

2+x^2-3x^3
Otherwise the method as written will fail. 

/**
 * Given a string representation of a Polynomial, return an
 * integer array of coefficients.
 *
 * @param s String representation of Polynomial.
 * @return int[] integer array of coefficients.
 */
public static int[] stringToCoefs(String s) {
    int thisSignIndex = 0;
    int[] coefAndDegree = new int[2];
    int lastDegree = 0;
    
    s = s.trim();
    
    if (s.indexOf("+", 1) == -1 && s.indexOf("-", 1) == -1) {
    // this polynomial only has one term.
    int[] coefs = new int[1];
    coefAndDegree = getCoefAndDegree(s);
    coefs[0] = coefAndDegree[0];
    return coefs;
    }
    
    thisSignIndex = Math.max(s.lastIndexOf("+"), s.lastIndexOf("-"));
    
    // figure out what the highest degree is and allocate 
    // space for int[] coefs accordingly.
    coefAndDegree = getCoefAndDegree(s.substring(thisSignIndex));
    int[] coefs = new int[coefAndDegree[1]+1];
    coefs[coefAndDegree[1]] = coefAndDegree[0];
    
    // loop through each polynomial term except for the last --
    // since we already took care of that in the above code.
    while (s.indexOf("+", 1) != -1 || s.indexOf("-", 1) != -1) { 
    for (int i = 1 ; i < s.length(); i ++ ) {
        char ch = s.charAt(i);
	    if (ch == '+' || ch == '-') {
	    thisSignIndex = i;
	    break;
	        }
		}
		
		coefAndDegree = getCoefAndDegree(s.substring(0, thisSignIndex));
		coefs[coefAndDegree[1]] = coefAndDegree[0];
		
		// make sure to initalize the missing degrees with coefficent 0.
		if (coefAndDegree[1] -1 > lastDegree) {
		    for (int i=lastDegree+1; i<coefAndDegree[1]; i++) {
		    coefs[i] = 0;
		        }
			}
			lastDegree = coefAndDegree[1];
			s=s.substring(thisSignIndex).trim();
    }
    
    return coefs;
}


/**
 * given one term of a polynomial, returns a int[2],
 * with int[0] being the coefficient of that term,
 * and int[1] being the degree.
 * 
 * @param s String representing one term of the polynomial.  i.e. -2x^2
 * @return int[2] int[0] is the coefficient of the polynomial term, 
 *         int[1] is the degree of the term.
 */
private static int[] getCoefAndDegree(String s) {
    s = s.trim();
    
    // integer array to store return result in.
    int[] cAndd = new int[2];
    
    int degree =0;
    int coef =0;
    
    // figure out wheather the coefficient should be positive of negative.
    boolean minus_p = false;
    int signIndex = s.lastIndexOf("+");
    if (signIndex == -1) {
    signIndex = s.lastIndexOf("-");
    if (signIndex != -1) {
        minus_p = true;
	}
    }
    int xIndex = s.lastIndexOf("x");
    int degreeIndex = s.lastIndexOf("^");
    
    if (xIndex == -1) {
    // this term is of degree 0
    coef = Integer.parseInt(s.substring(signIndex+1).trim());
    if (minus_p) {
        coef = 0-coef;
	}
	cAndd[0] = coef;
	cAndd[1] = 0;
    } else {
    // this term has an x, and thus degree > 0
    if ( xIndex == 0 ) {
        // there is no coefficient for this term.
	    coef = 1;
	    } else {
	        if ( s.substring(signIndex+1, xIndex).trim().equals("")) {
		coef = 1;
		    } else {
		    coef = Integer.parseInt(s.substring(signIndex+1, xIndex).trim());
		        }
			    if (minus_p) {
			    coef = 0-coef;
			        }
				}
				
				if (degreeIndex == -1) {
				    degree = 1;
				    } else {
				        degree = Integer.parseInt(s.substring(degreeIndex+1).trim());
					}
					cAndd[0] = coef;
					cAndd[1] = degree;
    }
    
    return cAndd;
}

Question:
  • What are the advantages and disadvantages of choosing static methods for binary operators vs. instance methods? (In this case we do both).
Submit the source to Polynomial.java, your test driver output, and answer to the question.

Exercise 5: Class Design

Read more about relationships between objects by choosing either:

Design a class hierarchy (classes and/or interfaces) to support a program dealing with geographic objects. Support the following classes (at least):

  • Countries
  • States/Provinces
  • Cities
  • Boundary Segments
  • Rivers
Support the following operations, where applicable, plus any others that seem useful (arguments have been omitted): 
area()
capital() 
getCities()
getCountry()
distance() (between cities)
boundaryLength() (total length of boundary)
neighbors() (objects sharing boundaries)
borderOf() (the countries/states this separates)

Draw a picture of your classes and how they relate.

Write out the class definition, instance variables and method definitions. Don't bother to implement the methods (but make sure you could). Use interfaces and superclasses where appropriate. Supply javadoc comments for all classes, interfaces, and methods.
Note: This problem is deliberately openended. Don't panic!
Submit: Your class and method definitions (in a single text file).

Exercise 6: Priority Queue

Read more about containers in one of the following: Priority queues are containers that hold objects that can be compared. That is have an order relation equivalent to > (greater-than). Objects are inserted into a priority queue in any order, but are removed in sorted order. That is, the largest (or smallest) element in the queue is removed and returned first. The basic PriorityQueue interface is 
public interface PriorityQueue { 
   // Add an Object to the queue 
   public void insert(Comparable a); 
 
   // Removes and returns the maximum object from the
   // queue 
   public Comparable removeMax(); 

   // Returns true iff queue is empty 
   public boolean empty(); 
 
   // Returns the number of objects in the queue 
   public int length(); 
}
These queues can only hold references to objects belonging to classes that implement the Comparable interface. (Note: This interface is defined in package java.lang so you needn't redefine it; you will have to be sure to import java.lang.* in your PriorityQueue class though.) 
interface Comparable {

   // Returns a negative integer, 0, or a positive integer  
   // depending on whether 'a' in
   // less-than, equal to, or greater than the implicit arg 
   // (this) in the desired ordering. 
   public int compareTo(Object a); 

}

You should read the full definition of the Comparable interface at JavaTM 2 Platform, Standard Edition, v 1.3 API Specification.

Follow the process outlined in Exercise 3 to write a class PQueue that implements PriorityQueue in the pset package. (You can just extend your Poly test driver.) Don't worry about efficiency. Use the collection LinkedList as the underlying data structure. It is easiest to sort the objects as they are inserted. Make sure the structure can grow to arbitrary size, yet properly shrinks when items are removed.

The Java String and Integer classes implement Comparable. Test your class by inserting a handful of Strings and removing them, verifying they come out in the right order. Test that it still work when you interleave inserts and removes.

Modify your Poly class to implement Comparable. The ordering for polynomials is based upon the following rules:

  • a higher degree polynomial is greater than a lower degree one
  • for polynomials of equal degree, compare based upon coefficients from highest order to lowest order terms
For example: 
x^5 > 10*x^4 + 20*x^3
x^4 + 6*x + 10 > x^4 + 3*x + 20
Questions:
  • What happens if you insert some Strings then some Integers (remember: this is the class wrapper for int, not the int type). What happens if you try to removeMax()? This reveals a problem with this type of abstraction. Is there any good solution?
  • The java.util package has a class TreeMap which implements similar functionality to PriorityQueue. It can use the Comparable interface to sort, but it also allows the specification of a Comparator object in the constructor. A Comparator is a class with a binary compare() function.
    The significant difference is that the Comparator is attached to the TreeMap rather than the elements themselves (as is the case with the compareTo method of Comparable). Does this solve the problem encountered above?
Submit: PQueue.java and answers to questions.

Exercise 7: A simple JSP page

Read one of the following JSP tutorials. Up to this point we've been implementing Java classes and executing them from the command line by explicitly invoking the JVM with the "java" command. Now we're going to shift gears and start running Java code over the Web, taking input from URL/form variables and displaying output in the web browser as HTML.

A convenient way of running Java code over the Web is Java Server Pages (JSP). JSPs contain a mixture of HTML and Java code. The HTML is displayed directly in the browser, and the Java code is executed to generate dynamic HTML displaying the results of some computations, database queries, etc. JSPs are translated into Java classes, compiled, and executed by a "JSP engine"; all of the HTML text ends up getting translated into println calls, whose output goes to the browser. This turns out to be very useful because you'll usually want to display much more formatting information on a Web page than you would from the command line, and explicitly wrapping each line of HTML inside a println call can be cumbersome and hard to maintain.

If you do not have Tomcat set up, download and install Tomcat from the Jakarta-Apache project (http://jakarta.apache.org). This is an open-source JSP and servlet engine. (Servlets are Java classes that process a request and return output; JSPs are translated into servlets and can be thought of as a servlet-on-the-fly.) After following the directions and starting Tomcat, you should have a working HTTP server that you can access at http://localhost:8080 (unless you configured the port number). The notes on configuring Tomcat in Getting Started with ACS 4.0 Java will help you set up your configuration file.

Tomcat is implemented entirely in Java, which means that starting your Tomcat server invokes the Java Virtual Machine (sometimes called the "Java Runtime Environment") just as you did in the previous exercises by using the "java" command explicitly. But, rather than displaying the results of a computation to the command line, the Java program listens to incoming HTTP requests and processes them accordingly, which usually means generating an HTTP response to display HTML text in the browser.

Look through the example JSP code. (If your JSP's don't work, it is likely that you need to

  • Add an environment variable JAVA_HOME that points to the top level JDK directory.
  • Add JAVA_HOME/lib/tools.jar to your CLASSPATH environment variable.
Note how URLs translate into the location of JSP files in the file system; http://localhost:8080/examples/jsp/snp/snoop.jsp serves the file $TOMCAT_HOME/webapps/examples/jsp/snoop.jsp. Also note that JSP pages are just like HTML pages, except they have some extra tags to escape into Java code and display the value of Java variables.

Make two new pages: one to display a form asking the user's name, and the other to display a hello-world message ("hello, [name], I'm talking to you in JSP."). The form-input page can be static HTML, and the output page should be a JSP.

Submit: the two pages you created.

Exercise 8: Using Java classes in JSPs

Now that you know how to create a basic JSP, you're going to use JSP as an interface to the Fibonacci class you created in Exercise 1.
  • copy your Fibonacci class into $TOMCAT_HOME/webapps/examples/WEB-INF/classes/pset. This ensures that any web page running in the "examples" web application will see your class. (You can also use the CLASSPATH environment variable to tell Tomcat about other classes it should use, but copying a file tends to be less painful and more foolproof.)
  • Make an HTML form as you did previously, to ask the user what fibonacci number they want, and whether they want it computed recursively or iteratively.
  • Make a JSP page that takes the user input from the form, computes a result using the Fibonacci class you implemented in Exercise 1, and generates output to the browser.
  • Question: Think about how we could have implemented the iterative version of the fibonacci function pretty easily entirely in the JSP without using a separate class. Is this a good idea? Do we gain anything from putting the Fibonacci logic in a separate class?

Submit the new pages you wrote, and any modifications to your Fibonacci class, along with your answer to the above question.

Who Wrote This and When

Some of the problems were collected from the ArsDigita University course and originally developed by Dr David Goddeau. These were compiled and modified by Bill Schneider and Ravi Jasuja. Tracy Adams added links to outside material, design methodoly tips, and command line instructions. Bruce Keilin tested the problem set and made several documentation edits.
©1999-2001 ArsDigita Corporation

Reader's Comments

Observations on this so far (having worked through most of part 3):
  • It would be useful if the Javadoc in the sample code was actually complete. That is, where are the @param and @returns tags?
  • The interface presented for the Poly class makes no mention of a "getter" method for the coefficient array. Given that this problem set is for beginners, it would be wise to hint at the concept of data hiding.
  • You mention "producers" as a pattern for methods that do not alter the message sink object, but rather produce new objects that reflect the method's operation. This should be discussed a bit more. Beginners to Java, or any reference-based OO language (as opposed to pointer-based, such as C++) will likely be confused by this.
  • JUnit is mentioned as being required. Again, beginners are not likely to understand how it works with their source code. A simple example with the Fib class would be beneficial.


-- Stephen Silber, March 15, 2001
spacer