[Show with no answers]   [Show with all answers]

1. (Counting primitive operations)

   The following algorithm

   • takes a sorted array A[1..n] of characters, and
   • outputs, in reverse order, all 2-letter words νω such that ν ≤ ω.

   Count the number of primitive operations (evaluating an expression, indexing into an array). What is the time complexity of this algorithm in big-O notation?

   for all i = n down to 1 do
       for all j = n down to i do
           print A[i] A[j]
       end for
   end for
   

   [show answer]

   statement	# primitive operations
   for all i = n down to 1 do	\( n+(n+1) \)
   for all j = n down to i do	\( 3+5+\cdots+(2n+1) = n(n+2) \)
   print A[i] A[j]	\( (1+2+\cdots+n)\cdot 2 = n(n+1) \)
   end for
   end for

   This totals to \( 2n^2+5n+1 \), which is \( O(n^2) \)

2. (Algorithms and complexity)

   Develop an algorithm to determine if a character array of length n encodes a palindrome — that is, it reads the same forward and backward. For example, racecar is a palindrome.

   1. Write the algorithm in pseudocode.

   2. Analyse the time complexity of your algorithm.

   3. Implement your algorithm in C. Your program should accept a single command line argument, and check whether it is a palindrome. Examples of the program executing are

      ./palindrome racecar
      yes
      ./palindrome reviewer
      no
      

      Hint: You may use the standard library function strlen(3), which has prototype size_t strlen(char *), is defined in <string.h>, and which computes the length of a string (without counting its terminating '\0'-character).

   [show answer]

   isPalindrome(A):
       Input  array A[0..n-1] of chars
       Output true if A palindrome, false otherwise
   
       i = 0; j = n-1
       while i < j do
           if A[i] ≠ A[j] then
               return false
           end if
           i = i + 1; j = j - 1
       end while
   
       return true
   

   Time complexity analysis: There are at most \( \lfloor n/2 \rfloor \) iterations of the loop, and the operations inside the loop are \( O(1) \). Hence, this algorithm takes \( O(n) \) time.