[1, 0] · [1, 1] = 1,
[1, 1, 0] · [0, 1, 1] = 1, and
[1, 0] · [1, 1, 0] => undefined.
Prompt the user whether to continue or stop.
Step U. Understanding the problem.
The examples in the problem are simple enough, and there is no mentioning of the the case where the user inputs an malformed vector. (We will get back to this problem later.) So, let's do a similar but slightly different decomposition from the last article by decomposing the problem into three sub-problems: prompting the user for vector, computing the inner product, and displaying the output. Let's list the sub-problems in a backlog:
Problem backlog
P1. Prompting the user. Display a welcome message; invite user to input a vector, and get the vector.
P2. Computing the inner product. Given two well-formed vectors, compute their inner product if defined. Flag an error otherwise.
P3. Displaying the output. Display the output message that show the input vectors and the inner product.
Each sub-problem is called a backlog item in the sub-problem backlog. Upon its entrance to the backlog, a sub-problem has been analyzed to give a more precise definition. With the definition, we should be able to determine the type of the sub-problem. Thus, P1 and P3 are about i/o; P2 is about computation.
You should check if you can solve the problem by solving all sub-problems. A little thinking shows that you can: Write a main program that works as follows:
repeat
P1(prompt for vector 1)
P1(prompt for vector 2)
P2(vector 1, vector 2)
P3(output result and prompt for continuation)
Since the decomposition is only a guess, it does not have to be perfect. At any rate, since we are doing multiple rounds, in step L for each round, we can always write up new items for what we did not do so well initially.
Which sub-problem should you begin with? Although any sub-problem in the backlog would do, the general rule is to select the sub-problem that the user cares the most. Since the solution of the whole problem hinges on computing the inner product, let us begin with sub-problem P2.
Step D. Devising a plan.
List the tasks to be completed for sub-problem P2. Recall that a task is a unit of work that should be straightforward. That said, it should be clear that the list of tasks depends on the worker -- you. If you know C programming already, you'll probably have a list like this:
T1. Write a function to compute inner product - normal case.
T2. Handle the case where an inner product is not defined.
T3. Write supporting program to exercise the function.
Task T3 is needed because we insist on having a working program at the end of a round. Without T3, you don't know if you're coding up the function correctly.
However, if you do not yet know how to code up a function, represent a vector, and so on, T1 would probably benefit from further decomposition into something like
T1. Write a function to compute inner product.
T1-1. Learn C function.
T1-2. Learn how to represent vector.
T1-3. Learn passing vector to a function.
T1-4. Write the inner product function.
T2. Handle the case where an inner product is not defined.
T3. Write supporting program to exercise the function.
T2-1. Learn how to call a C function.
T2-2. Write supporting program.
A rule of thumb: if a task is not straightforward to you as a unit of work, further decompose it until you feel comfortable handling.
The two lists intend to solve the same problem. In the first list, you are applying what you already know. In the second list, you are learning something new and putting it to work immediately afterward. So, don't feel you are behind just because you happen to have a longer list for a problem. A longer list just means you have to spend more time but it is definitely doable.
Back to the list. The list of tasks is called a task backlog for solving a sub-problem. In general, there is no implied order of working on the tasks; you get to decide which task to work on.
Step C. Carrying out the plan.
This is the step you can expect to spend the most amount of time in the four steps in solving a sub-problem. While each task is straightforward, in this step you use -- and learn -- your knowledge on programming and engineering practices to write code of good quality. Without getting into detail for now, at the end of T1, you have code like this:
double computeInnerProduct (double v1[], double v2[], int d1, int d2)
{
double r=0;
for (int i=0; i<d1; ++i) {
r = r + v1[i]*v2[i];
}
return r;
}
But does the function work? How do we check it? The obvious way is to call it and output something for you to check. This is the task of T3. So, we are going to write a main function and call the inner product function there. At the end of T3, you have supporting code to exercise the function like this:
#include <iostream>
using namespace std;
int main()
{
double u[2] ={1,0};
double v[2] ={1,1};
double ip;
ip = computeInnerProduct(u,v,2,2);
cout << ip << endl;
return 0;
}
Compile and run, you get something like this:
The first line shows the expected inner product "1" of the two vectors "[1,0]" and "[1,1]".
Carry on with T2. The inner product is not defined if the two vectors are of different dimensions. We fix the code in the function computeInnerProduct and the function main like this:
#include <stdlib.h>
#include <iostream>
using namespace std;
double computeInnerProduct (double v1[], double v2[], int d1, int d2)
{
if (d1 != d2) {
cout << "vectors of different dimension, aborting..." << endl;
exit(-1);
}
double r=0;
for (int i=0; i<d1; ++i) {
r = r + v1[i]*v2[i];
}
return r;
}
int main()
{
double u[2] ={1,0};
double v[2] ={1,1};
double ip;
ip = computeInnerProduct(u,v,2,2);
cout << ip << endl;
double x[2] ={1,0};
double y[3] ={1,1,1};
ip = computeInnerProduct(x,y,2,3);
return 0;
}
The result is something like this:
We have a working program!
Step L. Looking back.
In this step, inspect the program and identify places where improvements are needed. We have a function that appears to compute inner product when two vectors are of the same dimension and abort otherwise. Also, we are using the main function to exercise the function. The main function consists of two tests for computeInnerProduct: a normal case and a case where inner product is undefined. Because the program is not yet complete, it is probably premature to look back in the role of a user. On the other hand, we can always look back as a programmer.
The program aborts when given two vectors of different dimensions, but the problem says it should continue after displaying a proper message. This needs to be fixed.
Are the two tests sufficient? It seems so because every line of code in the function computeInnerProduct is exercised. But you can always add new tests. When you do, the tests will be added to the main function in the current structure of the program. This means that the main function has to be changed frequently. But there is another problem: later, we will need the main function to interacts with the user. When that moment comes, what do you do with the tests?
My suggestion: relocate the tests from the main function. Even better, relocate the tests into another project, one which we shall call a test project. That way you have two projects: a production project and a test project. We will add a new sub-problem:
P4. Test computeInnerProduct in a test project.
© Y C Cheng, 2013, 2014. All rights reserved.
No comments:
Post a Comment