EXERCISES ON ALGORITHMS

READING 
-------
  Notes for lectures 10 and 23.
  Sedgewick, pages 27-38, 253-258, 303-309, 335-342, 477-508.

EXERCISES
---------


 1. Sedgewick, Exercise 2.2

 2. Sedgewick, Exercise 6.15

 3. Sedgewick, Exercise 7.1

 4. Sedgewick, Exercise 7.8

 4. Sedgewick, Exercise 8.9

 5. Sedgewick, Exercise 12.47.
    (fix bug: "bottom tree in 12.5" -> "4th tree in 12.6")
















		  ----------------------------------
		  ANSWERS TO EXERCISES ON ALGORITHMS


 1. Depends on the computer and the compiler!  These times are on a DEC Alpha.

    % gcc billion.c
    time a.out 
    313.35u 1.16s 10:36 49% 0+1k 1+0io 14pf+0w

    % gcc -O9 billion.c
    time a.out
    30.64u 0.20s 1:02 49% 0+1k 1+0io 14pf+0w

    % cc billion.c
    time a.out
    289.52u 1.31s 9:51 49% 0+1k 3+0io 14pf+0w

    % cc -O9  billion.c
    time a.out
    289.49u 0.96s 9:45 49% 0+1k 10+0io 16pf+0w

    % lcc billion.c
    time a.out 
    45.79u 0.16s 1:31 50% 0+0k 2+0io 2pf+0w
.
.
.
 2. E  A  S  Y  Q  U  E  S  T  I  O  N
    A  E  S  Y  Q  U  E  S  T  I  O  N
    A  E  S  Y  Q  U  E  S  T  I  O  N
    A  E  S  Y  Q  U  E  S  T  I  O  N
    A  E  Q  S  Y  U  E  S  T  I  O  N
    A  E  Q  S  U  Y  E  S  T  I  O  N
    A  E  E  Q  S  U  Y  S  T  I  O  N
    A  E  E  Q  S  S  U  Y  T  I  O  N
    A  E  E  Q  S  S  T  U  Y  I  O  N
    A  E  E  I  Q  S  S  T  U  Y  O  N
    A  E  E  I  O  Q  S  S  T  U  Y  N
    A  E  E  I  N  O  Q  S  S  T  U  Y 
 
 3. E  A  S  Y  Q  U  E  S  T  I  O  N
    E  A  I  E  N* U  Y  S  T  S  O  Q
    E  A  E* I
    A* E
       E*
             I*
                N  O  Q* S  T  S  U  Y
                N  O*
                N*
                         S  T  S  U  Y*
                         S  T  S  U*
                         S  S* T
                         S*
                               T*
    A  E  E  I  N  O  Q  S  S  T  U  Y 

 4. N lg N. It divides the file in half because the partitioning
    pointers stop on keys equal to the partitioning element.

 5. E  A  S  Y  Q  U  E  S  T  I  O  N
p    A  E
          S  Y
    A  E  S  Y
                Q  U
                      E  S
                E  Q  S  U
    A  E  E  Q  S  S  U  Y
                            I  T
                                  N  O
                            I  N  O  T
    A  E  E  I  N  O  Q  S  S  T  U  Y

 6. A  S  E  R  C  H  I  N  G  X  M  P
    A  S  E  R  H  C  I  N  G  X  M  P
    A  S  E  R  H  I  C  N  G  X  M  P
    A  S  E  R  H  I  N  C  G  X  M  P
    A  S  E  R  H  I  N  G  C  X  M  P
    A  S  E  R  H  I  N  G  X  C  M  P
    [numerous other answers]