COMP2521 20T1 - Week 02 Tutorial

Week 02 Tutorial
Analysis of Algorithms

(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

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) \)

(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).
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.