## CSL 101 Introduction to Computers and Programming | ## Sem II 2007-08 |

## 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, H^{2}and H^{3}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.

- Write functions to compute the following:

- The area of a circle whose diameter is supplied as an argument.
- The volume of a 3-dimensional sphere whose surface area is given as an argument.
- The area of an ellipse for which the lengths of the major and minor axes are given as arguments.
- 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.- Given a positive integer n, the sum of squares of all (positive) proper divisors of n.
- Given integers n>=0 and b>1, the expansion of n in base b. (Example: (987654321)_10 = (4,38,92,23,114)_123.)
- Given n and an array of n positive floating point numbers, the geometric mean of the elements of the array.
- 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
Sof the 7-ary digits of a positive integer n (supplied as parameter)._{7}(n)Use the above functions to find out the smallest positive integer i for which

Sis composite, where_{7}(p_{i})pis the i-th prime. Also print the prime_{i}p._{i}

Note:1 is neither prime nor composite. The sequence of primes is denoted byp_{1}=2, p_{2}=3, p_{3}=5, p_{4}=7, p_{5}=11, ...As an illustrative example for this exercise consider the 31-st prime

p= 127 that expands in base 7 as_{31}127 = 2 x 7^{2}+ 4 x 7 + 1,i.e., the 7-ary expansion of 127 is 241 and therefore

Swhich is prime._{7}(127) = 2 + 4 + 1 = 7,- 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

xdefined 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.^{2}+ y^{2}+ ax + by + cInput 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.
- [M] Use the principle of mathematical induction to prove the following assertions:

- x
^{2n+1}+y^{2n+1}is divisible by x+y for all n inN._{0}- 1/sqrt(1) + 1/sqrt(2) +
...+ 1/sqrt(n) > 2(sqrt(n+1) - 1) for all n inN.- F
_{1}^{2}+ F_{2}^{2}+...+ F_{n}^{2}= F_{n}F_{n+1}for all n inN, where F_{0}_{n}denotes the n-the Fibonacci number.- H
_{1}+ H_{2}+...+ H_{n}= (n+1)H_{n}- n for all n inN, where H_{0}_{n}denotes the n-th harmonic number.- [M] Find the flaw in the following proof:

Theorem:All horses are of the same color.

ProofLet 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- [HM] Consider the following puzzle given in pseudocode:
Let n be anoddpositive 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.)- [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; }- For k in
Nwe havea^{2k }= (a^{k})^{2}, and a^{2k+1}= (a^{k})^{2}x a.Use this observation to write a recursive function that, given a real number

aand a non-negative integern, computes the powera.^{n}- 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.- Define a sequence G
_{n}as:

G_{n}= 0 1 2 G_{n-1}+ G_{n-2}+ G_{n-3} if n = 0, if n = 1, if n = 2, if n >= 3.

