Assignment 5 Solution

$35.00 $30.80

Description

  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.

 

  1. 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.