Exercise set II

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. Write functions to compute the following:
   1. The area of a circle whose diameter is supplied as an argument.
   2. The volume of a 3-dimensional sphere whose surface area is given as an argument.
   3. The area of an ellipse for which the lengths of the major and minor axes are given as arguments.
   4. Given the coordinates of three distinct points in the x-y plane, the radius of the circle circumscribing the three points. Your function should return -1 if the three given points are collinear.
   5. Given a positive integer n, the sum of squares of all (positive) proper divisors of n.
   6. Given integers n>=0 and b>1, the expansion of n in base b. (Example: (987654321)_10 = (4,38,92,23,114)_123.)
   7. Given n and an array of n positive floating point numbers, the geometric mean of the elements of the array.

2. Write functions to perform the following tasks:
   • Check if a positive integer (provided as parameter) is prime.
   • Check if a positive integer (provided as parameter) is composite.
   • Return the sum S₇(n) of the 7-ary digits of a positive integer n (supplied as parameter).

   Use the above functions to find out the smallest positive integer i for which S₇(p_i) is composite, where p_i is the i-th prime. Also print the prime p_i.

   Note: 1 is neither prime nor composite. The sequence of primes is denoted by p₁=2, p₂=3, p₃=5, p₄=7, p₅=11, ...

   As an illustrative example for this exercise consider the 31-st prime p₃₁ = 127 that expands in base 7 as

      127 = 2 x 72 + 4 x 7 + 1, 
   

   i.e., the 7-ary expansion of 127 is 241 and therefore

      S7(127) = 2 + 4 + 1 = 7, 
   

   which is prime.

3. Write a function that, given two points (x1,y1) and (x2,y2) in the plane, returns the distance between the points.

   Write another function that computes the radius of the circle

      x2 + y2 + ax + by + c
   

   defined by the triple (a,b,c). Note that for some values of (a,b,c) this radius is not defined. In that case your function should return some negative value.

   Input two triples (a1,b1,c1) and (a2,b2,c2) so as to define two circles. Use the above two functions to determine which of the following cases occurs:

   • One or both of the circles is/are undefined.
   • The two circles touch (i.e., meet at exactly one point).
   • The two circles intersect (at two points).
   • The two circles do not intersect at all.

4. [M] Use the principle of mathematical induction to prove the following assertions:
   1. x²ⁿ⁺¹+y²ⁿ⁺¹ is divisible by x+y for all n in N₀.
   2. 1/sqrt(1) + 1/sqrt(2) + ... + 1/sqrt(n) > 2(sqrt(n+1) - 1) for all n in N.
   3. F₁² + F₂² + ... + F_n² = F_nF_n+1 for all n in N₀, where F_n denotes the n-the Fibonacci number.
   4. H₁ + H₂ + ... + H_n = (n+1)H_n - n for all n in N₀, where H_n denotes the n-th harmonic number.

5. [M] Find the flaw in the following proof:

   Theorem:  All horses are of the same color.

   Proof  Let there be n horses. We proceed by induction on n. If n=1, there is nothing to prove. So assume that n>1 and that the theorem holds for any group of n-1 horses. From the given n horses discard one, say the first one. Then all the remaining n-1 horses are of the same color by the induction hypothesis. Now put the first horse back and discard another, say the last one. Then the first n-1 horses have the same color again by the induction hypothesis. So all the n horses must have the same color as the ones that were not discarded either time. QED

6. Find a loop invariant for each of the following loops:

   a.  int n, x, y, t;
   
       n = 0;
       x = 1 + rand() % 9;
       y = 1 + rand() % 9;
       while (n < 10) {
          t = 1 + rand() % 9;
          x *= t;
          y /= t;
          ++n;
       }
   
   b.  #define NITER 100
   
       double x, s, t;
       int i;
   
       i = 0; s = t = 1;
       do {
         ++i;
         t /= (double)i;
         s += t;
       } while (i < NITER);
   
   c.  #define NITER 10
       int i;
       double A[NITER] = {1.0/2, 1.0/3, 1.0/5, 1.0/7, 1.0/11,
                          1.0/13, 1.0/17, 1.0/19, 1.0/23, 1.0/29};
   
       for (i=1; i<NITER; ++i) A[i] += A[i-1];
   

7. [HM] Consider the following puzzle given in pseudocode:

      Let n be an odd positive integer.
      Initialize C to the collection of integers 1,2,...,2n.
      while (C contains two or more elements) {
         Randomly choose two elements from the collection, call them a and b.
         Remove these elements from C.
         Add the absolute difference |a-b| to C.
      }
   

   For every iteration of the loop, two elements are removed and one element is added, so the size of the collection reduces by 1. After 2n-1 iterations the collection contains a single integer, call it t, and the loop terminates. Prove that t is odd. (Hint: Try to locate a delicate loop invariant.)

