Solutions and grading by Mao Chen
maoch@cs.princeton.edu, office hours TuTh 2:30-3:30pm or by appointment 

NOTE: In the following description, A[i] refers to the ith item of array A

Problem 1: Total point is 10
The pseudocode of the algorithm is as follows:

Input: 
	array Module   -- the first string
	array Template -- the second string
Output:
	The position in Template of the beginning of the first
	appearance of Module

Code:
	assign Repetition the value of (length(Template) - length(Module) + 1);

        assign i the value 1;
	while (i <= Repetition) do 
	  (assign j the value 1;
	   while (j <= length(Module)) do
	     (if (Module[j] is not equal to Template[i+j-1]) then
		stop checking this i;
	     )
	   
	   if (j is equal to length(Module) ) then
	     (print i
	      done)
	  )

2. The worst case is that the first string is the last substring of
   the second string. For example, the first string is "cde" and the
   second string is "abcde". From the nested loop in the above code,
   we know the running time is proportional to S*L in the worst case.

3.
Part a:
Input: 
	array A with integers and Average which is the average value of A.
Output:
	array B in which integers less or equal to the average appear
	earlier than those greater than the average.
Code:
	assign Head with the value 1
	assign Rear with the value size(A)

	assign i with the value 1
	while (i <= size(A)) do
	  (if (A[i] <= Average) then
	     (B[Head] = A[i]
	      Head = Head + 1)
	    else 
	     (B[Rear] = A[i]
	      Rear = Rear - 1)
          )

        Print B.

*There are other approches to do it and the outputs using different approches
 may be different. Any algorithm which can give required result in a linear
 time is correct.

Part b:
 We can implement a divide and conquer algorithm using the algorithm in part a.
 The basic idea is we can divide one array into two parts using the average
 value. Then all items in the first part are not greater than those in the
 second part. We can do this patition on the two parts recursively and then
 get an array in increasing order.

 Let the function in part a be "Patition", a recursive sorting algorithm can
 be as follows:

 Input: array A with a sequence of integers
 Ouput: Sorted array B in increasing order.

 Sort(A)
     A' = Patition(A)
     A1'= subarray of A whose values are not greater than the average value 
	  of A
     A2'= subarray of A whose values are greater than the average value of A

     B1'= Sort(A1')
     B2'= Sort(B2')

     B = B1' followed by B2'

 The average running time of the above algorithm is O(nlogn), where n is 
 the size of the input array.

Problem 4:
  This is a recursive program. The following is a list of function calls and
  the output for each call.

    Function call	Last    Current	    Ouput(A[current])
  MysteryWrite(0,1)      0         1		1
  MysteryWrite(1,1)      1         1		1
  MysteryWrite(1,2)      1         2		2
  MysteryWrite(2,3)      2         3		3
  MysteryWrite(3,5)      3         5		5
  MysteryWrite(5,8)      5         8		8
    ......	        ...       ...           ...

  So the ouput is a Fibonacci sequence whose greatest item is less than 100.
  To be exactly, the output stream is 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89.


Extra Credit:
  In each level of recursion, the value of Current is printed out before
  the next level of recursion. Similarly, each level of recursion returns
  to the point where it is called in the above level. Let's change 100 to
  10 and we can describe the whole process by the following graph(let M
  denote the function MysteryWrite):
 
  M(0,1)	
    print 1	---- level 1
    M(1,1)
      print 1	---- level 2
      M(1,2)
	print 2 ---- level 3
        M(2,3)	
	  print 3 -- level 4
	  M(3,5)
	    print 5 -- level 5
	    M(5,8) 
	      print 8 -- level 6
	      M(8,13) 
	        return directly to the level 6  at level 7
	
	      return to the level 5
	    return to the level 4
          return to the level 3
        return to the level 2
      return to the level 1
    return and quit from the whole process

   The basic graph is similar to this one when we change 10 to 100.
   To get an inverse sequence, we can put the print function after
   the recursive function call in each level. The new procedure is:

    
  procedure New_MysteryWrite(Last, Current)
  if(Current < 100) then
    (assign Temp the value of Current + Last;
     apply New_MysteryWrite to the values Current and Temp
     print the value assigned to Current)

Again, using 10 instead of 100, we can describe the new result:

  M(0,1)     ---- level 1
    M(1,1)     ---- level 2
      M(1,2)    ---- level 3
        M(2,3)	   ---- level 4
	  M(3,5)     ---- level 5
	    M(5,8)     ---- level 6
	      M(8,13)     ---- level 7
	        return directly to the level 6 at level 7
	       print 8 -- level 6
	       return to the level 5
	    print 5 -- level 5
	    return to the level 4
	  print 3 -- level 4
          return to the level 3
	print 2 ---- level 3
        return to the level 2
      print 1	---- level 2
      return to the level 1
    print 1	---- level 1
    return and quit from the whole process