- Write an iterative function for the computation of G
_{n}for a given n.- Write a recursive function for the computation of G
_{n}for a given n.- [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.- Consider the sequence of integers given by:
a_{1}= 1, a_{2}= 1, a_{n}= 6a_{n-2}- a_{n-1}for n >= 3.

- Write a recursive function to compute a
_{20}.- Write an iterative function to compute a
_{20}.- Suppose that a mathematician tells you that
a_{n}= (2^{n+1}+ (-3)^{n-1})/5 for all n>=1.Use this formula to compute a

_{20}.Compare the timings of these three approaches for computing a

_{20}. In order to measure time, use the built-in functionclock()defined in<time.h>.- Consider three sequences of integers defined recursively as follows:
a_{0}= 0 a_{1}= 1 a_{n}= a_{[n/3]}- 2b_{n-2}+ c_{n}for n >= 2 b_{0}= -1 b_{1}= 0 b_{2}= 1 b_{n}= n - a_{n-1}+ c_{n-2}- b_{n-3}for n >= 3 c_{0}= 1 c_{n}= b_{n}- 3c_{[n/2]}+ 5 for n >= 1Here for a real number

xthe notation[x]stands for the largest integer less than or equal tox. 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 considerx>=0only, in which case[x]can be viewed as the integral part ofx.

- Write three mutually recursive functions for computing a
_{n}, b_{n}and c_{n}.- Compute a
_{25}. Count the total number of times a_{i}, b_{i}and c_{i}are computed fori=0,...,25(that is, the corresponding functions are called with argument i) during the computation of a_{25}.- Compute b
_{25}. Count the total number of times a_{i}, b_{i}and c_{i}are computed fori=0,...,25during the computation of b_{25}.- Compute c
_{25}. Count the total number of times a_{i}, b_{i}and c_{i}are computed fori=0,...,25during the computation of c_{25}.- 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
_{0}, a_{1}, b_{0}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.- Compute the values a
_{25}, b_{25}and c_{25}using the iterative procedure.- [M] What is wrong in the following mutually recursive definition of three sequences a
_{n}, b_{n}and c_{n}?a_{0}= 1. a_{n}= a_{n-1}+ b_{n}for n >= 1. b_{0}= 2. b_{n}= b_{n-1}+ c_{n}for n >= 1. c_{0}= -3. c_{n}= c_{n-1}+ a_{n}for n >= 1.- Suppose we want to compute the product a
_{0}x a_{1}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_{0}x a_{1}x a_{2}x a_{3}in the following five ways:a_{0}x (a_{1}x (a_{2}x a_{3})) a_{0}x ((a_{1}x a_{2}) x a_{3}) (a_{0}x a_{1}) x (a_{2}x a_{3}) (a_{0}x (a_{1}x a_{2})) x a_{3}((a_{0}x a_{1}) x a_{2}) x a_{3}The number of ways in which n+1 numbers can be multiplied is denoted by C

_{n}and is called the n-thCatalan number.

- [HM] Show that Catalan numbers can be recursively defined as follows:
C(Hint: Classify a multiplication sequence based on the last multiplication.)_{0}= 1, C_{1}= 1, and C_{n}= C_{0}C_{n-1}+ C_{1}C_{n-2}+ ... + C_{n-2}C_{1}+ C_{n-1}C_{0}for n>=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_{0},C_{1},...,C_{n-1}. So you are required to store Catalan numbers in an array.)- Write a recursive function to compute C
_{n}.- [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.- [HM] In this exercise we work with
permutationsof 1,2,...,n.

- Write a recursive function that prints all permutations of 1,2,
...,n with each permutation printed only once.- [H
^{2}] Write an iterative function that prints all permutations of 1,2,...,n with each permutation printed only once.- A permutation p = a
_{1},a_{2},...,a_{n}of 1,2,...,n can be treated as a functionp : {1,2,with p(i)=a...,n} --> {1,2,...,n}_{i}for all i=1,2,...,n. If p(b_{1})=b_{2}, p(b_{2})=b_{3},..., p(b_{k-1})=b_{k}and p(b_{k})=b_{1}, we say that (b_{1},b_{2},...,b_{k}) is acycleof 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 8The 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.- Let p be a permutation of 1,2,
...,n. If p(i)=i, then i is called afixed pointof p. A permutation p without any fixed point is called aderangement. Write a function that, upon input n, computes the number of derangements of 1,2,...,n.- In this exercise you are asked to build a function library on polynomial arithmetic. Assume that polynomials with real coefficients need only be considered.

- 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.
- 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.
- The built-in random number generator
rand()returns an integer value between 0 andRAND_MAX. You may assume that all these values are equally likely (uniform distribution). Use this built-in random number generator to generate the following:

- A signed random integer between
-RAND_MAXandRAND_MAX.- A random integer between 0 and 999.
- A random integer between 100 and 999.
- A random integer between -999 and 999.
- A random floating point number between 0 and 1.
- [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)pwhere^{t}(1-p)^{n-t},C(n,t)stands for the binomial coefficient.- [H
^{2}M] A random floating point number t between 0 and 1 following the continuous probability density function

p(t) =4t

4 - 4tif 0 <= t <= 1/2,

if 1/2 < t <= 1.- [H
^{3}M] A random non-negative floating point number t with the continuous probability density functione^{-t}for all t >= 0.- [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.)
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.Odd-even merging:This exercise explores a recursive method of merging two sorted arraysA = (aand_{0},a_{1},...,a_{n-1})B = (b. For simplicity assume that n is a power of 2. If n=1, then comparing_{0},b_{1},...,b_{n-1})awith_{0}bsuffices. So assume that n>1. Recursively merge the sorted subarrays_{0}Aand_{odd}= (a_{1},a_{3},a_{5},...)B. Also recursively merge the subarrays_{odd}= (b_{1},b_{3},b_{5},...)Aand_{even}= (a_{0},a_{2},a_{4},...)B. Call the resulting sorted arrays_{even}= (b_{0},b_{2},b_{4},...)X = (xand_{0},x_{1},...,x_{n-1})Y = (yrespectively._{0},y_{1},...,y_{n-1})

- Argue that X and Y can be merged by comparing
xwith_{i}yfor i=0,1,_{i+1}...,n-2.- Write a recursive function implementing this odd-even merging step.
- Write a program for printing the elements of a two-dimensional array (not necessarily square) in each of the following orders:

- To-and-fro row-major order.
- Diagonal-major order.
- 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 16The 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 18The 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 12Stirling numbers s(n,k) of the first kindare 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.

- Write a recursive function to compute s(n,k).
- 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).
Stirling numbers S(n,k) of the second kindare 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.

- Write a recursive function to compute S(n,k).
- Write an iterative function to compute S(n,k).
- A
runin a permutation is a maximal monotonic increasing sequence of adjacent elements in the permutation. For example, the runs in257183496are

257, 18, 349, 6.Every run (except the last) is followed by a

descent(also called afall). 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 calledEulerian 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> = 1It 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.

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