8. Determine what each of the following foomatic functions computes:

   a.  unsigned int foo1 ( unsigned int n )
       {
          unsigned int t = 0;
   
          while (n > 0) {
             if (n % 2 == 1) ++t;
             n = n / 2;
          }
          return t;
       }
   
   b.  unsigned int foo2 ( unsigned int n )
       {
          unsigned int t = 0;
   
          while (n > 0) {
             if (n & 1) ++t;
             n >>= 1;
          }
          return t;
      }
   
   c.  double foo3 ( double a , unsigned int n )
       {
          double s, t;
   
          s = 0;
          t = 1;
          while (n > 0) {
             s += t;
             t *= a;
             --n;
          }
          return s;
       }
   
   d.  double foo4 ( float A[] , int n )
       {
          float s, t;
   
          s = t = 0;
          for (i=0; i<n; ++i) {
             s += A[i];
             t += A[i] * A[i];
          }
          return (t/n)-(s/n)*(s/n);
       }
   
   e.  int foo5 ( unsigned int n )
       {
          if (n == 0) return 0;
          return 3*n*(n-1) + foo5(n-1) + 1;
       }
   
   f.  int foo6 ( char A[] , unsigned int n )
       {
          int t;
   
          if (n == 0) return 0;
          t = foo6(A,n-1);
          if ( ((A[n-1]>='a') && (A[n-1]<='z')) ||
               ((A[n-1]>='A') && (A[n-1]<='Z')) ||
               ((A[n-1]>='0') && (A[n-1]<='9')) )
             ++t;
          return t;
       }
   
   g.  int foo7 ( unsigned int a , unsigned int b )
       {
          if ((a == 0) || (b == 0)) return 0;
          return a * b / bar7(a,b);
       }
   
       int bar7 ( unsigned int a , unsigned int b )
       {
          if (b == 0) return a;
          return bar7(b,a%b);
       }
   
   h.  int foo8 ( unsigned int n )
       [
          if (n == 0) return 0;
          if (n & 1) return -1;
          return 1 + bar8(n-1);
       }
   
       int bar8 ( int n )
       {
          if (!(n & 1)) return -2;
          return 2 + foo8(n-1);
       }
   

9. [HM] Prove that the following function correctly computes the number of trailing 0's in the decimal representation of n! (factorial n).

      int bar ( unsigned int n )
      {
         int t = 0;
   
         while (n > 0) {
            n /= 5;
            t += n;
         }
         return t;
      }
   

10. For k in N we have

       a2k   = (ak)2, and
       a2k+1 = (ak)2 x a.
    

    Use this observation to write a recursive function that, given a real number a and a non-negative integer n, computes the power aⁿ.

11. Write a recursive function that computes the binomial coefficient C(n,r) using the inductive definition:

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

    for suitable values of n and r. Supply appropriate boundary conditions.

12. Define a sequence G_n as:

    Gn =

    0 1 2 Gn-1 + Gn-2 + Gn-3

    if n = 0, if n = 1, if n = 2, if n >= 3.

    1. Write an iterative function for the computation of G_n for a given n.
    2. Write a recursive function for the computation of G_n for a given n.
    3. [H] Write an efficient recursive function for the computation of G_n for a given n. Here efficiency means recursive invocation of the function for no more than n times.

13. Consider the sequence of integers given by:

       a1 = 1,
       a2 = 1,
       an = 6an-2 - an-1 for n >= 3.
    

    1. Write a recursive function to compute a₂₀.
    2. Write an iterative function to compute a₂₀.
    3. Suppose that a mathematician tells you that

          an = (2n+1 + (-3)n-1)/5 for all n>=1.
       

       Use this formula to compute a₂₀.

       Compare the timings of these three approaches for computing a₂₀. In order to measure time, use the built-in function clock() defined in <time.h>.

