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

cs2223, D97/98 Problem 3 Solution

Problem 3_1

A program which makes change is contained in the CCC directory

/cs/cs2223/problems/problem3/problem3_1

A README file explains how the program works and a script file shows program operation.

Problem 3_2

A program which calculates the optimal order of performing matrix multiplications is contained in the CCC directory

/cs/cs2223/problems/problem3/problem3_2

A README file explains how the program works and a script file shows program operation.

Problem 3_3

A program which calculates the optimal order of performing matrix multiplications is contained in the CCC directory

/cs/cs2223/problems/problem3/problem3_3

A README file explains how the program works and a script file shows program operation.

The method used was analogous to the method shown for integrating functions in Class 22. Three different random number generators were used. The three methods were:

The C standard library random number generator rand().

The method referenced in MR Headington and DD Riley, Data Abstraction and Structures using C++, 1997, Jones and Bartlett, ISBN 0-7637-0295-1, p79

The method referenced in SS Skiena, The Algorithm Design Manual, 1998, Springer/Telos, ISBN 0-387-94860-0, p218

Of the three, the last gave the best results in our tests. The error (to six decimal places) as a function of the number of points selected was as follows:

n	"pi"	error (absolute value)
1	4	0.85841
10	3.2	0.05841
100	3.04	0.10159
1000	3.08	0.06159
10000	3.156	0.01441
100000	3.14308	0.00149
1000000	3.14166	0.00007
10000000	3.14159	0.00000
100000000	3.14159	0.00000

Problem 3_4

The teaching staff hasn't figured out how to do this one yet. If we do, the website will be updated. But don't hold your breath waiting.

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.

[cs2223 text] [News] [Syllabus] [Problems] [Problem 3]

Contents ©1994-1998, Norman Wittels
Updated 24Apr98