Problem Set 4(Sparse Matrix)

Sparse Matrix:

Write an algorithm and the subsequent Python program to check whether the given matrix is sparse or not. A matrix is said to be a “Sparse” if the number  of zero entries  in the matrix,  is greater than or equal to the number  of non-zero entries. Otherwise it is  “Not sparse”. Check for boundary conditions and print 'Invalid input' when not satisfied.

Input Format:

The first line will contain the number of rows in the matrix, rows

The Second line will contain the number of columns in the matrix, cols

The next (rows * cols) lines will contain the elements of the matrix, entered row wise

Output Format:

Print either Sparse or Not sparse

Boundary Conditions:

Number of rows and columns > 0

Input:

Number of rows and columns and next rows*column number of elements

Processing:

result = []

temp = []

count_zero = 0

count_non_zero = 0

for i in range(rows):

    for j in range(columns):

        temp_element = int(input())

        if temp_element == 0:

            count_zero += 1

        else:

            count_non_zero += 1

        temp.insert(j,temp_element)

    result.append(temp)

    temp = []

           

Output:

Display whether the matrix is sparse or not sparse

Algorithm:

Step1. Initialize result and temp as empty lists

Step2. Get rows and columns as inputs.

Step3. Initialize count_zero and count_non_zero as zero

Step4. If one of rows or columns is less than 1 then display invalid input else proceed to Step5.

Step5. Initialize i as 0 and repeat the following steps till i is less than rows.

Step5.1 initialize j as 0 and repeat the following steps till j is less than columns.

Step5.1.1 get the i,jth element of the matrix as the input and store it in temp_element.

Step5.1.2 if temp_element is zero then increment count_zero by 1 else increment count_non_zero by 1.

Step5.1.3 insert temp_element into the jth position of temp

Step5.2 Append temp to result and reinitialize temp as an empty list

Step6. If count_zero is greater than or equal to count_non_zero display the Sparse else display Not sparse.

Step7. End

Program:

result = []

temp = []

rows = int(input())

columns = int(input())

count_zero = 0

count_non_zero = 0

if rows < 1 or columns < 1:

    print("invalid input")

else:

    for i in range(rows):

        for j in range(columns):

            temp_element = int(input())

            if temp_element == 0:

                count_zero += 1

            else:

                count_non_zero += 1

            temp.insert(j,temp_element)

        result.append(temp)

        temp = []

    if count_zero >= count_non_zero:

        print("Sparse")

    else:

        print("Not sparse")

Flowchart:

To edit this flowchart click on this