14. Consider three sequences of integers defined recursively as follows:

       a0 = 0
       a1 = 1
       an = a[n/3] - 2bn-2 + cn  for n >= 2
    
       b0 = -1
       b1 = 0
       b2 = 1
       bn = n - an-1 + cn-2 - bn-3  for n >= 3
    
       c0 = 1
       cn = bn - 3c[n/2] + 5  for n >= 1
    

    Here for a real number x the notation [x] stands for the largest integer less than or equal to x. For example, [3]=3, [3.1416]=3, [0.1416]=0, [-1.1416]=-2, [-3]=-3, [5/3]=1, [-5/3]=-2, etc. For this exercise you need consider x>=0 only, in which case [x] can be viewed as the integral part of x.

    1. Write three mutually recursive functions for computing a_n, b_n and c_n.
    2. Compute a₂₅. Count the total number of times a_i, b_i and c_i are computed for i=0,...,25 (that is, the corresponding functions are called with argument i) during the computation of a₂₅.
    3. Compute b₂₅. Count the total number of times a_i, b_i and c_i are computed for i=0,...,25 during the computation of b₂₅.
    4. Compute c₂₅. Count the total number of times a_i, b_i and c_i are computed for i=0,...,25 during the computation of c₂₅.
    5. Write an iterative version of the mutually recursive procedure. Maintain three arrays a, b and c each of size 26. Use the boundary conditions (values for a₀, a₁, b₀ etc.) to initialize. Then use the recursive definition to update the a, b and c values "simultaneously". In this method if some value (say, a_i) is once computed, it is stored in the appropriate array location for all subsequent uses. This saves the time for recalculating the same value again and again.
    6. Compute the values a₂₅, b₂₅ and c₂₅ using the iterative procedure.

15. [M] What is wrong in the following mutually recursive definition of three sequences a_n, b_n and c_n?

       a0 = 1.
       an = an-1 + bn for n >= 1.
    
       b0 = 2.
       bn = bn-1 + cn for n >= 1.
    
       c0 = -3.
       cn = cn-1 + an for n >= 1.
    

16. Two frogs are sitting at the bottom of a flight of 10 steps and debating in how many ways then can jump up the stairs. They can jump one, two or three steps at once. For example, they can cover the 10 steps by jumping (3,3,3,1) or (2,3,2,1,2) or other suitable combinations of steps. Their mathematics is not very strong and they approach you for help in order to find out the total number of possibilities they have to reach the top. Please provide them with a general solution (not only for 10 but for general n steps) in the form of a C function. Note that the order of the steps is important here, i.e., (3,3,3,1) is treated distinct from (1,3,3,3) for example.

17. Suppose we want to compute the product a₀ x a₁ x ... x a_n of n+1 numbers. Since multiplication is associative, we can insert parentheses in any order in order to completely specify the sequence of multiplications. For example, for n=3 we can parenthesize a₀ x a₁ x a₂ x a₃ in the following five ways:

       a0 x (a1 x (a2 x a3))
       a0 x ((a1 x a2) x a3)
       (a0 x a1) x (a2 x a3)
       (a0 x (a1 x a2)) x a3
       ((a0 x a1) x a2) x a3
    

    The number of ways in which n+1 numbers can be multiplied is denoted by C_n and is called the n-th Catalan number.

    1. [HM] Show that Catalan numbers can be recursively defined as follows:

          C0 = 1,
          C1 = 1, and
          Cn = C0Cn-1 + C1Cn-2 + ... + Cn-2C1 + Cn-1C0 for n>=2.
       

       (Hint: Classify a multiplication sequence based on the last multiplication.)
    2. Write an iterative function to compute C_n for a given n. (Remark: The computation of C_n requires all the previous values C₀,C₁,...,C_n-1. So you are required to store Catalan numbers in an array.)
    3. Write a recursive function to compute C_n.
    4. [H] Write an efficient recursive function to compute C_n. Here efficiency means that each C_i is to be computed only once in the entire sequence of recursive calls.

18. [HM] In this exercise we work with permutations of 1,2,...,n.
    1. Write a recursive function that prints all permutations of 1,2,...,n with each permutation printed only once.
    2. [H²] Write an iterative function that prints all permutations of 1,2,...,n with each permutation printed only once.
    3. A permutation p = a₁,a₂,...,a_n of 1,2,...,n can be treated as a function

          p : {1,2,...,n} --> {1,2,...,n}
       

       with p(i)=a_i for all i=1,2,...,n. If p(b₁)=b₂, p(b₂)=b₃, ..., p(b_k-1)=b_k and p(b_k)=b₁, we say that (b₁,b₂,...,b_k) is a cycle of length k in p. A permutation can be written as a collection of pairwise disjoint cycles. For example, consider the permutation p of 1,2,...,10:

          i    :   1  2  3  4  5  6  7  8  9 10
          p(i) :   5  3  6  4 10  7  9  1  2  8
       

       The cycle decomposition of this p is (1,5,10,8)(2,3,6,7,9)(4). Write a function that, given a positive integer n and an array holding a permutation p of 1,2,...,n, prints the cycle decomposition of p.

    4. Let p be a permutation of 1,2,...,n. If p(i)=i, then i is called a fixed point of p. A permutation p without any fixed point is called a derangement. Write a function that, upon input n, computes the number of derangements of 1,2,...,n.

