# Homework2

[Homework 2 is due on Jun 28 (Tuesday 11:59pm)]

Please choose any one of the following two problems for your homework 2:

## 1. Jumbo Numbers

A natural number takes on values 0, 1, 2, … and can be represented by an `int` or a few other numeric types in C++, all of which have a limit to how large a number they can store. On some systems (including ours) a `long int` is 8 bytes (64 bits), and the maximum value of an `unsigned long int` is 264-1, or 18,446,744,073,709,551,615. This is not large enough for many important purposes, like calculating the 1,000,000th Fibonacci number exactly.

Goal: We will therefore introduce a new numeric data type that can represent an arbitrarily large natural number.

Let’s call our new data type the `Jumbo`.

To accomplish the manipulation of large (`Jumbo`) numbers, create a class that (privately) stores an arbitrarily large sequence of digits. The public interface will allow a user to create `Jumbo` variables, read and write them, and add them together.

Let’s work in the decimal (base 10) system for this assignment.

In order to store very large natural numbers, the `Jumbo` class will have to dynamically allocate its private data. You have to define what happens when a `Jumbo` is copied from another `Jumbo` because you want to copy all the data, not just the pointer(s).

Here are a few reminders:

1. ``````Constructors and copy constructors:
Jumbo a(77); // creates a Jumbo using the constructor you define
Jumbo b(a); // creates a Jumbo b using the copy constructor (which copies a)
Jumbo c = a; // creates a Jumbo c using the copy constructor (which copies a)
b = a; // copies the already-constructed Jumbo b from a, using the assignment operator
``````
2. The assignment operator usually returns an object by reference (e.g. `*this`), so that you can chain assignments without making extra copies, e.g. `c=b=a;`.
3. In your assignment operator function, `operator=( const Jumbo& )`, function, you should check that you’re not assigning an object to itself (bad things will happen). If the address of the argument `==this`, then you don’t need to do anything (except return `*this`).

## Hints:

`Jumbo Jumbo::add(const Jumbo&) const;` will require you to remember how to add two numbers digit-by-digit.

When you add two or three one-digit numbers a1+a2+a3=s, the result is a one or two digit number, s. The first digit of s is given by `s/10` and the second digit of s is given by `s%10`.

`strings` have useful member functions. If you have a string `my_string` then:

• `my_string.size()` // returns an unsigned int that is the number of characters in the string
• `my_string[i]` // returns the ith character (starting with index zero, of course)

Google “ASCII table” and you’ll see that the ASCII value of the character `'0'` is not zero, it’s 48. The ASCII value of the character `'1'` is 49, etc.. To convert a single digit to the value it represents, subtract 48, e.g.:

``````char my_char;
```cout << "ENTER A DIGIT: ";
cin >> my_char;
int digit_value = my_char - '0';```

Plan out your `Jumbo(unsigned int)`, `str()`, and especially `add` functions first, and choose a `private` dynamically-allocated data representation that makes these procedures the easiest.

Starting files:

## More Hints:

Jumbo(unsigned int aValue);

Jumbo(const string& s);

Examples:

Jumbo(“678678963848937973974238947891734897239472389749827349”);

Jumbo(5786868)

(LSD) 9 -> 4 -> 3 -> 7 ->…. -> 7 -> 6 (MSD)

(LSD) 8 -> 6 -> 8 -> 6 -> …. -> 7 -> 5 (MSD)

Approach: Digit by digit addition and passing the carry forward.

Sample output:

Running sum is: 0

Running sum is: 9789089080808908089080808098908908908908

Running sum is: 9789092505132060268552067136310157002188

Running sum is: 341904832014830184390291279475419955968671836970948358469910600

Running sum is: 2978313897194739217489071289478912374891238289136726727219933302666191855267195143584211894127299707400312

Running sum is: 314897389127489123792449552844433656706612820222193809498785950683860624216532682215415124644705086381073483323071021654524299

## Solution

The solution files are here.

## 2. Sparse Matrices

In the subfield of numerical analysis, a sparse matrix is a matrix populated primarily with zeros (Stoer & Bulirsch 2002, p. 619) as elements of the table.

The basic data structure for a matrix is a two-dimensional array. For an m×n matrix, enough memory to store up to (m×n) entries to represent the matrix is needed. For storing a 1000×1000 matrix, this will take up 1 million entries. This is quite wasteful if only 1% of the entries are non-zero. Therefore, substantial memory requirement reductions can be realized by storing only the non-zero entries.

Goal: Implement a linked-list based data structure to realize a SparseMatrix, that only stores the non-zero elements. Overload the ‘*’ operator and implement the matrix multiplication for the Sparse matrices leveraging the linked-list based data structure.

Starting files:

Sample output:

Enter sm1
Enter the non-zero elements with row and col specification
Row: 0
Col: 1
Entry (0,1) = 5
More? (1/0) 1
Row: 2
Col: 2
Entry (2,2) = 6
More? (1/0) 1
Row: 1
Col: 2
Entry (1,2) = 8
More? (1/0) 0
sm1:

0 5 0
0 0 8
0 0 6

Enter sm2
Enter the non-zero elements with row and col specification
Row: 0
Col: 0
Entry (0,0) = 10
More? (1/0) 1
Row: 1
Col: 1
Entry (1,1) = 100
More? (1/0) 1
Row: 2
Col: 2
Entry (2,2) = 200
More? (1/0) 0
sm2:

10 0 0
0 100 0
0 0 200

Output (sm1 * sm2):
0 500 0
0 0 1600
0 0 1200

Enter sm3
Enter the non-zero elements with row and col specification
Row: 1
Col: 9
Entry (1,9) = 62
More? (1/0) 1
Row: 0
Col: 0
Entry (0,0) = 5
More? (1/0) 1
Row: 5
Col: 6
Entry (5,6) = 51
More? (1/0) 1
Row: 8
Col: 8
Entry (8,8) = 90
More? (1/0) 0
sm3:

5 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 62 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 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 51 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 0
0 0 0 0 0 0 0 0 90 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

Enter sm4
Enter the non-zero elements with row and col specification
Row: 5
Col: 2
Entry (5,2) = 100
More? (1/0) 1
Row: 0
Col: 0
Entry (0,0) = 23
More? (1/0) 1
Row: 9
Col: 3
Entry (9,3) = 99
More? (1/0) 0
sm4:

23 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 100 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 99 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 0 0 0 0
0 0 0 0 0 0

Output (sm3 * sm4):
115 0 0 0 0 0
0 0 0 6138 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

## Solution

The solution files are here.