CS13002 PDS Lab, Spring 2003, Section 1/A

Assignment 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 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]