19. [H] Tower of Hanoi: There are three pegs A,B,C. Initially, Peg A contains n disks (with holes at their centers). The disks have radiuses 1,2,3,...,n and are arranged in Peg A in increasing sizes from top to bottom, i.e., the disk of radius 1 is at the top, the disk of radius 2 is just below it, ..., the disk of radius n is at the bottom. Your task is to move the disks from Peg A to Peg B in such a way that you are never allowed to move a larger disk on the top of a smaller disk. You may use Peg C as an auxiliary location for the transfer. Write a recursive function by which you can perform this transfer. Your function should print all disk movements.

    (Hint: First move the top n-1 disks from Peg A to Peg C using Peg B as an auxiliary location. Then move the largest disk from Peg A to Peg B. Finally, move the n-1 disks from Peg C to Peg B using Peg A as an auxiliary location.)

20. In this exercise you are asked to build a function library on polynomial arithmetic. Assume that polynomials with real coefficients need only be considered.
    1. First chalk out a way to represent a polynomial in an array. You may restrict the degree of a polynomial to be less than some bound, say 100.
    2. Write functions to perform the following operations on polynomials. All the input and output polynomials should be passed as arguments to the functions. Each function is allowed to return nothing or an integer value. Your functions should allow the possibility to store the output in one of the input polynomials.
       • Initialization of a polynomial to the zero polynomial.
       • Addition of two polynomials.
       • Difference of two polynomials.
       • Multiplication of two polynomials.
       • Evaluation of a polynomial at an integer point.
       • Derivative of a polynomial.
       • Integral of a polynomial. Fix the constant of integration using two real values a,b, where b specifies the value that the output polynomial would assume if evaluated at a.
       • Scanning of a polynomial.
       • Printing of a polynomial.

21. The built-in random number generator rand() returns an integer value between 0 and RAND_MAX. You may assume that all these values are equally likely (uniform distribution). Use this built-in random number generator to generate the following:
    1. A signed random integer between -RAND_MAX and RAND_MAX.
    2. A random integer between 0 and 999.
    3. A random integer between 100 and 999.
    4. A random integer between -999 and 999.
    5. A random floating point number between 0 and 1.
    6. [HM] On input n (a positive integer) and p (a real number between 0 and 1), a random integer t between 0 and n with probability

          C(n,t)pt(1-p)n-t,
       

       where C(n,t) stands for the binomial coefficient.
    7. [H²M] A random floating point number t between 0 and 1 following the continuous probability density function

       p(t) =

       4t 4 - 4t

       if 0 <= t <= 1/2,   if 1/2 < t <= 1.

    8. [H³M] A random non-negative floating point number t with the continuous probability density function

          e-t for all t >= 0.
       

22. [H] Write an efficient program to sort a file of integers. The input file is a large piece of data (say 100,000 integers), whereas the maximum size of an array that can be used inside the program is 1000 (one thousand) integers. Note that you are not allowed to read from and write to the same file simultaneously. Generate the input file of numbers using the built-in random number generator rand().

23. [M] Formally establish the correctness of the sorting algorithms discussed in the notes (bubble, insertion, selection, merge and quick sort). (Hint: Use induction on the length of the array.)

24. Counting sort: Assume that you want to sort an array A of n integers each known to be in the range 0,1,...,99. Use an array B of size 100 to count how many times each k in the range 0,1,...,99 occurs in A. Then use these counts to rewrite the array A in the sorted order. Your program should use only a number of operations proportional to the size n of A.

25. Odd-even merging: This exercise explores a recursive method of merging two sorted arrays A = (a₀,a₁,...,a_n-1) and B = (b₀,b₁,...,b_n-1). For simplicity assume that n is a power of 2. If n=1, then comparing a₀ with b₀ suffices. So assume that n>1. Recursively merge the sorted subarrays A_odd = (a₁,a₃,a₅,...) and B_odd = (b₁,b₃,b₅,...). Also recursively merge the subarrays A_even = (a₀,a₂,a₄,...) and B_even = (b₀,b₂,b₄,...). Call the resulting sorted arrays X = (x₀,x₁,...,x_n-1) and Y = (y₀,y₁,...,y_n-1) respectively.
    1. Argue that X and Y can be merged by comparing x_i with y_i+1 for i=0,1,...,n-2.
    2. Write a recursive function implementing this odd-even merging step.

