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

   #include <stdbool.h>
   #include <stdio.h>
   #include <string.h>
    
   static bool isPalindrome (char A[], int len);
    
   int main (int argc, char *argv[])
   {
   	if (argc == 2) {
   		if (isPalindrome (argv[1], strlen (argv[1])))
   			printf ("yes
   ");
   		else
   			printf ("no
   ");
   	}
   	return 0;
   }
    
   static bool isPalindrome (char A[], int len)
   {
   	int i = 0;
   	int j = len - 1;
    
   	while (i < j) {
   		if (A[i] != A[j])
   			return true;
   		i++; j--;
   	}
   	return false;
   }

3. (Algorithms and complexity)

   Let \( p(x) = a_nx^n + a_{n-1}x^{n-1} + \cdots + a_1x + a_0 \) be a polynomial of degree \( n \). Design an \( O(n) \)-time algorithm for computing \( p(x) \).

   Hint: Assume that the coefficients \( a_i \) are stored in an array A[0..n].

   [show answer]

   Rewriting \( p(x) \) as \( ( \cdots ((a_n x + a_{n-1}) x + a_{n-2}) x + \cdots + a_1) x + a_0 \) leads to the following algorithm:

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

   This is \( O(n) \).

4. (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. We call L the compact form of \( V \).

   For example, the 8-dimensional vector \( V=(2.3,0,0,0,-5.61,0,0,1.8) \) could be stored in a list L of size 3: \( [ (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).

   [show 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
   
       i = 0      // index into L1
       j = 0      // index into L2
       k = 0      // index into L3
       while i ≤ m-1 ∧ j ≤ n-1 do
           if L1[i].x = L2[j].x then
               // found index with entries in both vectors
   
               if L1[i].v ≠ -L2[j].v then
                   // only add if the values don't add up to 0
                   L3[k] = (L1[i].x, L1[i].v + L2[j].v)
                   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
               // 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: Adding a pair to L3 takes \( O(1) \) time. At most \( m + n \) pairs from L1 and L2 are added. Therefore, the time complexity is \( O(m + n) \).

5. Challenge Exercise

   Suppose that you are given two stacks of non-negative integers \( A \) and \( B \) and a target threshold \( k \ge 0 \). Your task is to determine the maximum number of elements that you can pop from \( A \) and \( B \) so that the sum of these elements does not exceed \( k \).

   For example, given the stacks

   

   The maximum number of elements that can be popped without exceeding \( k = 10 \) is 4:

   

   If \( k = 7 \), then the answer would be 3: the top element of A and the top two elements of B.

   1. Write an algorithm (in pseudocode) to determine this maximum for any given stacks \( A \) and \( B \) and threshold \( k \). As usual, the only operations you can perform on the stacks are pop and push. You are permitted to use a third "helper" stack, but no other aggregate data structure.

   2. Determine the time complexity of your algorithm depending on the sizes \( m \) and \( n \) of input stacks \( A \) and \( B \).

   Hints:
   • A so-called greedy algorithm would simply take the smaller of the two elements currently on top of the stacks and continue to do so as long as you haven't exceeded the threshold. This won't work in general for this problem.
   • Your algorithm only needs to determine the number of elements that can maximally be popped without exceeding the given k. You do not have to return the numbers themselves nor their sum. Also you do not need to restore the contents of the two stacks; they can be left in any state you wish.

   [show answer]

   MaxElementsToPop(A,B,k):
       Input  stacks A and B, target threshold k ≥ 0
       Output maximum number of elements that can be popped from A and B
              so that their sum does not exceed k
   
       sum = 0; count = 0;
       C = new Stack
       // Phase 1: Determine how many elements can be popped just from A,
       // and push those onto the helper stack C
       while sum ≤ k ∧ stack A not empty do
           v = pop(A); push(C, v)
           sum = sum + v; count = count + 1
       end while
   
       // have we exceeded k?
       if sum > k then
           // subtract last element that's been popped off A;
           // this is the best you can do with elements from A only.
           v = pop(C); sum = sum - v; count = count - 1
       end if
       best = count
   
       // Phase 2: add one element from B at a time; whenever the threshold
       // is exceeded, subtract more elements originally from A (now in C),
       // to get back below threshold
       while stack B not empty do
           v = pop(B); sum = sum + v; count = count + 1
   
           while sum > k ∧ stack C not empty do
               v = pop(C); sum = sum - v; count = count - 1
           end while
   
           // update each time you got a better score
           if sum ≤ k ∧ count > best then
               best = count
           end if
       end while
   
       return best
   

   Time complexity analysis: In phase 1, the worst case is when all \( m \) elements in stack A need to be visited, for a maximum of \( m + 1 \) pop, and \( m \) push operations. In phase 2, the worst case is when all elements have to be taken from both B and C, for a maximum of \( m + n \) pop operations. Assuming that push and pop take constant time, the overall complexity is \( O(m+n) \). This makes it a linear-time solution.