Assignment02 _ Technical Report

Implementation and Analysis of Sparse Matrix and 3D Array Operations

• Course: Data Structures
• StudentID: 2466044
• Author: LEE SIEUN
• Date: 2025-09-27
• Repository(private): 2025-Data-Structures Repository/ 02-Assignment

Assignment Goals

• Implementation of sparse matrix representation and operations
  • (e.g., transpose, sort in row-wise manner, sparse matrix to dense matrix form).
• Implementation of dynamic 3D array allocation using malloc and performing addition.

---

#1. Introduction(Logic)

1.1 Theoretical Background

1.1.1 Why sparse matrices are needed (to save memory)?

Sparse Matrix is a matrix in which most of the elements are zero.
If all elements of such a matrix are stored, a large amount of memory is wasted.
Therefore, it is more efficient to use a sparse matrix representation that stores only the non-zero elements.
A common approach is the triple array representation, where each entry consists of (row, col, value) with value being non-zero.

1.1.2 Why 3D dynamic allocation is useful (flexibility in handling multidimensional data)?

Dynamic memory allocation allows us to allocate memory at runtime using functions such as malloc.

3D dynamic allocation provides flexibility in managing multidimensional data, making it possible to create, manipulate, and deallocate arrays of arbitrary dimensions as needed.

---

#2. Problem Definition

In this assignment, two different implementations are required:

• Sparse Matrix Transpose:
  Implement a sparse matrix representation that stores only non-zero elements using a triple array structure (row, col, value).
  Then, perform a transpose operation on the given sparse matrix and print both the original and the transposed matrices in dense form to verify correctness.
• 3D Dynamic Array Allocation and Addition:
  Implement a function mem_alloc_3D_double to dynamically allocate a three-dimensional array of type double.
  Using this function, define two 3D arrays A and B, perform element-wise addition to obtain a result array, and finally deallocate the memory after use.

---

#3. Algorithm and Data Structure

• Sparse Matrix:
  • Data structure design (struct element {row, col, value})
  • Representation as an array of triples
  • Algorithm for transpose (time complexity O(terms))
• 3D Array with malloc:
  • Memory allocation strategy with triple pointers (double***)
  • Nested loops for allocation and deallocation
  • Algorithm for matrix addition

---

4. Implementation

• Programming environment : C language, Visual Studio 2022
• Key code snippets
  • SparseMatrix
    The element structure stores the row, column, and value of each non-zero entry, while the SparseMatrix structure holds all non-zero elements (terms) along with the number of rows and columns.
    • Transpose: The transpose function iterates only through non-zero elements, swapping the row and col fields. A `mergeSort` is then applied to maintain proper order, allowing an efficient transpose operation.
    • Dense Matrix Conversion: The denseMatrix function converts a SparseMatrix back to a regular 2D array. It first initializes all entries to 0, then fills in the values of the non-zero elements.

typedef struct {
    int row;
    int col;
    int value;
} element;

typedef struct {
    element data[MAX_TERMS];
    int rows;
    int cols;
    int terms;
} SparseMatrix;

SparseMatrix transpose(SparseMatrix B) {
    SparseMatrix A=B;
    A.rows = B.cols;
    A.cols = B.rows;
    for (int i = 0; i < A.terms; i++) {
        swap(&A.data[i].row, &A.data[i].col);
    }

    element tmp[MAX_TERMS];
    mergeSort(A.data, 0, A.terms - 1, tmp);

    return A;

}


int** denseMatrix(SparseMatrix B) {
    int** dense = (int**)malloc(sizeof(int*) * B.rows);
    for (int i = 0; i < B.rows; i++)
        dense[i] = (int*)malloc(sizeof(int) * B.cols);

    // initialize 0
    for (int i = 0; i < B.rows; i++)
        for (int j = 0; j < B.cols; j++)
            dense[i][j] = 0;

    // Assigning values from SparseMatrix
    for (int k = 0; k < B.terms; k++)
        dense[B.data[k].row][B.data[k].col] = B.data[k].value;

    return dense;
}

• 3D Array with malloc - MemoryAllocate, 3D array addition
  The memoryAllocate function dynamically allocates a 3D array of size x·y·z. Memory is allocated sequentially for each dimension. After usage, allocated memory is freed to prevent memory leaks.
  • Element-wise Addition: The addition3DArray function performs element-wise addition of two 3D arrays. Since arrays in C are passed by reference, operations inside the function directly modify the original arrays, ensuring that the result array in the main function is updated without returning a new pointer.
  • Validation: The confirmPrint function prints the contents of a 3D array for verification purposes.

int ***memoryAllocate(int x, int y, int z) {
// Dynamically allocates a 3D array of integers
    int ***array = malloc(x * sizeof(int **));
    for (int i = 0; i < x; i++) {
        array[i] = malloc(y * sizeof(int *));
        for (int j = 0; j < y; j++) {
            array[i][j] = malloc(z * sizeof(int));
        }
    }
    return array;
}

double*** addition3DArray(double*** A, double*** B, double*** C,int x, int y, int z) {
    // Performs element-wise addition of two 3D arrays
    for (int i = 0; i < x; i++) {
        for (int j = 0; j < y; j++) {
            for (int k = 0; k < z; k++) {
                C[i][j][k] = A[i][j][k] + B[i][j][k];
            }
        }
    }
    return C;
}

void deallocate(double*** A,int x,int y) {
// Frees all dynamically allocated memory for the 3D array
    for (int i = 0; i < x; i++) {
        for (int j = 0; j < y; j++) {
            free(A[i][j]);
        }
        free(A[i]);
    }
    free(A);

}

void confirmPrint(double*** A, int x, int y, int z) {
    for (int i = 0; i < x; i++) {
        printf("Matrix %d:\n", i);
        for (int j = 0; j < y; j++) {
            for (int k = 0; k < z; k++)
                printf("%lf ", A[i][j][k]);
            printf("\n");
        }
        printf("\n");
    }
}

---

5. Results and Analysis

• Sparse Matrix
  The output (right) corresponds to the input (left). Dense matrices are shown as standard 2D arrays, while sparse matrices are displayed using the (row, col) = value format.
  • Verification: Small example matrices confirmed that both representations produced the same results.

Input data/ Output upper is Dense Matrix (dense ver) lower is SparseMatrix (with (row, col) = val format)

Memory efficiency comparison (sparse vs. dense).

Sparse matrices save significant memory when most elements are zero. Dense matrices, on the other hand, store all elements, leading to potential waste of memory. The difference becomes more noticeable as the number of zero elements increases.

• *3DArray Memory Allocation
  *The 3D array addition results were successfully validated using the confirmPrint function.

• whole time complexity → O(terms+terms⋅log⁡terms) (in terms of memory)
  • SparseMatrix → O(terms)
  • transpose(B) → O(terms⋅log⁡terms)
  • denseMatrix(B) → O(n)
  • denseMatrix(A) → O(n)
• 3D array addition → O(x·y·z) ... O(n³)

#6. My Learning Points

This assignment provided a chance to implement and gain a deeper understanding of merge sort. Although the sparse matrix implementation involved using two structures, which was initially a bit confusing, I managed to complete it successfully with guidance from the lecture slides.
Additionally, I learned that arrays in C are passed by reference, so operations inside functions modify the original arrays directly. This was particularly helpful when performing element-wise addition on 3D arrays.

---

Appendix

• MyGitHub Repository : https://github.com/sihyes/2025-Data-Structures
• About MergeSort(, my Koean) : https://sihyes.tistory.com/113