Exercise set V

Note: Students are encouraged to solve as many problems from this set as possible. Some of these will be solved during the lectures, if time permits. We have made attempts to classify the problems based on the difficulty level of solving them. An unmarked exercise is of low to moderate difficulty. Harder problems are marked by H, H² and H³ meaning "just hard", "quite hard" and "very hard" respectively. Exercises marked by M have mathematical flavor (as opposed to computational). One requires elementary knowledge of number theory or algebra or geometry or combinatorics in order to solve these mathematical exercises.

1. [M] Arrange the following functions in the increasing order of their rates of growth:

      (sqrt(2))n, 2sqrt(n), n2log n, n(log n)2, (nlog n)2, nlog n, nsqrt(n), nn, (log n)n.
   

2. Let f(n) be the polynomial

      f(n) = adnd + ad-1nd-1 + ... + a1n + a0
   

   with a_d > 0. Prove that f(n) = O(n^d) and n^d = O(f(n)). (Note that some of the coefficients a_i may be negative.)

3. Let f(n),g(n),f₁(n),g₁(n) be positive real-valued functions of natural numbers. Prove the following assertions:
   1. If f(n) = O(f₁(n)) and g(n) = O(g₁(n)), then f(n) + g(n) = O(f₁(n) + g₁(n)).
   2. If f(n) = O(f₁(n)) and g(n) = O(g₁(n)), then f(n)g(n) = O(f₁(n)g₁(n)).
   3. f(n) + g(n) = O(max(f(n),g(n))).

4. Establish that the worst-case running times of insertion sort and of selection sort on an array of n elements are O(n²).

5. [M] Denote U(n) = S(n) / 3, where S(n) is as defined in the derivation of the running time of the recursive Fibonacci function. Find a closed form formula for U(n) and hence for T(n).

6. Deduce that the following function recursively computes Fibonacci numbers in linear time.

      int F ( int n , int *Fprev )
      {
         int Fn_1, Fn_2;
   
         if (n == 0) {
            *Fprev = 1;
            return (0);
         }
         if (n == 1) {
            *Fprev = 0;
            return (1);
         }
         Fn_1 = F(n-1,&Fn_2);
         *Fprev = Fn_1;
         return (Fn_1+Fn_2);
      }
   

7. The following function recursively determines whether a given string is a palindrome. Determine its time complexity.

      int isPalindrome ( char A[] , int n )
      {
         if (n <= 1) return 1;
         if (A[0] != A[n-1]) return 0;
         return isPalindrome(&A[1],n-2);
      }
   

8. Determine the time complexity of the following iterative function:

      int f ( int A[SIZE][SIZE] , int n )
      {
         int i, j, sum = 0;
   
         for (i=0; i<n; ++i) {
            if (i % 2 == 0)
               for (j=0; j<=i; j=j+1) sum = sum + A[i][j];
            else
               for (j=n-1; j>=i; j=j-1) sum = sum - A[i][j];
         }
      }
   

9. [H] Write a function that accepts a positive integer n and prints all permutations of 1,2,3,...,n. Assume that printing a single integer is a basic operation and establish the time complexity of your function.

10. Establish that merging two sorted arrays each of size n/2 can be done in O(n) time.

11. Establish that merging two sorted linked lists each of size n/2 can be done in O(n) time.

12. [H] Write the sorting routines (bubble, insertion, selection, quick and merge sorts) for linked lists. Each routine should have the same time complexity as the corresponding routine on arrays.

13. Consider the Tower of Hanoi problem of Exercise set II. Solve the problem using the algorithm that first recursively moves the top n-1 disks from Peg A to Peg C using Peg B as an auxiliary location, then moves the largest disk from Peg A to Peg B, and finally moves the n-1 disks from Peg C to Peg B using Peg A as an auxiliary location. Let T(n) denote the number of disk movements done by the algorithm for n disks.
    1. Show that T(n) satisfies the following recurrence:

          T(1) = 1,
          T(n) = 2T(n-1) + 1 for n >= 2.
       

    2. Prove that T(n) = 2ⁿ - 1 for all n >= 1.
    3. [HM] Argue that any algorithm that solves the Tower of Hanoi problem must make at least 2ⁿ - 1 disk movements. (Hint: Consider the instance when the largest disk is removed from Peg A.)

