/sparse-matrices-addition-and-sub-matrices

A program that applies some functions on sparse matrices. First addition between two sparse matrices and secondly finding any 2x2 sub-matrix in which the sum of all 4 elements are greater than a variable c.

Primary LanguageC++MIT LicenseMIT

A C++ Project

This is a simple C++ project from my early days as a Computer Science student

This programm was created for the second semester class Data Structures and is one of two such simple C++ programms neccessary to pass the class

Description of project (2 exercises)

Exercise one is addition of two sparse tables / matrices. The implementation of the addition of tables should have a time complexity of Θ(nA + nB) where nA and nB are the number of non-zero elements of tables A and B. Also I minimize the total space necessary for implementing the addition of tables. Ideally, this program should use Θ(nC) space where nC is the number of non-zero elements of the result table C. Finally, the program prints table C in its two-dimensional form, including its zero elements.

Exercise two is a program that returns a 2X2 sub table (if any) from table A, whose sum of elements is greater than a variable c. For example if c = 80 then the program should return the sub array
[0 20]
[30 40]

Implementations (2 ways)

i. The first implementation uses linked-lists to reduce size and time complexity
ii. The second implementation uses 2D arrays

Functionality

  1. User can choose to run between the two exercises for both implementations
  2. User can choose betwwen randomly or manually creating arrays for both exercises for both implementations

About this project

  • The comments to make the code understandable, are within the archives
  • This program was written in CodeBlocks
  • This repository was created to show the variety of the work I did and experience I gained as a student