CS 305, Computer Algorithms I

Fall 2003 - Test 2

1. The following code compiles successfully

   void time::add() {
     increase();
     }
   

   The following code doesn't compile successfully:

   int main() {
     time t;
     t.increase();  // error here.
     }
   

   Show the declaration (not definition) of time.

   (Here's a hint: this question has a correct answer.)

   ---

   Given the call in time::add(), it's clear that the call t.increase() is sntatically correct. Because ftn(time::add) has no trouble calling ftn(increase) but ftn(main) does, that suggests that ftn(increase is non-public in time:

   class time {
     public:
       void add();    
     private:
       void increase();    
     };
   

   actually, there's no indication that ftn(time::add) is public, but too there's no indication that it isn't.

   Many answers to this weren't even close. If the question asks for a class definition, the answer should, at minimum, look something like a class definition.

   ---

   question() in class we derived an expression to map indices to array elements. that derivation depended on knowing the address of the first array element.

   Derive the expression to map indices to array elements when we know the address of the last array element. Don't forget to explain your derivation. You should assume C++ style arrays and only answer the question for 1-dimensional arrays.

   ---

   See Question 2 in .

   ---

2. Explain the difference between accessing characters in strings using [] and .at().

   ---

   See Section 3.4, page 133, in Nyhoff.

   This was a gimme, but there were only a few correct answers.

   ---

3. Write a recursive algorithm to convert a number represented as a string into an int. Your algorithm should accept as an input parameter a const char * array containing a string representation of a non-negative, base 10 integer and return as output the int representation of the input numeral. Your function may contain any other parameters you think necessary. You need not write in c++, but you must show a recursive algorithm.

   ---

   The value of the string d_n...d₂d₁ as an integer is the value of the string d_n...d₂ times ten plus the value of d₁ as an integer; the value of the empty string is 0. From these two observations, it's a short hop to a recursive conversion routine:

   int atoi(const char a[])
     return atoi(a, a + strlen(a))
   
   int atoi(const char * f, const char * l)
     if (f >= --l)
       return 0
     else
       return atoi(f, l)*10 + (*l - '0')
   

   Several answers converted the string from left-to-right, which works too, but is more complicated, and requires an expwnsive exponentation operation. Many answers had loops in addition to recursive calls, which is a bit besides the point because recursion replaces loops (or vice versa).

   ---

This page last modified on 19 October 2003.