EXERCISES ON COMPLEXITY

READING 
-------
  Lecture notes for Algorithms and Complexity.
  Sedgewick, pages 27-64.

EXERCISES
---------


 1.  Sedgewick, Exercise 2.2

 2a. Give the complexity of the following algorithm for
     printing a string in reverse order.

       N = strlen(word);
       for (i = 0; i < N; i++)
         printf("%c", word[N-i-1]);
 
 2b. Give the complexity of the following algorithm for
     printing a string in reverse order.

       for (i = 0; i < strlen(word); i++)
         printf("%c", word[strlen(word)-i-1]);

 3. Give the complexity (using big Oh notation) of the shuffling
     algorithm in Lecture P2.18.

 4a. Give the complexity (using big Oh notation) of the
     nearest-insertion heuristics in the TSP assignment.

 4b. Give the complexity (using big Oh notation) of the
     smallest-insertion heuristics in the TSP assignment.

 5.  Give a O(N log N) algorithm for computing the median (or mode)
     of a sequence of N integers. Hint: sort first.

 6.  Give a O(N) algorithm for computing the median (or mode)
     of a sequence of N integers that are between 0 to 99.

 7.  Give a O(N) algorithm for sorting a sequence of N integers that
     are between 0 and 99.

 0.  Given a sequence of N integers, find the pair of integers that
     are closest in value. Give a O(N^2) algorithm. Give a O(N log N)
     algorithm.

 0.  Given a sequence of N integers, find the pair of integers that
     are farthest apart in value. Give a O(N) algorithm.

 8.  (challenge for the bored)  Design a O(N log N) algorithm to read in
     a list of words and print out all anagrams.  For example, the
     strings "comedian" and "demoniac" are anagrams of each other.
     Assume there are N words and each word contains at most 20 letters.
     Designing a O(N^2) algorithms should not be too difficult, but
     getting it down to O(N log N) requires some cleverness.

 9.  Show that the following problem is undecidable: given a program P
     and two inputs X and Y, determine whether P halts on *both* X and Y.










		  ----------------------------------
		  ANSWERS TO EXERCISES ON COMPLEXITY


 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
.
.
.
 2a. O(N).  Computing strlen(word) takes N steps. The body of
     the for loop is executed N times.  Each statement in the
     body of the for loop takes O(1) time.

 2b. O(N^2).  Computing strlen(word) takes N steps. This
    is computed from scratch 2N times, once in the for loop
    test condition, and once in the body of the for loop.

    There are plenty of C program out there that are extremely
    slow on long strings exactly for this reason!

 
 3.  O(N).  The body of the loop is executed N times. The body
     of the loop has 3 statements.  Thus there are a total of 
     3N steps; in big-Oh notation this is O(N).

     There are plenty of C programs out there that are extremely
     slow because they use an N^2 shuffling algorithm.

 4a. O(N^2).  Each time a new point is inserted, the algorithm
     traverses through the current linked list. When the kth
     point is added, there are k-1 points already on the list.
     For each of these k-1 points, we need to compute the Euclidean
     distance to the new point.  Thus, inserting the kth point
     takes O(k) steps.  Summing up over all N points, we get
     1 + 2 + 3 + . . . + N-1 = O(N^2).

 4b. O(N^2).  Basically the same as above.  Instead of computing
     the distance from one of the k-1 points to the new point,
     we compute the change in tour length.  This involves 3 Euclidean
     distance computations instead of 1, but this constant is
     buried in the big Oh notation.

     Note that if you recompute the tour length each time from
     scratch (instead of computing the change in tour length),
     you would get a O(N^3) algorithm.


 5. Sort the integers using mergesort in O(N log N) steps.
    The median is now stored in array element N/2.  The
    mode can also be found easily since now all equal values
    are stored consecutively.

 6. See array exercises 4 and 5.

    Using lots of cleverness, the median can still be computed
    in O(N) time even without the assumption that the integers
    lie in the range 0 to 99. See COS 226.

 7. See Question 4 from Spring 2000 Midterm 1.  The assumption
    that the integers are in the range 0 to 99 is crucial, and
    enables us to beat the N log N lower bound.  Recall this lower
    bound assumes that the algorithm only performs comparison
    and swap operations.

 8. Hint 1: sort.
    Hint 2: sort.
    
 9. Suppose that the problem is decidable. Then there exists a
    subroutine HaltOnBoth(P, X, Y) that prints "yes" if program
    P halts on inputs X and Y, and "no" otherwise. Then, to solve
    the Halting problem we could just call the subroutine
    HaltOnBoth(P, X, X). This will print "yes" if program P halts
    on input X, and "no" otherwise. Thus, the Halting problem
    would be decidable. This is a contradiction, so the original
    problem is undecidable.