Week 03 Tutorial Answers

Algorithm Analysis

Analysis of Algorithms

  1. (Algorithms and complexity)

    Design an algorithm to determine if a string of length \( n \) is a palindrome - that is, it reads the same backwards as forwards. For example, "racecar" is a palindrome, while "reviewer" is not.

    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:

    1. isPalindrome(S):
	Input:  array S[0..n - 1] of characters
	Output: true if S is a palindrome, false otherwise
	
	l = 0
	r = n - 1
	while l < r do
		if S[l] ≠ S[r] then
			return false
		end if
		l = l + 1
		r = r - 1
	end while
	
	return true

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

    3. #include <stdbool.h>
#include <stdio.h>
#include <string.h>

static bool isPalindrome(char *s);

int main(int argc, char *argv[]) {
	if (argc == 2) {
		if (isPalindrome(argv[1])) {
			printf("yes\n");
		} else {
			printf("no\n");
		}
	}
	return 0;
}

static bool isPalindrome(char *s) {
	int l = 0;
	int r = strlen(s) - 1;

	while (l < r) {
		if (s[l] != s[r]) {
			return false;
		}
		l++;
		r--;
	}
	return true;
}

  2. (Algorithms and complexity)

    Using only techniques that you have learned so far, design an algorithm to determine if an array contains two elements that sum to a given value.

    1. Write the algorithm in pseudocode.
    2. Analyse the time complexity of your algorithm.
    3. Implement your algorithm as a function in C. The algorithm should accept an array and a value as input and return true or false.

    Answer:

    1. hasTwoSum(A, v):
	Input:  array A[0..n - 1] of integers
	        integer v
	Output: true if A contains two elements that sum to v, false otherwise

	for i = 0 up to n - 1 do
		for j = i + 1 up to n - 1 do
			if A[i] + A[j] = v then
				return true
			end if
		end for
	end for
	
	return false
    2. Time complexity analysis: The time complexity is determined by the number of iterations of the inner loop, since all the operations within the inner loop are \( O(1) \). In the worst case, there are \( n \) iterations of the outer loop and \( (n - 1) + (n - 2) + \ldots + 1 + 0 = \frac{1}{2} n(n - 1) \) iterations of the inner loop. Removing constant factors and lower terms gives a worst case time complexity of \( O(n^2) \).
    3. bool hasTwoSum(int a[], int n, int v) {
	for (int i = 0; i < n; i++) {
		for (int j = i + 1; j < n; j++) {
			if (a[i] + a[j] == v) {
				return true;
			}
		}
	}
	return false;
}

  3. (Algorithms and complexity)

    Let \( p(x) = a_n x^n + a_{n - 1} x^{n - 1} + \cdots + a_1 x + a_0 \) be a polynomial of degree \( n \). Design an \( O(n) \)-time algorithm for computing \( p(x) \). You can assume that the coefficients \( a_i \) are stored in an array \( A = [a_0, a_1, \ldots , a_n] \).

    Answer:

    An inefficient solution might compute each of the powers of \( x \) from scratch in order to obtain each term of the polynomial. This leads to the following pseudocode:

    evalPolynomial(A, n, x):
	result = 0
	for i = 0 up to n do
		result = result + A[i] * power(x, i)
	end for
	return result

    Assuming that power uses a simple loop to compute the \( i^{th} \) power of \( x \), this algorithm is \( O(n^2) \), because there are \( (n + 1) \) iterations of the loop, and power is an \( O(n) \) operation.

    One clue that this function could be improved is that it repeats a lot of computation. For example, the function computes \( x^n \) from scratch, but if it had kept the value of \( x^{n - 1} \) (which it had computed in the previous iteration) in memory, then \( x^n \) could be obtained by simply multiplying \( x^{n - 1} \) by \( x \).

    A more efficient solution uses a variable to keep the current power of \( x \) in memory, and multiplies it by \( x \) once each iteration to obtain the next power of \( x \).

    evalPolynomial(A, n, x):
	powerx = 1
	result = 0
	for i = 0 up to n do
		result = result + A[i] * powerx
		powerx = powerx * x
	end for
	return result

    This algorithm is \( O(n) \), because there are \( (n + 1) \) iterations of the loop, and the operations within the loop are \( O(1) \).

    An alternative efficient solution uses the observation that a polynomial \( a_0 + a_1x + a_2x^2 + \cdots + a_nx^n \) can be written as \( a_0 + x(a_1 + x(a_2 + \cdots + x(a_{n - 1} + xa_n) \cdots )) \) (this is known as Horner's rule). This leads to the following algorithm:

    evalPolynomial(A, n, x):
	result = A[n]
	for i = n - 1 down to 0 do
		result = result * x + A[i]
	end for
	return result

  4. (Algorithms and complexity)

    Consider the following algorithm, which converts a positive integer \( n \) to its binary representation.

    BinaryConversion:
	Input:  positive integer n
	Output: binary representation of n on a stack
	
	create empty stack S
	while n > 0 do
		push (n mod 2) onto S
		n = floor(n / 2)
	end while
	return S

    What is the time complexity of the algorithm? Assume that creating a stack and pushing an element onto a stack are both \( O(1) \) operations (i.e., constant).

    Answer:

    The complexity is determined by the number of iterations of the loop, since all of the operations in the loop are \( O(1) \). The loop will run as many times as it takes to reduce a number to zero by dividing by two (and taking the floor). This is \( log_2(n) \) times. So the time complexity is \( O(\log n) \).

  5. (Algorithms and complexity)

    A classic problem in computer science is the problem of implementing a queue using two stacks. Consider the following attempt at a solution (written in pseudocode):

    QueueNew:
	initialise two empty stacks s1 and s2

QueueEnqueue:
	push given item onto s1

QueueDequeue:
	while s1 is not empty:
		pop an item from s1 and push it onto s2

	front = pop item from s2

	while s2 is not empty:
		pop an item from s2 and push it onto s1

	return front
    1. Verify that this solution is correct.
    2. Analyse the time complexity of the enqueue and dequeue operations.
    3. The main problem with this solution is its efficiency - the dequeue operation is very inefficient as it must always move items from one stack to the other and then back again. Can you suggest an improvement to the dequeue operation? Analyse the time complexity of your improved dequeue operation.

    Answer:

    1. Try enqueuing a sequence of numbers and then dequeuing them.
    2. The time complexity of the enqueue operation is \( O(1) \), as pushing an item onto a stack is an \( O(1) \) operation. The time complexity of the dequeue operation is \( O(n) \) where \( n \) is the number of items in the queue, because it must perform \( 2n \) pushes and pops.
    3. The crucial observation is that when we pop everything from s1 and push it onto s2, the items in s2 are now in the correct order for dequeuing. So if we can avoid moving all the items back to s1, then we can dequeue the rest of the items very efficiently as all we have to do is to pop from s2.

      So suppose that when we dequeue, we pop everything from s1 and push it onto s2, but then we don't move everything back to s1. This leads to the following attempt:

      QueueDequeue:
	while s1 is not empty:
		pop an item from s1 and push it onto s2

	front = pop item from s2
	return front

      The problem with this approach is that if we enqueue some more items and then perform the dequeue operation again, the items in s2 will no longer be in the right order. So how do we resolve this?

      We can amend our observation from earlier by noting that the items in s2 will be in the correct order for dequeuing as long as no more items are pushed onto s2. So while s2 still contains items, we should leave the recently enqueued items in s1, and we can dequeue by simply popping the next item from s2. Once s2 becomes empty, we can refill it by transferring all the items from s1 to s2. This leads to the following solution:

      QueueDequeue:
	if s2 is empty:
		while s1 is not empty:
			pop an item from s1 and push it onto s2

	front = pop item from s2
	return front

      Now for the complexity analysis. Notice that the worst case time complexity is still \( O(n) \), because if s2 is empty then we must transfer all the items from s1 to s2. But after we do this, the next \( n \) dequeues will all be \( O(1) \). Therefore if we take the average over the entire sequence of dequeues, the average cost of a dequeue operation is \( O(1) \).

      The technique of analysing an algorithm's time complexity by averaging over a sequence of operations is known as amortised analysis. Amortised analysis is particularly useful when analysing an algorithm that is occasionally very costly but is otherwise very fast (i.e., the algorithm occasionally does more work up front to reduce the work later on). In these situations, only considering the worst case complexity is too pessimistic because the worst case occurs very infrequently. In this question we would say that the amortised complexity of the dequeue operation is \( O(1) \).

  6. (Algorithms and complexity)

    Suppose that you are given an array \( A \) containing \( n \) items. Your task is to print a permutation of these items which is given by a second array \( P \) of size \( n \), where each element \( P[i] \) is the position at which the corresponding item \( A[i] \) should appear in the permutation.

    For example, if \( A \) is [cat, dog, mouse] and \( P \) is [2, 3, 1], then you should print the permutation [mouse, cat, dog], because according to \( P \), cat should appear in the second position (2), dog should appear in the third position (3), and mouse should appear in the first position (1).

    Consider the following simple algorithm which solves the task:

    PrintPermutation(A, P):
	Input: array of items A and array of positions P of length n
	
	for i = 1 up to n do // for each position i
		for j = 0 up to n - 1 do // find the item that belongs at position i
			if P[j] = i then
				print A[j]
			end if
		end for
	end for
    1. What is the time complexity of this algorithm?
    2. What is the space complexity of this algorithm?
    3. Describe a more efficient algorithm that achieves the same purpose. The only restriction is that you are not allowed to modify the given arrays. What is the time complexity and space complexity of this new algorithm? (Hint: consider using a temporary array.)

    Answer:

    1. There are \( n \) iterations of the outer loop, and for each iteration of the outer loop, there are \( n \) iterations of the inner loop, so the time complexity is \( O(n^2) \).
    2. The algorithm uses a constant amount of extra memory - \( O(1) \).
    3. A more efficient algorithm assembles the permutation in a temporary array, and then prints the temporary array. 
      PrintPermutation(A, P):
	Input: array of items A and array of positions P of length n
	
	T = array of length n
	
	for i = 0 up to n - 1 do
		T[P[i] - 1] = A[i]
	end for
	
	for i = 0 up to n - 1 do
		print T[i]
	end for
      The main difference between this algorithm and the original algorithm is that the loops in this algorithm are not nested, but are performed one after the other. Each loop has \( n \) iterations, so the time complexity of this algorithm is \( O(n) + O(n) = O(n) \). Since this algorithm requires a temporary array of size \( n \), the space complexity of the algorithm is \( O(n) \). Notice that we have improved the efficiency of the algorithm, but at the cost of requiring additional memory.

  7. (Algorithms and complexity)

    A vector \( V \) is called sparse if most of its elements are 0. In order to store sparse vectors efficiently, we can use a list L to store only its non-zero elements. Specifically, for each non-zero element \( V[i] \), we store an index-value pair \( (i, V[i]) \) in L. For efficiency reasons, the index-value pairs are stored in increasing order of index. We call L the compact form of \( V \).

    For example, the sparse vector representation of the 8-dimensional vector \( V = (2.3, 0, 0, 0, -5.61, 0, 0, 1.8) \) is \( [ (0,2.3), \) \( (4, -5.61), \) \( (7, 1.8) ] \).

    Describe an efficient algorithm for adding two sparse vectors \( V_1 \) and \( V_2 \) of equal dimension, but given in compact form. The result should be in compact form too. What is the time complexity of your algorithm, depending on the sizes \( m \) and \( n \) of the compact forms of \( V_1 \) and \( V_2 \), respectively?

    Hint: The sum of two vectors \( V_1 \) and \( V_2 \) is defined as usual; for example, \( (2.3, -0.1, 0, 0, 1.7, 0, 0, 0) \) \( + \) \( (0, 3.14, 0, 0, -1.7, 0, 0, -1.8) \) \( = \) \( (2.3, 3.04, 0, 0, 0, 0, 0, -1.8) \).

    Answer:

    In the algorithm below, L[i].x denotes the first component (the index) of a pair L[i], and L[i].v denotes its second component (the value).

    VectorSum(L1, L2):
	Input:  compact forms L1 of length m and L2 of length n
	Output: compact form of L1 + L2

	L3 = new sparse vector

	i = 0      // index into L1
	j = 0      // index into L2
	k = 0      // index into L3
	while i ≤ m - 1 and j ≤ n - 1 do
		if L1[i].x = L2[j].x then
			// found index with entries in both vectors
			sum = L1[i].v + L2[j].v
			
			if sum ≠ 0 then
				// only add if the values don't add up to 0
				L3[k] = (L1[i].x, sum)
				k = k + 1
			end if
			i = i + 1; j = j + 1

		else if L1[i].x < L2[j].x then
			// copy an entry from L1
			L3[k] = (L1[i].x, L1[i].v)
			i = i + 1; k = k + 1

		else if L1[i].x > L2[j].x then
			// copy an entry from L2
			L3[k] = (L2[j].x, L2[j].v)
			j = j + 1; k = k + 1
		end if
	end while

	// copy any remaining pairs from L1
	while i < m - 1 do
		L3[k] = (L1[i].x, L1[i].v)
		i = i + 1; k = k + 1
	end while

	// copy any remaining pairs from L2
	while j < n - 1 do
		L3[k] = (L2[j].x, L2[j].v)
		j = j + 1; k = k + 1
	end while

    Time complexity analysis: Appending a pair to L3 takes \( O(1) \) time, and at most \( m + n \) pairs from L1 and L2 are added (this occurs when there are no indexes in common between L1 and L2. Therefore, the time complexity is \( O(m + n) \).