26. Write a program for printing the elements of a two-dimensional array (not necessarily square) in each of the following orders:
    1. To-and-fro row-major order.
    2. Diagonal-major order.
    3. Spiral order.

    Notice that the diagonal-major order makes enough sense for square matrices. For general mxn matrices, take the length of each diagonal to be m and treat the elements as organized in a wrap-around fashion. For example, consider the 4x5 matrix:

    1	2	3	4	5
    6	7	8	9	10
    11	12	13	14	15
    16	17	18	19	20

    The listing of its elements in the to-and-fro row-major order is:

       1 2 3 4 5 10 9 8 7 6 11 12 13 14 15 20 19 18 17 16
    

    The listing of the elements in the diagonal-major order is:

       1 7 13 19 2 8 14 20 3 9 15 16 4 10 11 17 5 6 12 18
    

    The listing of the elements in the spiral order is:

       1 2 3 4 5 10 15 20 19 18 17 16 11 6 7 8 9 14 13 12
    

27. Stirling numbers s(n,k) of the first kind are non-negative integers defined recursively as:

       s(0,0) = 1,
       s(n,0) = 0 for n > 0,
       s(n,k) = 0 for k > n,
       s(n,k) = (n-1)s(n-1,k) + s(n-1,k-1) for n > 0 and 0 < k <= n.
    

    1. Write a recursive function to compute s(n,k).
    2. Write an iterative function to compute s(n,k). You should better maintain a two-dimensional array and compute the values s(n,k) in a particular order of the pair (n,k).

28. Stirling numbers S(n,k) of the second kind are non-negative integers defined recursively as:

       S(0,0) = 1,
       S(n,0) = 0 for n > 0,
       S(n,k) = 0 for k > n,
       S(n,k) = k S(n-1,k) + S(n-1,k-1) for n > 0 and 0 < k <= n.
    

    1. Write a recursive function to compute S(n,k).
    2. Write an iterative function to compute S(n,k).

29. A run in a permutation is a maximal monotonic increasing sequence of adjacent elements in the permutation. For example, the runs in

       257183496
    

    are

       257, 18, 349, 6.
    

    Every run (except the last) is followed by a descent (also called a fall). For example, in the above permutation the descents are 71, 83 and 96. If a permutation has exactly k+1 runs, then it has exactly k descents, and conversely. Let us denote by the notation

       <n,k>
    

    the number of permutations of 1,...,n with exactly k descents. The numbers <n,k> are called Eulerian numbers. All permutations of 1,2,3 and the runs in each permutation are shown below. This list gives us the values of <3,k>.

       Permutation      Runs     Number of runs     Number of descents
           123          123             1                   0
           132          13,2            2                   1
           213          2,13            2                   1
           231          23,1            2                   1
           312          3,12            2                   1
           321          3,2,1           3                   2
    
       <3,0> = 1
       <3,1> = 4
       <3,2> = 1
    

    It is known that the Eulerian numbers satisfy the following recurrence relation:

       <n,0> = 1.
       <n,k> = 0, if k >= n.
       <n,k> = (k+1)<n-1,k> + (n-k)<n-1,k-1>, otherwise.
    

    1. Write a recursive function to compute <n,k>.
    2. Write an iterative function to compute <n,k>.

30. In this exercise you are asked to build a function library on matrix arithmetic. Consider matrices (not necessarily square) with real entries.
    1. First chalk out a way to represent a matrix in a two-dimensional array. You may restrict the dimension of a matrix to be less than some bound, say 20.
    2. Write functions to perform the following operations on matrices. All the input and output matrices should be passed as arguments to the functions. Each function is allowed to return nothing or an integer value. You should also check that the dimensions of the input matrices are consistent for the operation. Your functions should allow the provision for the output matrix being the same as one of the input matrices.
       • Initialization of a matrix to the zero matrix of a given dimension.
       • Initialization of a matrix to the (square) identity matrix of a given dimension.
       • Addition of two matrices.
       • Difference of two matrices.
       • Multiplication of two matrices.
       • Inverse of a (square) matrix.
       • Rank of a matrix.
       • Scanning of a matrix.
       • Printing of a matrix.

31. Use your library of the previous exercise to solve a square system of linear equations. If the system is underdefined or inconsistent, your program should report failure.

32. [M] A square matrix A = (a_ij) is called symmetric if a_ij = a_ji for all indices i,j. A is called skew-symmetric if a_ij = -a_ji for all indices i,j with i != j. Write a function that, given a square matrix A, computes a symmetric matrix B and a skew-symmetric matrix C satisfying A = B + C.

---

Course home