READING for Week 6


Sedgewick, 187-212

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

        EXERCISES for Week 6 (for discussion in precept 11/3)


 1. Sedgewick, Exercise 5.3.

 2. Sedgewick, Exercise 5.6.

 3. Sedgewick, Exercise 5.8.

 4. Sedgewick, Exercise 5.14.

 5. Sedgewick, Exercise 5.17.

 6. Sedgewick, Exercise 5.29.

 7. Sedgewick, Exercise 5.30.

 8. Sedgewick, Exercise 5.33.

 9. Sedgewick, Exercise 5.39.





































                    ANSWERS to Exercises for Week 6


 1.
      1 4 2 1
      3 10 5 16 8 4 ..
      6 3 10 5 ...
      7 22 11 34 17 52 26 13 40 20 10 5 ...
      9 28 14 7 ...

 2.   gcd(89, 55)
        gcd(55, 34)
          gcd(34, 21)
            gcd(21, 13)
              gcd(13, 8)
                gcd(8, 5)
                  gcd(5, 3)
                    gcd(3, 2)
                      gcd(2, 1)
                        gcd(1, 0)

 3.   eval() + * * 12 12 12 144
        eval() * * 12 12 12
          eval() * 12 12
            eval() 12
            eval() 12
            return 144 = 12*12
          eval 12
          return 1728 = 144*12
        eval 144
        return 1872 = 1728+144

 4.   link deletefinal(link x)
        {
          if (x == NULL) return NULL;
          if (x->next == NULL)
            { free(x); return NULL; }
          x->next = deletefinal(x->next);
          return x;
        }

 5.   Item findmax(link x)
        { int a, b
          if (x == NULL) return 0;
          a = x->item; b = findmax(x->next);
          if (a > b) return a; else return b;
        }

 6.   1 + 4 + 16 + 64 + 256 = 341

 7.   See Programming Assignment 6.

 8.   4^n

 9.
                      21
      
                8            13
      
           3         5     5    8
      
        1     2    2   3
      
            1   0