Tute 3, CSE2304, CSSE, Monash, Semester 1, 2004

Weeks 7 and 8, 19 to 30 April 2004

Class: Prepare your answers to the questions before the tute! It will probably not be possible to cover all questions unless the class has prepared them all in advance. (The online versions of the tutes may contain extra information and links.)

Tutors: (i) The purpose of the tutorials is not to solve the prac's! (ii) The purpose of the tutorials is to check answers, and to discuss particular sticking points, not to simply make answers available.

1. Given a sequence, x₁, x₂, ..., x_n, a subsequence is some (or all) of its elements, in the same order, e.g. x₂, x₄, x₅, x₈, say.
   A common subsequence of two sequences x₁, x₂, ..., x_n, and y₁, y₂, ..., y_m, is a sequence, z₁, z₂, ..., z_k, that is a subsequence of the x's and also of the y's.
   A longest common subsequence is a common subsequence that is as long as possible.
   Give C-code to find the length of a longest common subsequence: int LCS(int n, t x[], int m, t y[]).
   Note that the more similar the x-sequence and the y-sequence are, the longer is their LCS.

2. What is the time- and space-complexity of your answer to the previous question (best, average and worst cases)?

3. How many times are "base" and "body" executed for r(1000)?

   void r(int n)
        { if( n > 1 )
           { body;
             r(n/2);
           }
          else
             base;
        }
   

   Why?

4. Two intervals, [a,b] and [c,d], where a, b, c and d are floating-point numbers between 0.0 and 1.0 inclusive, a<=b and c<=d, can overlap in the following ways:

     1.  [a__________b]             2.     [a_______b]
             [c__________d]             [c_____d]
   
   
     3.  [a_________b]              4.       [a___b]
            [c__d]                      [c_____________d]
   

   You are working in a scientific laboratory where a long-running experiment is producing a sequence of intervals [i₁, j₁], [i₂, j₂], ..., [i_n, j_n]. For each interval, [i_m, j_m],  your colleagues need to know which of the earlier intervals,  [i_k, j_k]  k<m,  if any,  overlap with [i_m, j_m]. When m becomes large you expect the number of earlier intervals overlapping [i_m, j_m] to be <<m (much less than m) in most, but not all, cases. Note that n can be very large indeed, in the millions or even more, and you need an efficient solution.
   Is the problem easy or hard? Why? Outline a possible solution, i.e. algorithms and data-structures. (Do not give C code.) What is worst-case data for your solution? Why?