COS 111, Fall 1999 - Problem Set 7

Problem 1
Brookshear, Chapter Four Review Problem 14 (pg 219). Specifically, each character string is stored in an array -- one character per array entry. This means that for any i between 1 and the length of the character string, one can examine the ith character (and in particular test whether this character is equal to some other character). Your algorithm should give as an answer the position in the second string of the beginning of the appearance of the first string as a substring. If the first string appears more than once, just give the start of the first (earliest) appearance. For example, for the strings "mississippi" and "iss", the arrays would be:

   1 m                  1 i
   2 i                  2 s
   3 s                  3 s
   4 s
   5 i
   6 s
   7 s
   8 i
   9 p
  10 p
  11 i

Problem 2

For your algorithm solving problem 1 above, in the worst case, what is the running time of your algorithm given a first (short) string of length S and a second (long) string of length L? I am interest in an answer of the form "the running time is proportional to ...", analogous to the statement "the running time for binary search on an array of N items is proportional to log (base 2) of N." If it helps you in thinking about this, plug in real numbers and figure out how many steps your algorithm executes.

Problem 3
Part a Write an algorithm that takes as input an array of integers in arbitrary order and the average of those integers and produces a new array containing the same integers, but for which the integers less than the average appear earlier in the array than the integers greater than or equal to the average. Other than this condition that integers less than the average appear before integers greater than or equal to the average, there is no other requirement on the order of the integers in the new array. Design the algorithm to be as efficient as you can. Your algorithm should have linear running time, that is, running time proportional to the number of integers in the array.

Example:

Input array:      Average:  36.8           Output array:
  1.  35                                     1.  35
  2.  10                                     2.  10
  3.  59                                     3.   3
  4.   3                                     4.  59
  5.  77                                     5.  77

Part b How can you use your algorithm of Part a as part of (i.e. a subroutine in) an algorithm to sort the array of integers?
(If your algorithm of Part a is no more efficient than sorting, this is not an efficient way to construct a sorting algorithm. However, if your algorithm of Part a has linear running time, then an efficient sorting algorithm can be produced.)

Problem 4
Brookshear, Chapter Four Review Problem 16 (pg 219).

Extra Credit
Brookshear, Chapter Four Review Problem 17 (pg 219).