$29
1. Let arrays X[1 : n] and Y [1 : n] describe a set of intervals (xi, yi), xi < yi, i = 1, ..., n. Two intervals (xi, yi) and (xj , yj ) overlap if:
xi ≤ xj ∧ xj ≤ yi ∨ xj ≤ xi ∧ xi ≤ yj .
Two overlapping intervals (xi, yi) and (xj , yj ) can be merged into one (xk, yk), where xk = min(xi, xj ) and yk = max(yi, yj ).
Write an integer Fortran function M erge(X, Y, n) which iteratively merges the overlapping intervals and returns the number of resulting, non-overlapping intervals (the merged intervals replace the original intervals in arrays X and Y ).
Also, write a Fortran program which reads the data, invokes M erge and prints the results.
2. A block–diagonal matrix is a square matrix in which all non-zero elements are in the form of disjoint submatrices (called blocks) on the main diagonal, as shown below (where nonzero elements are represented by asterisks):
*
*
*
0
0
0
0
0
0
*
*
*
0
0
0
0
0
0
*
*
*
0
0
0
0
0
0
0
0
0
*
*
*
*
0
0
0
0
0
*
*
*
*
0
0
0
0
0
*
*
*
*
0
0
0
0
0
*
*
*
*
0
0
0
0
0
0
0
0
0
*
*
0
0
0
0
0
0
0
*
*
Write an integer function BLOCKS(A,N,B) which checks if a real matrix A[1 : n, 1 : n] is block– diagonal and which returns the sizes of consecutive blocks in array B[1 : n] (for the example above the returned values of B are [3,4,2]). The value returned by the function is the number of blocks (i.e., 3 for the example above).
Also, write a Fortran program which reads the data, invokes Blocks and prints the results.
Hint: Start with the element A[1, 1] and, for consecutive values of k = 1, 2, · · · check if all elements k + 1 to n in the first k rows and the first k columns are equal to zero. If a nonzero element is found, increase k and repeat. When the first block is identified, repeat the same process starting from the next diagonal element, until the whole matrix A is checked.