14. Compare the running times of the insertion and deletion functions in our implementations of the ordered list, stack and queue ADTs. Express the running time in terms of the current size n (number of elements) of the list (or stack or queue).

15. [H²] In this exercise we plan to compute the binomial coefficient C(n,k). Several algorithms are proposed to that effect. These algorithms vary widely in their time complexities ranging from polynomial to truly exponential.
    1. We know that binomial coefficients satisfy the recurrence relation:

          C(n,k) = C(n-1,k) + C(n-1,k-1)
       

       for suitable values of n,k. Write a recursive function that straightaway uses this recurrence relation. Use suitable boundary conditions so that recursion eventually terminates.
    2. Deduce that the running time of the recursive algorithm of Part a) is exponential and not polynomial in n. For computing the running time, take k <= n.
    3. Use a two-dimensional auxiliary array to keep track of the pairs (m,j) for which C(m,j) has already been computed. If the value is available, replace a recursive call for computing C(m,j) by reading the value from the auxiliary array. This technique is known as memoization.
    4. Deduce that the running time of the recursive routine with memoization is polynomial in n.
    5. Write an iterative routine that generates the Pascal triangle in the following order: C(0,0), C(1,0), C(1,1), C(2,0), C(2,1), C(2,2), ... till the value of C(n,k) is computed. The top-down algorithm of Part a) recomputes many C(m,j) values multiple times. The bottom-up technique of this part is an example of dynamic programming.
    6. Deduce that the iterative algorithm of Part e) runs in time polynomial in n.
    7. Use the formula

          C(n,k) = n(n-1)...(n-k+1) / k!
       

       to compute the value of C(n,k).
    8. Argue that the running time of the algorithm of Part g) is polynomial in n.
    9. Compare the space complexities of the above four algorithms.

16. Suppose we want to compute the transpose of a matrix A and store the result in A itself. We do not assume A to be necessarily a square matrix.
    1. Write a function that takes an m x n matrix A as input, computes in a local matrix B the transpose of A and finally copies B back to A. What is the space complexity of this function?
    2. [H] Write a function that computes A^t in A using only a constant amount of additional storage.

17. Write a function that takes a square matrix A as input and computes in A itself the matrix A - A^t using only O(1) additional storage. (Hint: The matrix A - A^t is anti-symmetric, i.e., its (j,i)-th element is the negative of its (i,j)-th element.)

18. Let A be an n x n matrix.
    1. Write a function that converts A to row-reduced echelon form in O(n³) time using elementary row operations only.
    2. Write a function that computes the determinant of A in O(n³) time.

19. Write a function that computes the rank of an n x n matrix in O(n³) time.

20. Write a function that inverts an n x n matrix in O(n³) time.

21. Write a function that, given a square system

       Ax = b
    

    of linear equations, determines a solution for x, provided that the system is solvable. Your function should run in a time polynomial in the size (number of variables or equations) of the system. Your function should handle underdetermined (but consistent) systems, i.e., systems that have multiple solutions.

22. In this exercise a sparse matrix denotes a square matrix having only few (constant numbers of) non-zero elements in each row.
    1. Define a data type for storing a sparse matrix.
    2. Write a function that adds two n x n sparse matrices in O(n) time.
    3. [H] Write a function that multiplies two n x n sparse matrices in O(n²) time.

    Notice that the complexities of addition and multiplication of dense (non-sparse) n x n matrices are O(n²) and O(n³) respectively. The sparse representation brings down these complexity figures.

---

Course home