ArsDigita Logo

Java Programming Language Training Exercises

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

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: 


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.

Questions:

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: 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):

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:

For example: 
x^5 > 10*x^4 + 20*x^3
x^4 + 6*x + 10 > x^4 + 3*x + 20
Questions: 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

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.

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):

-- Stephen Silber, March 15, 2001
Advertisements