EXERCISES ON COMPLEXITY



 1.  Sedgewick, Exercise 2.2

 2.  (a) 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]);
 
     (b) 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.

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

     (b) 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.  (a) Give a O(N) algorithm for sorting a sequence of N integers that
         are between 0 and 99.

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

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

     (b) Given a sequence of N real numbers, 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.