## CS13002 PDS Lab, Spring 2003, Section 1/AAssignment 3

1. [Linear sequence]

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.

How to measure timings?

2. [Six points inside a circle]

Consider six distinct points in the X-Y plane. Read their coordinates from the terminal. Find out if there are any three of the input points, that are non-colinear and that have a circum-circle of radius greater than 1.

Hint: Write a routine that takes the coordinates of three distinct points and returns the radius of the circle circumscribing the three points. Your routine should reject (say, by returning -1), if the three input points are colinear.

Typical output

```Point 0 : (0.383754,0.016448)
Point 1 : (0.310564,0.196194)
Point 2 : (0.667872,0.454824)
Point 3 : (0.873062,0.614338)
Point 4 : (0.873176,0.553859)
Point 5 : (0.794014,0.283437)
Circum-radius of points 0, 1 and 2 is 0.268895
Circum-radius of points 0, 1 and 3 is 0.398951
Circum-radius of points 0, 1 and 4 is 0.369377
Circum-radius of points 0, 1 and 5 is 0.250142
Circum-radius of points 0, 2 and 4 is 0.699557
Circum-radius of points 0, 2 and 5 is 0.261631
Circum-radius of points 0, 3 and 4 is 0.572528
Circum-radius of points 0, 3 and 5 is 0.561090
Circum-radius of points 0, 4 and 5 is 0.558148