\documentclass{article}
\usepackage{graphics}

\title{Exercise Sets: How to Design Class Hierarchies}
\author{Viera K. Proulx and Matthias Felleisen}

\begin{document}

\maketitle

\section*{Exercise Set 1A: Exploring Numbers and Arithmetic}

\smallskip
\par
\textbf{Exercise 1A.1} Use the function \texttt{computeInt} to
determine the
result of the following expressions: \\
\indent{\texttt{27 \% 4},}\\
\indent{\texttt{-27 \% 4},}\\
\indent{\texttt{27 \% -4},}\\
\indent{\texttt{-27 \% -4},}\\
\indent{\texttt{27.5 \% 4}.}
\smallskip
\par
\noindent\textbf{Exercise 1A.2} Use the function
\texttt{computeInt} to
determine the result of the following expressions: \\
\indent{\texttt{150 / 3 * 10}\\
\indent{\texttt{150 / (3 * 10)}\\
\indent\texttt{10 / 3 * 10}.
\smallskip
\par\noindent\textbf{Exercise 1A.3} Use the function \texttt{computeInt} to
determine the result of the following expressions: \\
\indent{\texttt{150 - 20 - 30 - 10}\\
\indent{\texttt{150 - (20 - 30) - 10)}\\
\indent\texttt{(150 - 20) - (30 - 10)}.
\smallskip
\par\noindent\textbf{Exercise 1A.4} Use the function \texttt{computeInt} to
determine the result of the following expressions. Experiment with
the second
expression to find out what is the largest integer Java can represent.\\
\indent{\texttt{4 * 4 * 4 * 4 * 4 * 4 * 4 * 4 * 4 * 4 * 4 * 4 * 4 * 4 * 4}\\
\indent{\texttt{16 * 16 * 16 * 16 * 16 * 16 * 16 * 16 * 16 * 16}.
\smallskip
\par\noindent\textbf{Exercise 1A.5} Use the function \texttt{computeInt} to
determine the result of the following expressions. Experiment with
the second expression to find out what is the largest magnitude of
a negative integer that Java can represent.\\
\indent{\texttt{-4 * 4 * 4 * 4 * 4 * 4 * 4 * 4 * 4 * 4 * 4 * 4 * 4 * 4 * 4}\\
\indent{\texttt{-16 * 16 * 16 * 16 * 16 * 16 * 16 * 16 * 16 * 16}.
\smallskip
\par\noindent\textbf{Exercise 1A.6} Use the function \texttt{computeDouble} to
determine the result of the following expressions: \\
\indent{\texttt{27.6 \% 4}\\
\indent{\texttt{-27.6 \% 4}\\
\indent{\texttt{27.6 \% -4}\\
\indent{\texttt{-27.6 \% -4}.
\smallskip
\par
\noindent\textbf{Exercise 1A.7} Use the function
\texttt{computeDouble} to
determine the result of the following expressions: \\
\indent{\texttt{10 / 3 * 3.0)}\\
\indent\texttt{10 / 3.0 * 3}\\
\indent\texttt{10.0 / 3 * 3}\\
\indent\texttt{10.0/3/3/3/3/3 *3*3*3*3*3}\\
\indent\texttt{10.0/3/3/3/3/3/3/3/3/3/3 *3*3*3*3*3*3*3*3*3*3}\\
\indent\texttt{10.0 *3*3*3*3*3*3*3*3*3*3 /3/3/3/3/3/3/3/3/3/3}\\
\indent\texttt{1E20 /3/3/3/3/3/3/3/3/3/3 *3*3*3*3*3*3*3*3*3*3}\\
\indent\texttt{1E20 *3*3*3*3*3*3*3*3*3*3 /3/3/3/3/3/3/3/3/3/3}.
\smallskip
\par
\par\noindent\textbf{Exercise 1A.8} Use the function \texttt{computeDouble} to
determine the result of the following expressions: \\
\indent{\texttt{1.0 / 0}\\
\indent{\texttt{-1.0 / 0}\\
\indent{\texttt{0.0 / 0}\\
\indent{\texttt{1 / 0}.
\smallskip
\par

\par\noindent\textbf{Exercise 1A.9} Find out whether the function
\texttt{areaOfDisk} allows the input to be an integer.
\smallskip
\par
\par\noindent\textbf{Exercise 1A.10} Find out what happens if you use
\texttt{int} return type in the function \texttt{areaOfDisk}
instead of \texttt{double}.
\smallskip
\par
\newpage

\section*{Exercise Set 1B: Developing Functions; Function Composition}

\noindent\textbf{Exercise 1B.1} Test the following four functions
with the same set of inputs. Try to predict the outcome. Explain
the differences between the different results.\\
\indent\texttt{c1(f): ((f-32)*5)/9} \\
\indent\texttt{c2(f): (f-32)*(5/9)} \\
\indent\texttt{c3(f): (((f-32)/9)*5)} \\
\indent\texttt{c4(f): (f-32*5/9)}
\smallskip
\par\noindent\textbf{Exercise 1B.2} Develop the function \texttt{fToC} that
converts the temperature given in Fahrenheit to a temperature in
Celsius. In this case represent all temperatures as integers,
which is sufficient for weather reports.
\smallskip
\par
\noindent\textbf{Exercise 1B.3} Develop the function
\texttt{travelTime} that computes how long a car trip takes (in
hours and fractions of an hour), given the distance in miles and
the estimated average speed in miles per hour.
\smallskip
\par
\noindent\textbf{Exercise 1B.4} Develop the function
\texttt{travelTimeInMinutes} that computes how long a car trip
takes (in minutes), given the distance in miles and the estimated
average speed in miles per hour. Use the function
\texttt{travelTime} as a helper function.
\smallskip
\par
\noindent\textbf{Exercise 1B.5} Develop the function
\texttt{numberOfPages} that estimates the number of pages in a
document, given the number of words in the document. Assume that a
page has on the average 60 lines and a line has on the average 15
words in it.
\smallskip
\par
\noindent\textbf{Exercise 1B.6} Develop the function
\texttt{timeToDownload} that estimates the time for downloading an
image file from the web, given the pixel size and the download
speed. The size of the picture is given by the number of pixels in
each row and the number of rows of pixels. The download speed is
given in the number of bytes per second. Each pixel requires three
bytes.
\smallskip
\par
\noindent\textbf{Exercise 1B.7} Develop the function
\texttt{unitPrice} that computes the unit price of a grocery item,
given the weight and price of an item. The weight of the item is
given in pounds and ounces. The price of the item is given in
cents (i.e., for an item that costs \$2.45 the price is given as
the integer value 245).
\smallskip
\par
\noindent\textbf{Exercise 1B.8} Develop the function
\texttt{howManyTiles} that computes how many tiles are needed to
cover the floor during kitchen renovation, given the area of the
kitchen and the size of the tile. The area of the kitchen is given
in square feet. The size of the tile is given in inches. Assume
the tiles are square.
\smallskip
\par
\newpage

\section*{Exercise Set 1C: Functions with Conditionals}

\noindent\textbf{Exercise 1C.1} Develop the function
\texttt{taxRate} that determines the tax rate for a given income
level. If the income is under \$6000, there is no tax. For an
income under \$20000 the tax is 15\%, for income under \$70000 the
tax is 24\%, for \$70000 and over the tax is 33\%.\\
Develop the function \texttt{computeTax} that will compute the
amount of tax for the given income, using the tax rates as
determined earlier.
\smallskip
\par
\noindent\textbf{Exercise 1C.2} Develop the function
\texttt{ticketType} that produces an age label (a \texttt{String})
for a ski ticket, given the age of the skier. The result is
\texttt{"Child"} for those under six years old, \texttt{"Youth"}
for those under twelve, \texttt{"Student"} for those under 21,
\texttt{"Adult"} for those under 65, and \texttt{"Senior"} for
anyone 65 and older.
\smallskip
\par
\noindent\textbf{Exercise 1C.3} Develop the function
\texttt{letterGrade} that consumes the exam score (between 0 and
100) and produces a character representing the earned grade as
follows: 85 and above is A, 70 and above is B, 60 and above is C,
50 and above is D, below 50 is F.
\smallskip
\par
\noindent\textbf{Exercise 1C.4} Develop the function
\texttt{passing} that consumes the exam scores from two exams (a
midterm and a final) and produces a \texttt{Boolean} value that
indicates whether the student passes the course.  Student who
either failed both exams, or got F on one exam and D on the
other, fails the course, otherwise student passes the course.\\
Hint: Use the function \texttt{letterGrade} as a helper.
\smallskip
\par
\noindent\textbf{Exercise 1C.5} Modify the function
\texttt{letterGrade}, so that if the reported score is negative,
or greater than 100, an exception with the message "Score out of
range" is raised.
\smallskip
\par
\noindent\textbf{Exercise 1C.6} Develop the function
\texttt{computeToll} that computes the toll for a vehicle passing
through the toll booth, given information about the vehicle. The
vehicle driver hands in a ticket with one character code as
follows: A is for a passenger car (automobile), B is for bus, T is
for a truck, W is for a car towing a small trailer or a boat or an
airplane (glider in a box). The ticket also has the code that
determines the distance travelled. The toll structure is as
follows. Passenger cars pay \$0.25 per 10 miles of travel, rounded
down, car with a trailer pays \$0.35 per 10 miles. Bus pays \$0.50
per 10 miles and an additional surcharge of \$5 if the distance is
greater than
100 miles. Trucks pay \$0.40 per 10 miles, with a minimum of \$5.\\
Remember the basic guidelines and develop two auxiliary functions
to deal with bus and truck tolls.\\
Your purpose statement must specify clearly the range of
acceptable input values for the vehicle code and the distance
travelled.
\newpage

\section*{Exercise Set 2: Simple Classes}

\noindent\textbf{Exercise 2.1} A class to represent information
about one person.
\begin{itemize}
    \item{Define the member data for the \texttt{Class
Person} that will include the date of birth (year only). Do not
use more than seven attributes.}
    \item{Define the constructor and the \texttt{toString} method
for the \texttt{Class Person}.}
    \item{Develop the purpose and the contract (header) for at least
    three methods for the \texttt{Class Person}.}
    \item{Develop the method isOlderThan that determines whether
    this person is older that a given age.}
    \item{Draw the UML diagram for this class.}
\end{itemize}

\noindent\textbf{Exercise 2.2} A class that represents weather
data for one day.
\begin{itemize}
    \item{Run the code for the tests of the \texttt{Class WeatherData}.}
    \item{Add the code to test the method \texttt{tempPhrase}.}
    \item{Develop the method \texttt{howWet} for the
\texttt{Class WeatherData}. It should return the String
\texttt{"dry"} if the precipitation is below 0.01, \texttt{"wet"},
if the precipitation is below 0.25, \texttt{"soggy"} if the
precipitation is below 1.0 and \texttt{"very wet"} otherwise.}
\end{itemize}
\smallskip
\par
\noindent\textbf{Exercise 2.3} A class that represents
automobiles.
\begin{itemize}
    \item{Design the \texttt{Class Car} that
records the make and model of the car, the fuel tank capacity in
gallons, and the estimated fuel consumption given in miles per
gallon.}
    \item{ Develop the constructor and the \texttt{toString}
    method for this class.}
    \item{Develop the method \texttt{maxDistance}, which computes
    the distance the car can travel on one tank of gas.}
    \item{Develop the method \texttt{canReach}, which determines
whether a destination (distance given in miles) is reachable on
one tank of gas.}
    \item{Develop the method \texttt{goFartherThan},
    which determines whether this car can travel farther on one tank
    of gas than some other given car.}
    \item{Draw the UML diagram for this class.}
\end{itemize}
\smallskip
\par
\noindent\textbf{Exercise 2.4} A class that represents one type of
item in a grocery store (a can of coffee).
\begin{itemize}
    \item{Design the \texttt{Class Coffee} that
represents a coffee can in the grocery store. The relevant
information is the brand name, the weight of the can, given in
ounces, and the price of the can, given in cents.}
    \item{Develop the constructor and the \texttt{toString} method for
this class.}
    \item{Develop the method \texttt{unitPrice}, which computes
the price per ounce of this grocery item.}
    \item{Develop the method \texttt{isCheaperThan}, which determines
    whether the unit price is
lower that some given price.}
    \item{Develop the method \texttt{betterPriceThan} for this class, that
determines whether this coffee is cheaper (in terms of the unit
price) than some other given \texttt{Coffee}.}
    \item{Draw the UML diagram for this class.}
\end{itemize}
\smallskip
\par
\noindent\textbf{Exercise 2.5} Run the existing code for the tests
of the \texttt{Class DayData}. Complete the test suite for the
\texttt{Class DayData}.
\smallskip
\par
\noindent\textbf{Exercise 2.6} A class that represents inventory
information about an item in a grocery store (a can of coffee).
\begin{itemize}
    \item{Design the \texttt{Class InventoryItem} that keeps a record of
the number of specific Coffee items in stock, as well as the
number that has been sold.}
    \item{Develop the constructor and the \texttt{toString} method for this class.}
    \item{Develop the method \texttt{itemValue}, which computes the value of the current stock of
Coffee items.}
    \item{Develop the method \texttt{grossIncome}, which determines
the amount of money received for the Coffee items already sold.}
    \item{Draw the UML diagram for this class.}
\end{itemize}
\smallskip
\par
\noindent\textbf{Exercise 2.7} Continuation of Exercise 2.1.
\begin{itemize}
\item{Define the \texttt{Class Address}, which contains the
information about the city, state, and zip code.}

\item{Modify the \texttt{Class Person}, so that it also contains
person's address. Remember to build the constructor and the
\texttt{toString()} method, and test them.}

\item{Design the method \texttt{getState()} in the \texttt{Class
Address}.}

\item{Design the method \texttt{getState()} in the \texttt{Class
Person}. Remember to follow the \emph{Law of Demeter}.}
\end{itemize}
\smallskip
\par
\newpage

\section*{Exercise Set 3: Simple Class Hierarchy}

\noindent\textbf{Exercise 3.1} Given a class hierarchy to
represent information about people at a university, including the
classes \texttt{Person}, \texttt{Instructor}, and \texttt{Staff}:
\begin{itemize}
\item{design \texttt{class Student} to be a new subclass of the
\texttt{Class Person}. It should contain information about the
student's GPA and major.} \item{Develop the method
\texttt{withHonors}, which determines whether the student's GPA is
greater than 3.5} \item{Complete the test suite for this
collection of classes.} \item{Complete the UML diagram for this
collection of classes.}
\end{itemize}
\smallskip
\begin{center}
\resizebox{\textwidth}{!} {\includegraphics{PersonItems.eps}}
\end{center}
\smallskip
\par
\noindent\textbf{Exercise 3.2} Given a UML class hierarchy to
represent items in the grocery store, develop the classes
\texttt{Grocery}, \texttt{Coffee}, \texttt{Juice}, and
\texttt{IceCream} as specified in the UML diagram.
\smallskip
\begin{center}
\resizebox{\textwidth}{!} {\includegraphics{GroceryItemsOld.eps}}
\end{center}
\smallskip
\par \noindent\textbf{Exercise 3.3} Develop a class
hierarchy to represent three different types of vehicles: cars,
trucks, and buses. For all vehicles we need to record the size of
the fuel tank in gallons, and the estimated fuel consumption given
in miles per gallon. Just like the \texttt{class Car} in an
earlier exercise, we can compute: \begin{itemize} \item{the
maximum distance the vehicle can travel on one tank of fuel}
\item{whether it can travel a given distance} \item{whether it can
travel farther than some other vehicle.}
\end{itemize}
\smallskip
\noindent\textbf{Exercise 3.4} \emph{Warning:} This exercise can
be completed independently of the previous exercise.\\Develop a
class hierarchy to represent three different types of vehicles:
cars, trucks, and buses. Different kinds of vehicles need to
represent additional information as follows:
\begin{itemize}
\item{A car may or may not pull a trailer.} \item{A bus can carry
some number of passengers (capacity) and has some number of
passengers on board.} \item{A truck has some specified maximum
load and some current load.}
\end{itemize}
Develop the method \texttt{computeToll}, which will compute the
toll for each vehicle according to the following rules:
\begin{itemize}
\item{A car without a trailer pays \$0.25 per mile.} \item{A car
towing a trailer pays \$0.35 per mile.} \item{A bus pays \$0.35
per mile and additional \$0.20 for each passenger.} \item{A truck
pays \$0.40 per mile and in addition \$0.05 for each 1000 lb of
load it currently carries.}
\end{itemize}
\smallskip
\par
\noindent\textbf{Exercise 3.5} \begin{itemize} \item{Create a
class to represent the address of some person. Address should
include the street, the city, the state and the zip code.}
\item{Extend the class hierarchy from Exercise 3.1, so that it
records the address for each kind of person (\texttt{Person},
\texttt{Instructor}, \texttt{Staff}).} \item{Develop the method
\texttt{thisZip}, which determines whether this person lives in a
given zip code.} \item{Draw the UML diagram for this collection of
classes.}
\end{itemize}
\smallskip
\par
\noindent\textbf{Exercise 3.6} \begin{itemize} \item{Modify the
\texttt{class InventoryItem }from Exercise 2.6 to represent the
inventory information about any grocery item in the class
hierarchy from Exercise 3.2.} \item{Draw the UML diagram for this
collection of classes.} \item{Explain briefly how the method
\texttt{grossIncome} performs the calculations.} \item{Explain
briefly how the method \texttt{betterPriceThan} performs the
calculation, when we choose to compare a \texttt{Coffee} item with
an \texttt{IceCream} item.} \end{itemize}

\smallskip
\par
\newpage

\section*{Exercise Set 4: Self Referential Class Hierarchies}

\noindent\textbf{Exercise 4.1} Given the shopping list of
groceries and the UML diagram (Figure 4.1), develop the following
methods:
\begin{itemize} \item{\texttt{isInList}, which determines whether a
given item is already on the list;} \item{\texttt{countItems},
which counts how many items are on the shopping
list;}\item{\texttt{removeFromList}, which produces a new list
with the given item removed;}\item{\texttt{addToList}, which adds
a new item to the shopping list.}
\end{itemize}
\smallskip
\par
\noindent\textbf{Exercise 4.2} Develop the collection of classes
for representing a list of actors in a cast. We assume, each actor
is listed only once. It is sufficient to just record actor's full
name as one \texttt{String}: the last name followed by the first
name.\begin{itemize}\item{Develop the method \texttt{isInCast},
which determines whether some actor is in the cast.}\item{Develop
the method \texttt{castSize}, which determines how many actors are
in the cast.}\item{Develop the method \texttt{sortList}, which
return a sorted list of actors.}\item{Develop the method
\texttt{sortedIsInCast}, which determines whether some actor is in
the cast, and takes advantage of the fact that the list is already
sorted.}\end{itemize}
\smallskip
\par
\noindent\textbf{Exercise 4.3} The playbill is a list of
actor-role pairs, each actor and each role can be represented as
one \texttt{String}. Every actor plays only one
role.\begin{itemize}

\item{Design the class \texttt{Role}, which represents one role
and includes the title of the role (a \texttt{String}) and the
actor of this role (a \texttt{String}).}

\item{Develop the collection of classes
 to represent a playbill for a play.}

\item{Develop the method \texttt{whosePart}, which determines the
name of the actor playing the given role. If the role is not in
the list, the method should return the String "" (a non-empty
string of length 0).}

\item{Develop the method \texttt{whatPart}, which determines the
role played by a given actor. If the actor is not in the list, the
method should return the String "" (a non-empty string of length
0).}

\item{Develop the method \texttt{substitute}. The method consumes
an actor and a role. It produces a new playbill where the actor
for the given role is replaced by the given actor. If the given
role does not appear in the playbill, the playbill is
unchanged.}\end{itemize}
\newpage
\begin{center}
\textbf{Figure 4.1}\\
\resizebox{\textwidth}{!} {\includegraphics{GroceryItems.eps}}
\end{center}

\newpage
\noindent\textbf{Exercise 4.4} The course information in the
registrar's database contains the course number (four digits), the
course title, and the number of credits.
\begin{itemize}
\item{Develop the classes to represent a list of
courses.}
\item{Develop the method \texttt{departmentList}, which
produces a list of all courses offered in the given department. A
department is identified by the first two digits of the course
number.}
\item{Develop the method \texttt{credits}, which
determines the number of credits student earns in a given course.}
\end{itemize}
\smallskip
\par
\noindent\textbf{Exercise 4.5} The grocery store keeps the
inventory as a list of lists of grocery items of different kind
(\texttt{Coffee}, \texttt{IceCream}, \texttt{Juice} - see an
earlier exercise).
\begin{itemize}

\item{Develop the classes to represent the inventory for this
grocery store.}

\item{Develop the method \texttt{grossIncome}, which computes the
gross income from all products in the inventory.}

\item{Develop the method \texttt{incomeForBrand}, which determines
the gross income for a given brand of products, given the
\texttt{class} name for the products.}

\item{Draw the UML diagram for this collection of
classes.}\end{itemize}

\smallskip
\par
\newpage

\section*{Exercise Set 5: Trees}
\noindent\textbf{Exercise 5.1} A river is defined by the cities at
the places where two tributaries join together, or at the river
source. If we want to study river traffic or river pollution, we
may select the following representation of the river:\\
\indent \texttt{City} is a structure, which consists of
\begin{itemize}

\item{\texttt{name}}

\item{\texttt{location} represented as double x-y coordinates}

\item{\texttt{data} - an object in the class \texttt{Data}, which
we can define as we wish, to study various problems related to
this river, such as pollution, fish population, navigability}
\end{itemize}

\texttt{ARiver} is
\begin{itemize}
\item{either a \texttt{Port}, which contains just one member data
field - a \texttt{City}}

\item{or a \texttt{Tributary}}
\end{itemize}

\texttt{Tributary} is a structure, which consists of
\begin{itemize}
\item{\texttt{Port}}

\item{\texttt{ARiver leftTributary}}

\item{\texttt{ARiver rightTributary}}
\end{itemize}
For this assignments perform the following tasks:
\begin{enumerate}
\item{Design the class hierarchy corresponding to the above data
definition. Make class \emph{stubs} with data definitions,
constructors, and \texttt{toString()} methods. Make sure you test
these.}

\item{Draw UML diagram for this class hierarchy}

\item{Test your code by drawing the river using the given
\texttt{RiverDisplay} class.}

\item{Write the method \texttt{navLength()}, which computes the
total length of all tributaries for this river.}

\item{Write the method \texttt{findCity()}, which determines
whether the city with the given name is a port on this river.}

\item{Write the method \texttt{riverLength()}, which determines
the length of this river (that means the longest distance from the
source to the river end).}

\item{\emph{Optional}: Add a field to measure the volume of
pollution that flows into the river from each city. Define the
formula to measure the pollution in the river, which is based on
the length of the river segment and the total volume of
pollutants. Write the method to compute the pollution for the
river.}

\end{enumerate}
\smallskip
\par
\noindent\textbf{Exercise 5.2} A town soccer team has a phone tree
to notify players about game cancellations and other changes in
the schedule. Each player is assigned to call at most two other
players.
\begin{itemize}
\item{Develop the classes to represent the phone tree, where the
player information consists of player's name and phone number.}

\item{Develop the method \texttt{countPlayers}, which counts how
many players are in the phone tree.}

\item{Develop the method \texttt{isInTree}, which determines
whether a player with the given name is in this tree.}

\item{Develop the method \texttt{phoneNumber}, which returns the
phone number of a given player, or returns 0 if the player is not
found in the tree.}

\item{Develop the method \texttt{myPhoneTree}, which returns the
phone subtree starting with the given player. If the player is not
found, it should return the empty tree.}

\item{Develop the method \texttt{checkList}, which determines
whether every player in a given list of players also appears in
the given phone tree.}
\end{itemize}
\smallskip
\par
\noindent\textbf{Exercise 5.3} Design the \texttt{class Item}that
contains some integer-valued \emph{attribute} that defines an
ordering of Item objects. For example, an item may be a book (with
price), a CD (with number of tracks), a circle (with area), an
animal (with weight)
\begin{itemize}

\item{Develop the classes to represent a binary search tree of
\texttt{Item}s.}

\item{Develop the method \texttt{insert}, which inserts a new
\texttt{Item} into the BST.}

\item{Develop the method \texttt{inBST}, which determines whether
an  \texttt{Item} with the given \emph{attribute} appears in the
BST.}

\item{Develop the method \texttt{find}, which produces the
\texttt{ConsBST}, which has the \texttt{Item} with the given
\emph{attribute} as its root, or it produces an \texttt{EmptyBST}
object if the \texttt{Item} is not found.}

\end{itemize}

\newpage
\section*{Exercise Set 6: Interfaces}

\noindent\textbf{Exercise 6.1} The given UML diagram describes
classes that define a list of measurable objects with a sample
method \texttt{totalSize} and a sample \texttt{class MString} on
which the list is tested.
\begin{itemize}\item{Develop the method \texttt{minItem}, which returns the
minimum (\texttt{IMeasurable}) item in the list, as determined by
the \texttt{size()} method. Test the \texttt{minItem} method using
the \texttt{class MString}} \item{Develop the method
\texttt{sortList}, which implements the insertion sort on the
list.}\end{itemize}
\smallskip
\begin{center}\resizebox{\textwidth}{!}
{\includegraphics{ClassHierarchy.eps}}
\end{center}

\noindent\textbf{Exercise 6.2} The Java \texttt{Comparable}
\texttt{interface} is designed to support uniform comparison of
objects.
\begin{itemize} \item{Develop a new collection of classes
 \texttt{CompList, EmptyCompList, ConsComp} that define a list of
 \texttt{Comparable} objects. \item{Develop the method \texttt{minItem}, which returns the
minimum (\texttt{Comparable}) item in the list, as determined by
the \texttt{compareTo()} method. Test the \texttt{minItem} method
using the \texttt{class String}} \item{Develop the method
\texttt{sortList}, which implements the insertion sort on the
list.} Use the \texttt{class String} to test your
code.}\item{Develop the \texttt{class CompString}, which is based
on the Java \texttt{class String}, but re-implements the
\texttt{Comparable interface} so that it compares \texttt{String}s
by their length. Test your implementation of the \texttt{CompList}
using the \texttt{Class CompString}.}\item{Draw the UML diagram of
this collection of classes.}\end{itemize}
\smallskip
\par
\noindent\textbf{Exercise 6.3} Develop further tests and uses of
the list of \texttt{Comparable} objects from the previous
exercise. Develop the \texttt{class CompRectangle} which extends
the Java \texttt{class Rectangle} by implementing the
\texttt{Comparable interface}. The comparison is based on the area
of the rectangle. Test the \texttt{class CompList} using the
\texttt{class CompRectangle}. Draw the UML diagram of this
collection of classes.
\smallskip
\par
\newpage

\section*{Exercise Set 7: Complex Class Hierarchies}

\noindent\textbf{Exercise 7.1} Given a UML diagram to represent
the descendant tree, and the code that implements the method which
counts the number of people in the descendant tree, develop the
following methods:
\begin{itemize}
\item \texttt{blueEyes}, which determines whether there is a
person with blue eyes in the descendant tree.

\item \texttt{countBlueEyes}, which count the number of persons
with blue eyes in the descendant tree.

\item{\texttt{find}, which produces the year of birth for a person
with the given name, or \texttt{0}, if no person in the tree has
this name.}

\item{\texttt{children}, which produces a list of children for a
person with the given name, or an empty list of children, if a
person with this name is not in the tree.}
\end{itemize}
Add the missing templates to all classes and continue to develop
the templates as you work on this problem. Add one more generation
(at least three grandchildren) to the test cases.
\smallskip
\begin{center}\resizebox{\textwidth}{!}
{\includegraphics{DescendantTree.eps}}
\end{center}

\newpage

\noindent\textbf{Exercise 7.2} A GUI \texttt{Component} is one of
the
following:\begin{itemize}\item{BooleanView}\item{TextFieldView}
\item{OptionsView}\item{ColorView}\item{Table}\end{itemize} Each
component contains a label and some additional data.\\The data for
a \texttt{Table} is one of \begin{itemize}\item{empty}\item{list
of \texttt{Row}s}\end{itemize}A \texttt{Row} is one of
\begin{itemize}\item{empty}\item{list of \texttt{Component}s}\end{itemize}
Data for each of the remaining components is the default value to
be displayed, specified as a \texttt{String}, and the preferred
width and height.\begin{itemize}\item{Draw the UML diagram for
this collection of classes.}\item{Develop the templates for
methods needed to count the number of primitive GUI elements in a
given GUI \texttt{Component}.}\item{Develop the templates for the
methods needed to determines the height of a given GUI
\texttt{Component}. The height of the table is the sum of the
heights of the \texttt{Row}s. The height of a \texttt{Row} is the
maximum size of components in the list of
\texttt{Component}s.}\end{itemize} Note: Do not write the code!!!
\smallskip
\par
\newpage
\noindent\textbf{Exercise 7.3} A \texttt{WebPage} consists of a
\begin{itemize}\item{\texttt{String header},}\item{and a \texttt{Body b}.}\end{itemize}
A \texttt{Body} is a list of \texttt{HTML} elements.\\A
\texttt{HTML} element is either\begin{itemize}\item{a
\texttt{String word}}\item{or a \texttt{Link}.}\end{itemize}A
\texttt{Link} consists of
\begin{itemize}\item{a \texttt{String
word}}\item{and a \texttt{WebPage}.}\end{itemize}
\smallskip
\noindent Perform the following tasks:
\begin{itemize}\item{Draw
the UML diagram for the collection of classes that represent web
pages.}\item{Develop the classes.}\item{Develop the method
\texttt{allWords}, which produces a list of all words in the web
page}\item{Develop the method \texttt{pages}, which produces the
list of \emph{immediate} words on a page. That is, it consumes a
\texttt{WebPage} and produces a list of \texttt{String}. An
\texttt{immediate} word on a list of \texttt{HTML} elements is
defined as follows:
\begin{itemize}\item{an \texttt{HTML} element that is a \texttt{word}
is the \emph{immediate} word} \item{for an \texttt{HTML} element
that is a \texttt{Link}, the method extracts the \texttt{word}
from the \texttt{Link}.}\end{itemize}}\item{Develop the method
\texttt{occurs}, which determines whether the given \texttt{word}
occurs in the web page or its embedded pages.}
\end{itemize}

\smallskip
\par
\newpage

\section*{Exercise Set 8: Anonymous Inner Classes (Lambda)}
\noindent\textbf{Exercise 8.1} The given code implements a list of
\texttt{String}s with four methods: \texttt{count} which counts
the number of items in the list, using the \emph{traditional}
technique; \texttt{mapStringToString} and
\texttt{mapStringToBool}, each of which creates a new list by
applying the specified method to every item in the original list;
and \texttt{orMapString} which returns true if one of the list
items satisfied the given predicates. The last three methods take
as argument an object which implements one of the two
\emph{functional} interfaces. The examples in the test suite
illustrate the implementation which uses the anonymous inner
classes.

\begin{itemize}
\item{In the test suite develop the test which consumes a list of
\texttt{String} and produces a new list of \texttt{String}s in
which each \texttt{String} has been converted to all upper case
letters.}

\item{In the test suite develop the test which consumes a list of
\texttt{String}s and determines whether a given \texttt{String} is
one of the items in this list.}

\item{Develop a new method \texttt{andMap} in the class
\texttt{AListStrings} and its variants. The method will take as
argument an object which implements the \texttt{Obj2Boolean}
\texttt{interface} and returns \texttt{true} if every item in the
list satisfies the predicate defined in the class which implements
this interface.\\Hint: Think of Scheme \emph{andmap}.}

\item{Develop two tests for this method - selecting the predicates
on your own. Make sure you explain clearly the purpose of your
test!}
\end{itemize}
\smallskip
\par
\noindent\textbf{Exercise 8.2} The given example sorts the list of
Persons by their full names, first names, and by the year of
birth, using the anonymous inner classes to implement the desired
Comparator interface.\\Using the same technique, first develop a
list of CDs, where each CD has a title, artist name and the number
of tracks. Implement three different ways of sorting this list: by
titles, by artists, and by the number of tracks.
\smallskip
\par
\newpage

\section*{Exercise Set 9: Loops with Iterators}
\noindent\textbf{Exercise 9.1} Study the given \texttt{IRange
interface} for an iterator and its use with the list of
\texttt{Student}. An example shows how to use the iterator to find
whether a student with the given name is in the list and how to
print all items in the list.
\begin{itemize}
\item{Draw the UML diagram of this collection of classes.}

\item{Develop another example of the use of this iterator to
determine whether a student with gpa greater than 3.5 is in the
list.}

\item{Use a similar technique to design a method in the test
suite, which computes the best gpa of all \texttt{Students} in
this list.}

\item{Use a similar technique to design a method in the test
suite, which counts the number of students in this list.}

\item{Use a similar technique to design a method in the test
suite, which computes the average gpa of all students in this
list.}
\end{itemize}
\smallskip
\par
\noindent\textbf{Exercise 9.2} The given code defines also an
\texttt{ArrayRange} iterator and a \texttt{TreeRange} iterator for
binary trees. Use the \texttt{ArrayRange} iterator and the
\texttt{TreeRange} iterator to perform the same tasks as in the
previous example.
\smallskip
\par
\noindent\textbf{Exercise 9.3} The given code defines a binary
search tree of \texttt{Integer}s (BST), and an iterator which
implements \texttt{IRange} to traverse the tree in \emph{inorder}.
\begin{itemize}
\item{Develop a test suite that tests the iterator on a BST with
at least 7 nodes.}

\item{Design and test a \texttt{ReverseTreeRange} iterator which
traverses the BST in \textbf{\emph{reverse inorder}}.}
\end{itemize}
\smallskip
\par
\noindent\textbf{Exercise 9.4} Design the class \texttt{DataSet}
which has as its member data a data collection of
\texttt{Comparable} objects, such as list of \texttt{Integer}s, or
an array of \texttt{String}s, and a corresponding iterator. Design
the following methods in this class:
\begin{itemize}
\item{\texttt{findItem} method, which determines whether a given
object appears in the data collection}

\item{\texttt{count} method, which counts the number of items in
the collection}

\item{\texttt{minimum} method, which returns the minimum item in
the collection. The method may assume that it will only be invoked
by with a non-empty collection.}
\end{itemize}

\smallskip

\noindent Make sure you develop the tests for these methods that
use at least two different data collection and their corresponding
iterators.
\smallskip
\par
\noindent\textbf{Exercise 9.5} (Will be avilable later.) Use the
given \texttt{IRange interface} and its \texttt{FileRange}
implementation to perform the following tasks:
\begin{itemize}
\item{Develop the classes to represent a Binary Search Tree
(\texttt{BST})of arbitrary \texttt{Comparable} objects.}
\item{Develop the method which reads the data from a file using
the \texttt{FileRange} iterator and builds a \texttt{BST}. Test
your result using the code from previous exercises.}
\end{itemize}
\smallskip
\par
\newpage

\section*{Exercise Set 10: Loops with Counters}
\noindent\textbf{Exercise 10.1} Design the class ArrayAlgorithms.
Its member data is an array on Comparable objects. Develop the
following methods for this class:
\begin{itemize}
\item{\texttt{find} method which determines whether a given object
is one of the elements of this array.}

\item{\texttt{findMinLocation} method which returns the index for
the smallest item in this array.}

\item{\texttt{floor} method which consumes another array of the
same size and returns a new array of the same size in which each
element is the smaller of the two corresponding elements in the
original arrays.}

\item{\texttt{filter} method which consumes a Comparable data item
and produces a new array which contains only those items from the
original array that are smaller that the given item.}

\item{\texttt{sort} method which consumes an array of Comparable
data items and produces a new array which contains the same
elements, but sorted in ascending order.}
\end{itemize}
Write the tests for these methods in the test suite.

\noindent Test your code on arrays of \texttt{String}s and arrays
of \texttt{Integer}s.
\smallskip
\par
\noindent\textbf{Exercise 10.2} The given code specifies a
\texttt{Double2Double} \texttt{interface} and a \texttt{Plot}
\texttt{class}. The constructor for the \texttt{Plot} class
consumes \texttt{Rectangle2D} object which specifies the region
for the display of the function graph. The \texttt{Plot} class
also includes the methods \texttt{plotAxes()} which plots the axes
for the graph, and \texttt{plotValue(double x, double y)} which
plots the value \texttt{y} for the point \texttt{x}.
\par
\noindent Write the class \texttt{FunctionPlot} as follows. The
member data specify the function to plot - an object in the class
which implements the \texttt{Double2Double interface}. Develop the
following methods in the class \texttt{FunctionPlot}:
\begin{itemize}
\item{\texttt{minimum} method which consumes the \texttt{double}
values \texttt{x1} and \texttt{x2} - the two ends of the interval
on which the function should be plotted and an \texttt{int} value
\texttt{n} which specifies the number of points to plot and
returns the minimum value of this function among the \texttt{n}
points.}

\item{\texttt{maximum} method which consumes the \texttt{double}
values \texttt{x1} and \texttt{x2} - the two ends of the interval
on which the function should be plotted and an \texttt{int} value
\texttt{n} which specifies the number of points to plot and
returns the maximum value of this function among the \texttt{n}
points.}

\item{\texttt{plotFunction} method which consumes the
\texttt{double} values \texttt{x1} and \texttt{x2} - the two ends
of the interval on which the function should be plotted and an
\texttt{int} value \texttt{n} which specifies the number of points
to plot. The function returns \texttt{void}, but displays the
graph with axes in the graphics window.}

\end{itemize}
\smallskip
\par
\noindent\textbf{Exercise 10.3} This is an independent
continuation of the previous exercise. Develop the method
\texttt{integral} which for the given (\texttt{double}) interval
\texttt{(x1, x2)} computes the value of the integral of this
function, approximated to the value of a given \texttt{epsilon}.

\newpage
\section*{Exercise Set 11: The Meaning of Equality}
\noindent\textbf{Exercise 11.1} Create a class \texttt{Person}:
with name, eyecolor, date of birth, and address. Create a class
\texttt{Address} with city and zip code only.
\begin{itemize}
\item{Define three a \texttt{Address} objects and four
\texttt{Person} objects. Design examples to illustrate the problem
with assignment and mutation. Write comments explaining the
problem.}

\item{Define a shallow copy constructor for the class
\texttt{Person} and show on examples when it fails.}

\item{Define a \texttt{copy} method in the class \texttt{Person},
which returns a new copy of the given object. Design and run test
that verify that your code works properly.}

\item{Define the method \texttt{equals}, which compares two person
objects and returns true if the two people have the same name,
eyecolor, date of birth, city, and zip, even if they are not
represented by the same object. Design tests to verify that your
method works correctly.}
\end{itemize}


\smallskip
\par
\noindent\textbf{Exercise 11.2} Start with an array of Person.
Experiment with making copies of the array, modifying people in
the first array, observe what happens in both. First make the copy
by assignment, then using the incorrect copy constructor, then
using the copy method developed in the previous exercise.


\newpage
\section*{Exercise Set 12: Assignment for Primitive Types}
\noindent\textbf{Exercise 12.1} Create a table which displays the
values of the variables x and y after each of the following
statements, assuming the statements are executed in the order
shown.\smallskip\noindent\begin{itemize} \item(a){\begin{verbatim}
    x = 40;              // line 1
    y = 55;              // line 2
    x = y;               // line 3
    /** -------------------------------------- */
\end{verbatim}}
\item(b){\begin{verbatim}
    x = 25;              // line 1
    y = 40;              // line 2
    x = x + 20;          // line 3
    y = x - 10;          // line 4
    /** -------------------------------------- */
\end{verbatim}}
\item(c){\begin{verbatim}
    x = 25;              // line 1
    y = 40;              // line 2
    y = x - 10;          // line 3
    x = x + 20;          // line 4
    /** -------------------------------------- */
\end{verbatim}}
\item(d){\begin{verbatim}
    x = 15;              // line 1
    y = 20;              // line 2
    x = x + y;           // line 3
    /** -------------------------------------- */
\end{verbatim}}
\item(e){\begin{verbatim}
    x = 55;              // line 1
    y = 99;              // line 2
    x = x + y;           // line 3
    y = x - y;           // line 4
    x = x - y;           // line 5
    /** -------------------------------------- */
\end{verbatim}}
\end{itemize}



\end{document}
