# Practice Problems

Acknowledgement: Prof Abhijit Das

Note: Students are encouraged to solve as many problems from this set as possible (not to be submitted). 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, H2 and H3 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 S7(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 S7(pi) is composite, where pi is the i-th prime. Also print the prime pi.

Note: 1 is neither prime nor composite. The sequence of primes is denoted by p1=2, p2=3, p3=5, p4=7, p5=11, ...

As an illustrative example for this exercise consider the 31-st prime p31 = 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. x2n+1+y2n+1 is divisible by x+y for all n in N0.
2. 1/sqrt(1) + 1/sqrt(2) + ... + 1/sqrt(n) > 2(sqrt(n+1) - 1) for all n in N.
3. F12 + F22 + ... + Fn2 = FnFn+1 for all n in N0, where Fn denotes the n-the Fibonacci number.
4. H1 + H2 + ... + Hn = (n+1)Hn - n for all n in N0, where Hn 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. [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.)

7. [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;
}
```

8. 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 an.

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

10. Define a sequence Gn 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 Gn for a given n.
2. Write a recursive function for the computation of Gn for a given n.
3. [H] Write an efficient recursive function for the computation of Gn for a given n. Here efficiency means recursive invocation of the function for no more than n times.

11. 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 a20.
2. Write an iterative function to compute a20.
3. Suppose that a mathematician tells you that
```   an = (2n+1 + (-3)n-1)/5 for all n>=1.
```

Use this formula to compute a20.

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

12. 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 an, bn and cn.
2. Compute a25. Count the total number of times ai, bi and ci are computed for i=0,...,25 (that is, the corresponding functions are called with argument i) during the computation of a25.
3. Compute b25. Count the total number of times ai, bi and ci are computed for i=0,...,25 during the computation of b25.
4. Compute c25. Count the total number of times ai, bi and ci are computed for i=0,...,25 during the computation of c25.
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 a0, a1, b0 etc.) to initialize. Then use the recursive definition to update the a, b and c values "simultaneously". In this method if some value (say, ai) 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 a25, b25 and c25 using the iterative procedure.

13. [M] What is wrong in the following mutually recursive definition of three sequences an, bn and cn?
```   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.
```

14. Suppose we want to compute the product a0 x a1 x ... x an 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 a0 x a1 x a2 x a3 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 Cn 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 Cn for a given n. (Remark: The computation of Cn requires all the previous values C0,C1,...,Cn-1. So you are required to store Catalan numbers in an array.)
3. Write a recursive function to compute Cn.
4. [H] Write an efficient recursive function to compute Cn. Here efficiency means that each Ci is to be computed only once in the entire sequence of recursive calls.

15. [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. [H2] Write an iterative function that prints all permutations of 1,2,...,n with each permutation printed only once.
3. A permutation p = a1,a2,...,an of 1,2,...,n can be treated as a function
```   p : {1,2,...,n} --> {1,2,...,n}
```
with p(i)=ai for all i=1,2,...,n. If p(b1)=b2, p(b2)=b3, ..., p(bk-1)=bk and p(bk)=b1, we say that (b1,b2,...,bk) 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.

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

17. 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. [H2M] A random floating point number t between 0 and 1 following the continuous probability density function
 p(t) = 4t4 - 4t if 0 <= t <= 1/2,  if 1/2 < t <= 1.
8. [H3M] A random non-negative floating point number t with the continuous probability density function
```   e-t for all t >= 0.
```

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

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

20. Odd-even merging: This exercise explores a recursive method of merging two sorted arrays A = (a0,a1,...,an-1) and B = (b0,b1,...,bn-1). For simplicity assume that n is a power of 2. If n=1, then comparing a0 with b0 suffices. So assume that n>1. Recursively merge the sorted subarrays Aodd = (a1,a3,a5,...) and Bodd = (b1,b3,b5,...). Also recursively merge the subarrays Aeven = (a0,a2,a4,...) and Beven = (b0,b2,b4,...). Call the resulting sorted arrays X = (x0,x1,...,xn-1) and Y = (y0,y1,...,yn-1) respectively.
1. Argue that X and Y can be merged by comparing xi with yi+1 for i=0,1,...,n-2.
2. Write a recursive function implementing this odd-even merging step.

21. 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
```

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

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

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