\documentclass{article}
\setlength{\textwidth}{6.0in}
\setlength{\textheight}{9.0in}
\setlength{\headheight}{0.0in}
\setlength{\headsep}{0.0in}
\setlength{\parskip}{1.5ex plus 0.5ex minus 0.5ex}
\setlength{\topmargin}{0.5in}
\setlength{\topskip}{0.0in}
\setlength{\evensidemargin}{0.5in}
\setlength{\oddsidemargin}{0.5in}
\newcounter{exercise}
\newcounter{problem}
\newcommand {\exercise}[1]{\bigskip\noindent{\large\bf Exercise \stepcounter{exercise} \arabic{exercise}: {#1}}}
\newcommand {\problem}[1]{\bigskip\noindent{\large\bf Problem \stepcounter{problem} \arabic{problem}: {#1}}}
\begin{document}
\begin{center}
\LARGE
Object-Oriented Programming in Java
\end{center}
\bigskip
{\noindent\Large\bf Problem Set 1 \hfill Due: Jan 8, 2001}
\hrule
\bigskip
\noindent{\Large\bf Exercises}
\bigskip
\exercise{Hello World}
Compile and run the Hello.java program. Modify the initial
message, recompilem, and re-run.
Add to Hello the recursive and iterative factorial methods from class.
Test these with calls from main().
\exercise{Arrays}
Write and test static methods
\begin{verbatim}
float Mean(float[] data)
float Variance(float[] data)
\end{verbatim}
which compute the mean and variance of the elements in data respectively.
\exercise{Recursion and Iteration}
Write a method that computes fib(x) recursively using the
recurrence
\begin{eqnarray}
&& fib(0) = 1 \nonumber \\
&& fib(1) = 1 \nonumber \\
&& fib(x) = fib(x-1) + fib(x-2). \nonumber
\end{eqnarray}
Now write a method that computes fib(x) iteratively. (Hint: Start from 0,
and compute the sum forward, saving the last two values each iteration).
Test these by calling from main()
\exercise{Command Arguments}
Modify your main() routine from Exercise 3 to take two arguments on the command line. The
first is a string with values ``I'' or ``R'' which selects the Interative
or Factorial versions respectively. The second is an integer which is the
arg to $fib()$ (Remember to convert this from String to int. Hint: Use
Integer.parseInt()).
Use the UNIX {\tt time} command to time both versions on $fib(10)$
and $fib(40)$. Is there a moral here?
\exercise{Arrays: A Word Problem}
If one lends D dollars at an (annual compound)
interest rate of r (ie r = 0.07 for $7\%$ interest). The investment, at
the end of N years, will be worth $D(1 + r)^N$ dollars. Inverting this,
to have a nest-egg of D dollars in N years, one must invest $D/(1 + r)^N$
dollars today. This quantity is called the Net Present Value or Discounted
Value of D dollars N years in the future. Some investments, like stocks
and bonds, produce an annual cash flow ($D_t$ for year t). The net present
value of such an asset is computed by summing the Discounted cash flows
for each year.
$$
NPV = \sum_t (D_t/(1+r)^t)
$$
a) Write a static method to compute the NPV of an investment returning
a constant $D_t = d$ dollars for N years assuming an interest rate of r.
(Assume the first payment comes in year 0 and is not discounted).
b) If you win \$2,000,000 in the Lottery, rather than a check for \$2M, you
will actually receive \$100,000 per year for the next 20 years. Call your
method to calculate the NPV of your prize assuming r=0.06 (ie 6\%). Compute the
NPV for a 9\% interest rate.
\bigskip
\noindent{\Large\bf Problems}
\bigskip
In this section, we will implement a number of simple numerical algorithms
and data structures in Java. \footnote{This is not to imply that Java is the
language of choice for numerical algorithms, or algorithms in general.
Algorithms are generally about program speed and efficiency, Java and OOP are
about {\it programmer} speed and efficiency in constructing large systems.
To quote {\it Numerical Recipes in C}, ``The practical scientist is trying to
solve tomorrow's problems with today's hardware, computer scientists, it
often seems, are doing the reverse.''}
\problem{Root Finding by Binary Search}
One algorithm for computing (approximately) the real roots of a
continuous function (i.e.; a value $R$ such that $f(R)=0$ ), is binary search.
Suppose you know two values $a$ and $b$ such that $f(a)$ and $f(b)$
have opposite signs. By the intermediate value theorem,
there is at least one root of $f$ between $a$ and $b$.
The root is said to be {\it bracketed} by $a$ and $b$.
We can now trap the root to any accuracy by computing
$f(x)$, where $x=(a+b)/2$ and comparing to $f(a)$ and $f(b)$.
If $f(x)$ has the same sign as $f(a)$, we know $x < R < b$, and if
$f(x)$ has the same sign as $f(b)$, we know $a < R < x$.
We can iterate this procedure to compute the root to any desired
accuracy. Note that the error in our estimate is halved each iteration.
Write a driver class {\tt FunctionTest } and implement the root bracketing
algorithm as a static method:
\begin{verbatim}
public static double bracketRoot(double a, double b, double maxerr);
\end{verbatim}
Use {\tt Math.sin()} as the function to be evaluated. Call this method from
{\tt main()} to find the root of $sin(x)$ between 3 and 4 to within $10^-8$.
Save your code. You will submit it as part of Problem 4.
\problem{Numerical Integration: Extended Trapezoidal Rule}
Another useful numerical algorithm computes definite integrals
through use of the trapezoidal approximation
\begin{displaymath}
\int\limits_a^b f(x) dx \approx (b-a){{f(a) + f(b)}\over 2}.
\end{displaymath}
This (crude) approximation can be made more accurate by dividing the
interval $[a,b]$ into $N$ segments of length $h=(b-a)/N$, computing
the integral over each of the segments and summing the result.
\footnote{ Remember the following property of integration:
$\int\limits_a^b f(x) dx = \int\limits_a^c f(x) dx + \int\limits_c^b f(x) dx$
}
The resulting approximation is
\begin{displaymath}
\sum_{i=0}^{N-1} h{{f(a + hi) + f(a + h(i+1))}\over 2}.
\end{displaymath}
Since the each intermediate point appears twice in the sum, this can be
simplified to
\begin{displaymath}
h{{f(a) + f(b)}\over 2} + \sum_{i=1}^{N-1} h{f(a + hi)}.
\end{displaymath}
Add a method to {\tt FunctionTest } that implements this algorithm
on {\tt Math.sin()} with the following signature:
\begin{verbatim}
public static double defIntegral(double a, double b, int N);
\end{verbatim}
Use this method to compute $\int\limits_0^\pi sin(x)$ and
$\int\limits_0^{2\pi} sin(x)$. Choose $N$ to be a power of
two such that the difference between using $N/2$ and $N$ is less
than $10^-8$ (ie start at $n=1024$ and double each time).
\footnote{In order to find an adequate value of $N$ for a given problem,
one must
iterate over increasing $N$ and re-computing the integral.
In this iteration, a lot of redundent work is performed. If $N$ is doubled
each time, it is possible to improve this algorithm by only computing
the sum for points not computed on the previous iteration (computed with
$N/2$ segments). This sum can be added to the result of the previous iteration
to give the correct approxiation for $N$ segments. For further refinements,
consult any numerical algorithms text.}
Save your code. You will submit it as part of Problem 4.
\problem{A Polynomial Class}
Write a class {\tt Poly} representing polynomials with integer
coefficients. Implement the following methods:
\begin{itemize}
\item {\tt Poly(int[] coef)} --
Constructor from an array of coefficients c[] where c[n] is the
coefficient of $x^n$.
\item {\tt int degree()} - returns the power of the highest non-zero term.
\item {\tt String toString()} - returns a string representation of the polynomial
(use ``x'' as the dummy variable and format high-order to low-order powers).
\end{itemize}
Add addition and multiplication in both static and instance forms:
\begin{itemize}
\item {\tt Poly add(Poly a)}
\item {\tt Poly mul(Poly a)}
\item {\tt static Poly add(Poly a, Poly b)}
\item {\tt static Poly mul(Poly a, Poly b)}
\end{itemize}
Rather than implement substraction, implement a scale method, which multiplies
all coefficient by a constant value.
Subtraction can them be implemented as p1.add(p2.scale(-1));
\begin{itemize}
\item Poly scale(int s)
\end{itemize}
Comment your class with Javadoc compatable comments and run Javadoc to
produce documentation. Hint: Use the {\tt -d} option to have the
documentation sent to a subdirectory of your working directory.
Write a driver class and test your implementation.
Download our PolyTest.class driver into your working directory and run it.
\medskip
{\bf Questions:}
\medskip
This is an immutable implementation of polynomials. Unary operators like
scale() return new polynomials. What are the advantages and disadvantages
of this choice?
What are the advantages and disadvantages of choosing static methods for
binary operators vs. instance methods? (In this case we do both).
\noindent{\bf Submit:} The source to Poly.java and your test driver,
the output of PolyTest, and your answers to the questions.
\problem{Inheritance}
We will now use inheritance to generalize the numerical routines from the
previous section.
Write a class {\tt RFunc } which will
represent the behavior of functions over the real numbers (or in
our case, Java {\tt double}s).
Since there is no such thing as a generic function, make {\tt RFunc}
an abstract class supporting the method
\begin{itemize}
\item {\tt public abstract double evaluate(double x)}
\end{itemize}
Generalize the bracketRoot and defIntegral methods you wrote earlier,
by replacing the calls to Math.sin() with calls to evaluate(),
and add them as instance methods to RFunc. (Remember
to document RFunc with Javadoc comments).
\begin{itemize}
\item {\tt public double bracketRoot(double a, double b, double maxErr)}
\item {\tt public double defIntegral(double a, double b, int N)}
\end{itemize}
Now that we have an abstract function class, we need some real functions.
Write subclasses of RFunc, SinFunc and CosFunc, that override the
evaluate() method to return Math.sin(x) and Math.cos(x) respectively.
Add JavaDoc comments everywhere, as always.
Write a test driver to find the root of cos(x) between 1 and 3. Compute
the integral of cos(x) from 0 to $\pi/2$ and 0 to $\pi$.
Download and run the FuncTest.class driver in your working directory
and submit the results.
\noindent{\bf Submit:} The source to RFunc.java, the output of FuncTest,
and your answers to the questions.
\problem{Polynomials as Functions}
Since polynomials can be considered as functions, modify Poly to
be a subclass of RFunc (add an evaluate() method).
Modify your driver class to compute the
positive root of $x^2-3$ and $x^2-x-1$. Also compute the integral
of $x^2-4$ from 0 to 2.
Re-run Javadoc on your function classes and browse the result.
Unlike arbitrary functions, polynomials can be integrated in closed form.
\begin{displaymath}
\int\limits_a^b f(x) dx = F(b) - F(a)
\end{displaymath}
where $F(x)$ is the indefinite integral of $f(x)$. For a polynomial
$\sum a_ix^i$ the indefinite integral is $\sum {a_ix^{i+1}\over{i+1}}$.
Use this principle to override the defIntegral method in Poly.
Use your test program to again compute the integral
of $x^2-4$ from 0 to 2.
Download and run the FuncTest2.class driver in your working directory
and submit the results.
\noindent{\bf Submit:} The source to Poly.java and the output of Func2Test.
\problem{Interfaces}
An alternate way to abstract functions is as an interface.
We can write an RFuncLib class to be
a repository for the bracketRoot and defIntegral methods,
and use an interface {\tt Function} to hold the {\tt evaluate} method.
Write a {\tt Function} interface with one method, {\tt evaluate}.
Modify SinFunc, CosFunc and Poly to implement Function rather than
extend RFunc. Write the RFuncLib class to contain your numerical routines
as static methods. You will need to modify them
to take an additional argument of type {\tt Function} and use this
as the function to evaluate. Test this new implementation.
Download and run the FuncTest3.class driver in your working directory.
\medskip
\noindent{\bf Questions:}
\medskip
What are some reasons for choosing the inheritance-based approach rather
than interface-based approach and vice-versa?
\noindent{\bf Submit:} The source to RFuncLib.java, Function.java,
the output of FuncTest3, and answers to questions.
\problem{Class Design}
Design a class hierarchy (classes and/or interfaces) to support a program
dealing with geographic objects. Support the following classes (at least):
\begin{itemize}
\item Countries
\item States/Provinces
\item Cities
\item Boundary Segments
\item Rivers
\end{itemize}
Support the following operations, where applicable, plus any others
that seem useful (arguments have been omitted):
\begin{itemize}
\item area()
\item capital()
\item getCities()
\item getCountry()
\item distance() -- between cities
\item boundaryLength() -- total length of boundary
\item neighbors() -- objects sharing boundaries
\item borderOf() -- the countries/states this separates
\end{itemize}
Write out the class definition, instance vars 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 open\-ended. Don't panic!
\noindent{\bf Submit:} Your class and method definitions (in a single text file).
\problem{Priority Queue}
Priority queues are containers that hold objects that can be compared. That is
have an order relation equivalent to $>$. Object are inserted into a
priority queue arbitrarily, but are removed in sorted order. That is,
the largest ( or smallest) element in the queue is removed and returned.
The basic PriorityQueue interface is
\begin{verbatim}
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();
}
\end{verbatim}
These queues can only hold Object classes which implement the
Comparable interface. (Note: This interface is defined in package
java.util so you needn't redefine it.)
\begin{verbatim}
interface Comparable{
/*
* Return -1,0,or 1 depending on whether 'a' in less-than, equal to,
* or greater than the implicit arg (ie 'this') in the desired
* ordering.
*/
public int compareTo(Comparable a);
}
\end{verbatim}
Write a class PQueue that implements PriorityQueue. [Don't worry about
efficiency. You can use a linked list, doubly-linked list, array, or
Vector 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:
compare degrees first, if degrees are equal, then compare leading
coefficients, if these are equal, compare on lower order terms.
\noindent{\bf 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.utils 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?
\noindent{\bf Submit:} PQueue.java and answers to questions.
\end{document}