[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 2^{64}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:

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 alreadyconstructed Jumbo b from a, using the assignment operator
 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;
.  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 digitbydigit.
When you add two or three onedigit numbers a_{1}+a_{2}+a_{3}=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 stringmy_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
dynamicallyallocated data representation that makes these procedures the easiest.
Starting files:
Files to start with are here. Please copy all the files from /comp/15/public_html/homeworks/homework2/problem1/ directory.
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
Add: 9789089080808908089080808098908908908908
Running sum is: 9789089080808908089080808098908908908908
Add: 3424323152179471259037401248093280
Running sum is: 9789092505132060268552067136310157002188
Add: 341904832014830184390281490382914823908403284903812048312908412
Running sum is: 341904832014830184390291279475419955968671836970948358469910600
Add: 2978313897194739217489071289478912374891237947231894712389748912374912379847239174912374923178941237489712
Running sum is: 2978313897194739217489071289478912374891238289136726727219933302666191855267195143584211894127299707400312
Add: 314897389127489123789471238947238917489123748932714897123894712394723897489312748912748932789437891237489271428943721947123987
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 twodimensional 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 nonzero. Therefore, substantial memory requirement reductions can be realized by storing only the nonzero entries.
Goal: Implement a linkedlist based data structure to realize a SparseMatrix, that only stores the nonzero elements. Overload the ‘*’ operator and implement the matrix multiplication for the Sparse matrices leveraging the linkedlist based data structure.
Starting files:
Files to start with are here. Please copy all the files from /comp/15/public_html/homeworks/homework2/problem2/ directory.
Sample output:
Enter sm1
Enter the nonzero 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 nonzero 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 nonzero 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 nonzero 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.