READING for Week 4


Sedgewick, 127-149, 153-170
Kernighan and Ritchie, 4.11.1, 4.11.2, 5.1, 5,2, 5.3

---------------------------------------------

        EXERCISES for Week 4 (for discussion in precept 10/13)


 1. Sedgewick, Exercise 4.2.

 2. Sedgewick, Exercise 4.6.

 3. Sedgewick, Exercise 4.10.

 4. Sedgewick, Exercise 4.18.

 5. Modify Program 4.4 to properly handle the situations where client
    programs attempt to pop an empty stack or push onto a full one.

 6. Sedgewick, Exercise 4.30 (assume maxN is 10, as in Fig. 4.8).

 7. Sedgewick, Exercise 4.31.

 8. Sedgewick, Exercise 4.47.

 9. Suppose that an intermixed sequence of push and pop operations are
    performed.  The pushes push the integers 0 through 9 in order;
    the pops print out the return value. Which of the following sequences 
    could not occur?

           4 3 2 1 0 9 8 7 6 5
           4 6 8 7 5 3 2 9 0 1 
           2 5 6 7 4 8 9 3 1 0
           4 3 2 1 0 5 6 7 8 9

10. Describe a client program that uses Program 4.1 but has different 
    outcomes depending on whether the array (Program 4.4) or linked-list 
    (Program 4.5) implementation is used.

---------------------------------------------


                    ANSWERS to Exercises for Week 4

 1.
        typedef point Item;
        #define eq(A, B) ((A.x == B.x) && (A.y == B.y))

    This definition of eq might be preferable in some applications:

        #define eq(A, B) (distance(x, y) < epsilon)

 2. 
          S   Y       E U Q     T S A     O   N I E

    E A S A Y A Q U E U Q A S T S A E I O I N I E
      E A E A E A Q U Q A E A S A E   E I E I E
        E   E   E A Q A E   E A E       E   E
                  E A E       E
                    E


 3.
    5
    5 9
    45
    45 8
    45 8 7
    45 8 7 4
    45 8 7 4 6
    45 8 7 10
    45 8 70
    45 8 70 2
    45 8 70 2 1
    45 8 70 2 1 3
    45 8 70 2 3
    45 8 70 5
    45 8 350
    45 358
    16110

 4.
    L  S  T  F
    
 5. STACKpush returns 0 if the stack was full, 1 otherwise (requires
    changing the interface); STACKpop returns NULLitem if the stack
    was empty (requires definition of NULLitem in Item.h).

      int STACKpush(Item item)
        { if (N == maxN) return 0; 
          s[N++] = item; 
          return 1; }
      Item STACKpop()
        { if (N == 0) return NULLitem; else return s[--N]; }

 6. T  O  U  T

 7.
          E   A       S Y Q     U E S     T   I O N

    E E E A A S S S S Y Q U U U E S T T T   I O N
      A A S S Y Y Y Y Q U E E E S T   I I   O N 
        S   Y   Q Q Q U E   S S T       O   N
                  U U E       T             
                    E 

 8. Same as Fig. 4.9 until second S is pushed.  Then:

    S      L T F I S
    T      L F I S T
    *   T  L F I S
    *   S  L F I
    *   I  L F
    O      L F O
    U      L F O U
    *   U  L F O
    T      L F O T
    *   T  L F O
    *   O  L F
    *   F  L


 9. The second ( 4 6 8 7 5 3 2 9 0 1 ).  When the 4 is popped, the
    stack must have 3 2 1 0 on it, so 1 has to be popped before 0.

10. Do a pop().  Array representation would give garbage; linked 
    representation would bomb on segmentation fault.