Week 03 Tutorial Questions

Algorithm Analysis

Analysis of Algorithms

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