CS 305, Computer Algorithms I

Fall 2003 - Test 2


  1. A palindrome is a string that reads the same forwards as backwards; "otto" is a palindrome, as is "madamimadam", which is a palindrome for "Madam, I'm Adam" (and "madam" too is a palindrome).

    Write a recursive algorithm to determine if a string is a palindrome. Your algorithm should accept as an input parameter a const char * array containing the suspected palindrome and return true if the input really is a palindrome; otherwise it should return false. Your function may contain any other parameters you think necessary. You need not write in c++, but you must show a recursive algorithm.


    If the string cstrc is a palindrome, then so is the string str; this is the basis for a recursive test for palindromes. If str is less than two characters long, then str is also a palindrome; this is the stopping condition.

    From these two observations, it's a short hop to some recursive code to find palindromes:

    bool palindrome(const char str[])
      return palindrome(str, str + strlen(a) - 1)
    
    bool palindrome(const char * left, const char * right)
      if (left >= right)
        return true
      else
        return (*left == *right) and palindrome(f + 1, l - 1)
    

    Most answers got close to the right answer, at least in the general details.


  2. In class we derived an expression to map indices to array elements in left to right order by increasing non-negative index value.

    Some languages also provide a mapping in right-to-left order by decreasing negative index value.

    Derive the expression to map indices to array elements for right-to-left order by decreasing negative index values. Don't forget to explain your derivation. Only answer the question for 1-dimensional arrays.


    See Question 1 in .


  3. 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.


  4. The following code, when compiled, fails with a compilation error as indicated.

    void time::add(unsigned delta) {
      running_time += delta; // compilation error.
      }
    

    The following code compiles successfully:

    int main() {
      time t;
      unsigned now;
      now = t.running_time;
      }
    

    Show the declaration (not definition) of time.

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


    There's no access problem, because if main() can access time::running_time, then time::add()() can certainly access it too. The problem must be in the way time::running_time's being accessed: main() accesses it for reading, but (time::add()) accesses it for writing, which is causing problems.

    class time {
      public:
        void add(unsigned delta);    
        const unsigned t.running_time;
      };
    

    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.



This page last modified on 19 October 2003.