MCS-178, Intro. to Computer Science I, Spring 2005
Homework Assignments



Chapter 15
  1. Do exercise 15.11 on pages 621-622.

    Suppose in your scenarios, two threads each push tile 15 from the starting configuration. Then both threads will have row set to 3. Now, one way to clearly describe a scenario is to label the relevant lines of code in pushTile with labels start, A, B, C, D, end as below: 

      public void pushTile(int row, int col){             // start
        if (row == blankRow) {                            // A
          // First for loop omitted here (it won't execute in this scenario)
          for( ;
                 blankCol > col;                          // B
                                 blankCol--){             // C
            buttons[blankRow][blankCol].setLabel          // D
              (buttons[blankRow][blankCol-1].getLabel()); // D continued
          }
        // code omitted here (it also won't execute)
        }
        buttons[blankRow][blankCol].setLabel("");         // end
      }
    Now, to demonstrate a scenario in which two threads interact to cause unwanted behavior, you can fill in a table like the one below to explain how two threads (thread 1 and thread 2) might interact if they both push tile 15 at the same time starting from the initial configuration:
    1's LINE 2's LINE 1's col 2's col blankCol PUZZLE ROW 3
    start   2 2 3 13 14 15 --
               
               
               
               
               
  2. Do exercise 15.12 on pages 624-625.

    For part (a), you should state a clear invariant about the state of the instance variables of an item-list (item-vector and num-items) and explain how the constructor and the delete maintain these invariants.

    For part (b), your discussion should also focus on how the invariant might be violated and how your suggestion is required to avoid the violation of the invariant.

  3. Do exercise 15.19 on page 640.


Chapter 14
  1. Do exercise 14.10 on page 502.
  2. Do exercises 14.6 and 14.7 on page 499.  Just hand in the final version of delete.
  3. Do exercise 14.14  on page 513.
  4. 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).
  5. Do exercise 14.40 on pages 571-572.
Chapter 13
  1. Do exercise 13.5 on page 429.
  2. Do exercise 13.6 on pages 435-436.
  3. Do exercise 13.9 on page 441.
  4. Do exercise 13.10 on page 451.
  5. Do exercise 13.28 on pages 478-479.

Chapter 10
  1. Do exercise 10.2 on page 283. An unsigned integer is just a string of digits, such as 314.
  2. Do exercise 10.4(b) on page 284. The else branch is optional, but if it appears only the last branch can be an else branch, which has one or more expressions after the else.
  3. Do exercise 10.9 on page 295. Your answer should not only be correct, but should also be lucid, clear, and to the point.
  4. Do exercise 10.10 on page 297. I recommend you draw two types of diagrams, one as in Figures 10.3 and 10.4 on page 296, and one as in Figure 10.5 on page 298. If the diagrams are clear, no additional text is needed.
  5. Do exercise 10.13 on pages 301-302. You should show the AST and the evaluation process using the same two kinds of diagrams as in exercise 10.10.

Chapter 12
  1. This problem is an extension of 12.32.
    1. Start by doing exercise 12.32 on pages 415-416. When testing your improved versions, try running them on a large enough inputs so that the original version takes a while (at least a few seconds), and verify that the improved version computes nearly instantaneously. Be sure the results returned are identical.
    2. You'll now have three versions of ps, the recursive version in the book, a dynamic programming version, and a memoized version. For each version, draw a diagram which shows every call to ps and and every or call to ps-subproblem (i.e., every table lookup in the memoized and dynamic programming versions) in the evaluation of (ps 5). You can test your work by placing display statement(s) in your code.

  2. Repeat the last exercise using Exercise 12.34. Again, you'll have three versions of best. For each version, make diagrams showing what calls to best get called in the evaluation of (best '(2 1 3 1 4 2)).
  3. Exercise 12.x1: Draw a tree, analogous to Figure 4.4 on page 92, showing how the value of C(5,3) is computed by choose. Your tree should have C(5,3) at the root and 1s as its leaves. Also, mark which two subproblems (tree nodes) a memoized version would find already in the table, rather than needing to compute.

Chapter 11
  1. Do exercise 11.1 on page 344. Here is a postscript version of figure 11.5 which you can print and use. There is no need to allocate register names. Use SLIME to test your code.
  2. Do exercise 11.17(a) on page 372. For part (a) two opcodes can be eliminated. For each of the two opcodes, show how to rewrite an instruction which uses that opcode so that it instead uses a non-eliminated opcode.
  3. Do exercise 11.17(b) on page 372. For part (b) all but one opcode can be eliminated. To argue an individual opcode can be eliminated, give specific code fragments showing how an instruction using it can be rewritten in terms of any uneliminated opcodes. For example, assuming we have an otherwise unused register tmp at our disposal, we can start by eliminating sne, since 
      sne s, a, b
    b can be replaced by the sequence of instructions: 
      seq s, a, b
      li tmp, 1
      sub s, tmp, s
    or with the sequence of instructions: 
      sub, s, a, b
      li tmp, done-label
      jeqz s, tmp
      li s, 1
    done-label:

    Remember, that the instruction you are replacing could appear anywhere in a larger program, so (for example) your proposed replacement should not halt. (It's always best if you can avoid using an an auxiliary register such as tmp.)

  4. Do exercise 11.18 on page 373. You should test out your code in SLIME.
  5. Do exercise 11.27 on pages 375-376.
MCS 178 homepage