Exercise 9.1

Consider the following algorithm:
 

   Input s
    begin
        k := LEN(s);
        if k is even then
        begin
            j := k/2;
            u := “”;
 

           while j>0 do
            begin
                u := ADDCHAR(CHAR(s),u);
                s := REST(s);
                j := j – 1;
            end
 

           s := REVERSE(s);
            u := REVERSE(u);
 

           while LEN(s)>0 do
            begin
                u := ADDCHAR(CHAR(s),u);
                s := REST(s);
            end
        end
        else
            u := s;
    end
    Output u

[Note: REVERSE is a function that reverses the order of the characters in a string. For example

REVERSE(“bin”) = “nib”.]

(a) Trace through what happens in the algorithm when theinput string s is “biscotti”. What is the resulting output string u?

(b) Describe in words the effect of the algorithm on an arbitrary string s.

Exercise 9.2

Each of the formulae below describes the number of stepsan algorithm takes, in terms of n, the size of the input to the algorithm.
 

For each formula, determine the least order of magnitudeto which it can be assigned.