Assignment 5 Solution

Description

1. Let arrays X[1 : n] and Y [1 : n] describe a set of intervals (x_i, y_i), x_i < y_i, i = 1, …, n. Two intervals (x_i, y_i) and (x_j , y_j ) overlap if:

x_i ≤ x_j ∧ x_j ≤ y_i ∨ x_j ≤ x_i ∧ x_i ≤ y_j .

Two overlapping intervals (x_i, y_i) and (x_j , y_j ) can be merged into one (x_k, y_k), where x_k = min(x_i, x_j ) and y_k = max(y_i, y_j ).

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.