## Homework Assignment 6

MCS-178: Introduction to Computer Science II
Max Hailperin, Spring 2003; Due: May 9

Remember: You are encouraged to turn in individual problems as soon as possible, rather than turning in the whole assignment on the due date. Please mark each problem with the exercise number from the book, or the exercise number indicated below, for any problem that is not from the book.

• Exercise 14.x1: Draw a UML diagram containing the following information:
There are two basic kinds of objects: procedures and ASTs. ASTs can be constants or applications. Each application is associated with one or more ASTs known as its children; it is their parent. Not every AST needs to have a parent, but those that do only have one. The association between a parent and its children is navigable only from parent to child. There is also a one-way association from each procedure to a parentless AST. Each AST is associated in this way with any number of procedures (including zero).

• Do exercise 14.40 on pages 571-572.

• Exercise 15.x1: Add the method `countExpensiveItems` to the `ItemList` class in the Java version of CompuDuds. This method takes a single argument, which is the maximum price we are willing to consider "inexpensive." The method's job is to return as its value the count of how many expensive Items are in the ItemList. For example, suppose we display our ItemList and it is as follows:
```1) Charcoal chinos, size 32, hemmed to 32 inches; \$33.00
2) Ecru Oxford shirt, size 16/32; \$19.50
3) Khaki chinos, size 32, hemmed to 29 inches; \$33.00
4) Blue Oxford shirt, size 16/32; \$19.50
Total: \$105.00
```
If we now invoke `countExpensiveItems(1950)` on this ItemList, we are asking to count only those items that cost more than 1950 (i.e., \$19.50), so we will get back 2 as the return value.

• Exercise 15.x2: Consider the `Puzzle` applet's `pushTile` method. Suppose the puzzle is in its initial configuration

with `blankRow` and `blankCol` both equal to 3. Suppose that now two different threads concurrently invoke `pushTile(3, 2)` on this puzzle. That is, both threads are pushing the tile immediately to the left of the blank. As a result of a race between the two threads, the final result is as follows:

You are to focus on the following six steps that each thread goes through:
1. Checking `blankCol > col` the first time.
2. Doing `buttons[blankRow][blankCol-1].getLabel()`.
3. Doing `buttons[blankRow][blankCol].setLabel` with the result from the previous step.
4. Doing `blankCol--`.
5. Checking `blankCol > col` the second time.
6. Doing `buttons[blankRow][blankCol].setLabel("")`.
If we call one thread that is doing `pushTile(3, 2)` thread 1 and the other one thread 2, we can call thread 1's actions 1a through 1f and thread 2's actions 2a through 2f. You are to list these 12 actions in an interleaved order that will produce the result shown above. You are also to say what the final values of `blankRow` and `blankCol` are.