Week 02 Tutorial
Analysis of Algorithms

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

  1. (Counting primitive operations)

    The following algorithm

    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]

  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
      ./palindrome reviewer

      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]

  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]

  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]

  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

    [stack A, from bottom to top: 1, 6, 4, 2, 4;
           stack B, from bottom to top: 5, 8, 1, 2]

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

    [stack A, from bottom to top: 1, 6, 4;
           stack B, from bottom to top: 5, 8;
           nodes 2, 4 popped from A;
           nodes 1, 2 popped from B]

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


    [show answer]