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:

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 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:

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 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.