Programming Exercises for Chapter 10
This page contains several exercises for Chapter 10 in Introduction to Programming Using Java. For each exercise, a link to a possible solution is provided. Each solution includes a discussion of how a programmer might approach the problem and interesting points raised by the problem or its solution, as well as complete source code of the solution.
Exercise 10.1:
Rewrite the PhoneDirectory class from Subsection 7.4.2 so that it uses a TreeMap to store directory entries, instead of an array. (Doing this was suggested in Subsection 10.3.1.) You should also write a short program to test the class.
Exercise 10.2:
In mathematics, several operations are defined on sets. The union of two sets A and B is a set that contains all the elements that are in A together with all the elements that are in B. The intersection of A and B is the set that contains elements that are in both A and B. The difference of A and B is the set that contains all the elements of A except for those elements that are also in B.
Suppose that A and B are variables of type set in Java. The mathematical operations on A and B can be computed using methods from the Set interface. In particular: A.addAll(B) computes the union of A and B; A.retainAll(B) computes the intersection of A and B; and A.removeAll(B) computes the difference of A and B. (These operations change the contents of the set A, while the mathematical operations create a new set without changing A, but that difference is not relevant to this exercise.)
For this exercise, you should write a program that can be used as a "set calculator" for simple operations on sets of non-negative integers. (Negative integers are not allowed.) For input and output, a set of such integers will be written as a list of integers, separated by commas and, optionally, spaces and enclosed in square brackets. For example: [1,2,3] or [17, 42, 9, 53, 108]. The characters +, *, and - will be used for the union, intersection, and difference operations. The user of the program will type in lines of input containing two sets, separated by an operator. The program should perform the operation and print the resulting set. Here are some examples:
Input Output
------------------------- -------------------
[1, 2, 3] + [3, 5, 7] [1, 2, 3, 5, 7]
[10,9,8,7] * [2,4,6,8] [8]
[ 5, 10, 15, 20 ] - [ 0, 10, 20 ] [5, 15]
To represent sets of non-negative integers, use sets of type TreeSet<Integer>. Read the user's input, create two TreeSets, and use the appropriate TreeSet method to perform the requested operation on the two sets. Your program should be able to read and process any number of lines of input. If a line contains a syntax error, your program should not crash. It should report the error and move on to the next line of input. (Note: To print out a Set, A, of Integers, you can just say System.out.print(A). I've chosen the syntax for sets to be the same as that used by the system for outputting a set.)
Exercise 10.3:
The fact that Java has a HashMap class means that no Java programmer has to write an implementation of hash tables from scratch—unless, of course, that programmer is a computer science student.
For this exercise, you should write a hash table in which both the keys and the values are of type String. (This is not an exercise in generic programming; do not try to write a generic class.) Write an implementation of hash tables from scratch. Define the following methods: get(key), put(key,value), remove(key), containsKey(key), and size(). Remember that every object, obj, has a method obj.hashCode() that can be used for computing a hash code for the object, so at least you don't have to define your own hash function. Do not use any of Java's built-in generic types; create your own linked lists using nodes as covered in Subsection 9.2.2. However, you are not required to increase the size of the table when it becomes too full.
You should also write a short program to test your solution.
Exercise 10.4:
A predicate is a boolean-valued function with one parameter. Java has the parameterized functional interface Predicate<T>, from package java.util.function, to represent predicates. The definition of Predicate<T> could be:
public interface Predicate<T> {
public boolean test( T obj );
}
The idea is that an object that implements this interface knows how to "test" objects of type T in some way. Java already has some methods that use predicates, such as the removeIf(p) method that is defined for any Collection. (See Subsection 10.6.1). However, this exercise asks you to write a few similar methods yourself. Define a class that contains the following generic static methods for working with predicate objects. The name of the class should be Predicates, in analogy with the standard class Collections that provides various static methods for working with collections. You should not use the stream API for this exercise.
public static <T> void remove(Collection<T> coll, Predicate<T> pred) // Remove every object, obj, from coll for which pred.test(obj) // is true. (This does the same thing as coll.removeIf(pred).) public static <T> void retain(Collection<T> coll, Predicate<T> pred) // Remove every object, obj, from coll for which // pred.test(obj) is false. (That is, retain the // objects for which the predicate is true.) public static <T> List<T> collect(Collection<T> coll, Predicate<T> pred) // Return a List that contains all the objects, obj, // from the collection, coll, such that pred.test(obj) // is true. public static <T> int find(ArrayList<T> list, Predicate<T> pred) // Return the index of the first item in list // for which the predicate is true, if any. // If there is no such item, return -1.
Exercise 10.5:
This is a short exercise in using the stream API. Suppose that the class Score is defined as
class ScoreInfo {
String firstName;
String lastName;
int score;
ScoreInfo( String lName, String fName, int s ) {
firstName = fName;
lastName = lName;
score = s;
}
}
and that scoreData is an array of ScoreInfos containing information about the scores of students on a test. Use the stream API to do each of the following tasks:
- print the number of students (without using scoreData.length)
- print the average score for all of the students
- print the number of students who got an A (score greater than or equal to 90)
- use the collect() stream operation to create a List<String> that contains the names of students whose score was less than 70; the names should be in the form first name followed by last name
- print the names from the List that was generated in the previous task
- print out the student's names and scores, ordered last name
- print out the student's names and scores, ordered by score
You can put all of the code in main() routine and include ScoreInfo as a static nested class. Do not use any for loops or other control structures. Do everything using the stream API. For testing your code, you can use this array:
private static ScoreInfo[] scoreData = new ScoreInfo[] {
new ScoreInfo("Smith","John",70),
new ScoreInfo("Doe","Mary",85),
new ScoreInfo("Page","Alice",82),
new ScoreInfo("Cooper","Jill",97),
new ScoreInfo("Flintstone","Fred",66),
new ScoreInfo("Rubble","Barney",80),
new ScoreInfo("Smith","Judy",48),
new ScoreInfo("Dean","James",90),
new ScoreInfo("Russ","Joe",55),
new ScoreInfo("Wolfe","Bill",73),
new ScoreInfo("Dart","Mary",54),
new ScoreInfo("Rogers","Chris",78),
new ScoreInfo("Toole","Pat",51),
new ScoreInfo("Khan","Omar",93),
new ScoreInfo("Smith","Ann",95)
};
Exercise 10.6:
An example in Subsection 10.4.2 concerns the problem of making an index for a book. A related problem is making a concordance for a document. A concordance lists every word that occurs in the document, and for each word it gives the line number of every line in the document where the word occurs. All the subroutines for creating an index that were presented in Subsection 10.4.2 can also be used to create a concordance. The only real difference is that the integers in a concordance are line numbers rather than page numbers.
Write a program that can create a concordance. The document should be read from an input file, and the concordance data should be written to an output file. You can use the indexing subroutines from Subsection 10.4.2, modified to write the data to TextIO instead of to System.out. (You will need to make these subroutines static.) The input and output files should be selected by the user when the program is run. The sample program WordCount.java, from Subsection 10.4.4, can be used as a model of how to use files. That program also has a useful subroutine that reads one word from input.
As you read the file, you want to take each word that you encounter and add it to the concordance along with the current line number. Keeping track of the line numbers is one of the trickiest parts of the problem. In an input file, the end of each line in the file is marked by the newline character, '\n'. Every time you encounter this character, you have to add one to the line number. WordCount.java ignores ends of lines. Because you need to find and count the end-of-line characters, your program cannot process the input file in exactly the same way as does WordCount.java. Also, you will need to detect the end of the file. The function TextIO.peek(), which is used to look ahead at the next character in the input, returns the value TextIO.EOF at end-of-file, after all the characters in the file have been read.
Because it is so common, don't include the word "the" in your concordance. Also, do not include words that have length less than 3.
Exercise 10.7:
The sample program SimpleInterpreter.java from Subsection 10.4.1 can carry out commands of the form "let variable = expression" or "print expression". That program can handle expressions that contain variables, numbers, operators, and parentheses. Extend the program so that it can also handle the standard mathematical functions sin, cos, tan, abs, sqrt, and log. For example, the program should be able to evaluate an expression such as sin(3*x-7)+log(sqrt(y)), assuming that the variables x and y have been given values. Note that the name of a function must be followed by an expression that is enclosed in parentheses.
In the original program, a symbol table holds a value for each variable that has been defined. In your program, you should add another type of symbol to the table to represent standard functions. You can use the following nested enumerated type and class for this purpose:
private enum Functions { SIN, COS, TAN, ABS, SQRT, LOG }
/**
* An object of this class represents one of the standard functions.
*/
private static class StandardFunction {
/**
* Tells which function this is.
*/
Functions functionCode;
/**
* Constructor creates an object to represent one of
* the standard functions
* @param code which function is represented.
*/
StandardFunction(Functions code) {
functionCode = code;
}
/**
* Finds the value of this function for the specified
* parameter value, x.
*/
double evaluate(double x) {
switch(functionCode) {
case SIN:
return Math.sin(x);
case COS:
return Math.cos(x);
case TAN:
return Math.tan(x);
case ABS:
return Math.abs(x);
case SQRT:
return Math.sqrt(x);
default:
return Math.log(x);
}
}
} // end class StandardFunction
Add a symbol to the symbol table to represent each function. The key is the name of the function and the value is an object of type StandardFunction that represents the function. For example:
symbolTable.put("sin", new StandardFunction(Function.SIN));
In SimpleInterpreter.java, the symbol table is a map of type HashMap<String,Double>. It's not legal to use a StandardFunction as the value in such a map, so you will have to change the type of the map. The map has to hold two different types of objects. The easy way to make this possible is to create a map of type HashMap<String,Object>. (A better way is to create a general type to represent objects that can be values in the symbol table, and to define two subclasses of that class, one to represent variables and one to represent standard functions, but for this exercise, you should do it the easy way.)
In your parser, when you encounter a word, you have to be able to tell whether it's a variable or a standard function. Look up the word in the symbol table. If the associated object is non-null and is of type Double, then the word is a variable. If it is of type StandardFunction, then the word is a function. Remember that you can test the type of an object using the instanceof operator. For example: if (obj instanceof Double).