cs2223 Problem 2 Solution

[WPI] [cs2223] [cs2223 text] [News] [Syllabus] [Problems] [Problem 2]

cs2223, D97/98 Problem 2 Solution

Note: The code in these files has been tested on the WPI CCC alpha systems. Hovever, the script files for these problems were made using a different computer system because of the quantity of computation time required for problems 2_3 and 2_4.

Problem 2_1

A program which performs heap operations is contained in the CCC directory

/cs/cs2223/problems/problem2/problem2_1

A README file explains how the program works and what is printed out. The "best" caase operations - when the smallest number is the one added, the largest number is the one being deleted, and when the array is already sorted in inverse order (largest values first), take no swaps. The "worst" cases take the numbers of swaps we discussed in Class 9.

Problem 2_2

A program which implements the greedy chage-making program is contained in the CCC directory

/cs/cs2223/problems/problem2/problem2_2

A README file explains how the program works and what is printed out. Two data files with coin denominations up to 100.00 were used:

us.dat is the standard US coin system
wpi.dat uses non-standard coin values and does not contain a coin of value 0.01 so not all values of change can be made with this system.

Note that the README file points out the methods used to prevent roundoff errors and conversions between floating point numbers and integers from producing erroneous results.

Problem 2_3

This problem was solved in two ways. In the first, a classical N² approach was used. The program is contained in the CCC directory

/cs/cs2223/problems/problem2/problem2_3a

A README file explains how the program works and what is printed out. The program first multiplies N-digit random numbers by 1-digit random numbers and shows the number of single-digit multiplies is linear in N. Then it multiplies N-digit numbers by N-digit numbers and shows the number of single-digit multiples is quadratic in N. The cases used wre N = 1, 2, 4, 8, ... 1024.

In the second approach, the N^lg3 approach discussed in Class 14 was used. The program is contained in the CCC directory

/cs/cs2223/problems/problem2/problem2_3b

There are two important comments about these programs.

First, when you look at the second solution, notice that the number of single-digit multiplies increasesas approximately N^lg3. However, the actually number is greater than N^lg3 and, for small values of N, the numberof single-digit multiplies can even exceed the N² algorithm in the first solution! That is because the second multiplication algorithm is recursive. When two N/2 digit numbers are multiplied, the answer can be between size (N/2 - 1) and size(N/2 ) - depending on the actual values being multiplied. And, in the calculation of P2, the "middle" value - see the Class 14 notes - can be of size (N/2 + 1). This incrases the number of multiplications required in other recursive steps. That also explaines why this program run multiple times will give different values for the N x N case.

Second, if you actually time the two programs above, you will find - on most systems - that the first program, the N² one, runs faster than the second program, the N^lg3 one. That is because of the large number of function calls used in the second program. This problem is a demonstration of how to work with a class of algorithms, but no attempt has been made to optimize the programs once the algorithm has been selected. If the N^lg3 algorithm were implemented properly - using binary instead of decimal notation, assembly language or in-line functions for the multiplications, in-place computations (instead of making all of the copies which this code uses), etc. - the second algorithm could be made to run substantially faster than the first algorithm.

Problem 2_4

The program is contained in the CCC directory

/cs/cs2223/problems/problem2/problem2_4

A README file explains how the program works and what is printed out. This program uses the divide and conquer algorithm from Section 7.7 of the text. Notice how greatly the number of digits varies depending on the specific values of the two numbers, especially the one which is the exponent. In the script file, the number of digits in the answer for the case of 3-digits numbers is actually smaller than the number of digits in the answer for the case of 4-digit numbers.

Grading

The grading criteria are available. These are subject to interpretation by the grader. As we stated in class, our primary goal in the grading of these exams is consistency. If your intrepretation differs from the grader's and the grader has applied her/his criteria uniformly, then the grader's interpretation will prevail.