CS13002 PDS Lab, Spring 2003, Section 1/A

Assignment 3

1. [Linear sequence]
   
   Consider the sequence of integers given by

   a₁ = 1,
   a₂ = 1,
   a_n = 6a_n-2 - a_n-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

      a_n = (2ⁿ⁺¹ + (-3)^n-1)/5 for all n>=1.

      Use this formula to compute a₂₀.
      
      Compare the timings of these three approaches for computing a₂₀.
      
      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 3 is 1.175169  (BIG CIRCUM-RADIUS)
   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
   Circum-radius of points 1, 2 and 3 is 10.229454  (BIG CIRCUM-RADIUS)
   Circum-radius of points 1, 2 and 4 is 1.892223  (BIG CIRCUM-RADIUS)
   Circum-radius of points 1, 2 and 5 is 0.245637
   Circum-radius of points 1, 3 and 4 is 0.414770
   Circum-radius of points 1, 3 and 5 is 0.382621
   Circum-radius of points 1, 4 and 5 is 0.372621
   Circum-radius of points 2, 3 and 4 is 0.144148
   Circum-radius of points 2, 3 and 5 is 0.170165
   Circum-radius of points 2, 4 and 5 is 0.143332
   Circum-radius of points 3, 4 and 5 is 0.601605
   

[Course home] [Home]