CSci 49 - Systematic Software Development

School of Engineering and Applied Science
Department of Computer Science
CSci 49 -- Introduction to C Computing
http://www.seas.gwu.edu/~csci49/spring06
Prof. Michael B. Feldman
mfeldman@gwu.edu

SYSTEMATIC SOFTWARE DEVELOPMENT USING ANSI/ISO C

Problem Solving and Programming

Computer problem-solving ability is a combination of art and science, the transformation of a description—in English or another human language—of a problem into a form that permits a mechanical solution and the implementation of that solution on a computer. A relatively straightforward example of this process is transforming a word problem into a set of algebraic equations that can then be solved for one or more unknowns.

Most problems are not so easily solved. The problem-solving process is more difficult because problem descriptions are often incomplete, imprecise, or ambiguous. The successful problem solver needs to learn the following skills:

Ask the right questions to clarify the problem and obtain any information that is missing from the problem statement (this process is called problem specification).
Analyze the problem, attempting to extract its essential features and identify what is provided (the problem inputs) and what is required (the problem outputs).
Determine whether there are any constraints or simplifying assumptions that can be applied to facilitate the problem solution. We often cannot solve the most general case of a problem but must make some realistic assumptions that limit or constrain the problem so that it can be solved.
Apply knowledge of the problem environment and the formulas or equations that characterize it, to develop a series of steps whose successful completion will lead to a problem solution, eventually implementing or coding these steps in a form that can be submitted to a computer.
Once a solution is obtained, verify its accuracy by testing it systematically, according to a test plan.

The Software Development Method

Students in many subject areas receive instruction in specific problem-solving methods. For example, business students are encouraged to follow a systems approach to problem solving; engineering and science students are encouraged to follow the engineering and scientific method. Although these problem-solving methods are associated with very different fields of study, their essential ingredients are quite similar. We will describe one such method below.

This course is concerned with a particular kind of problem solving, namely, developing solutions that use computers to get results. A computer cannot think; therefore, to get it to do any useful work, we must provide a computer with a program that is a list of instructions. Programming a computer is a lot more involved than simply writing a list of instructions. Software development is really an exercise in systematic problem solving. Before we can write a program to solve a particular problem, we must consider carefully all aspects of the problem and then organize its solution.

A software developer is someone who is involved with the design and implementation of reliable software systems. This title emphasizes the fact that programmers, like engineers, are concerned with developing practical, reliable solutions to problems. However, the product that a software developer produces is a software system rather than a physical system.

To highlight the analogy with engineering, some people refer to software engineering and software engineers. To emphasize the fact that one need not be an actual engineer or even an engineering student to develop good software, we instead use the terms software development and software developer.

Steps in the Software Development Method

Software can be complicated, so software development requires the developer to use a methodical working style. Details of different methods vary somewhat, but these methods have in common that they are systematic, step-by-step approaches. The software development method that is used in this course is typical of the methods used in industry. You are required to use this method in your projects, and your project grade will depend heavily on your following it carefully. Here are the major steps:

Problem specification: State the problem and gain a clear understanding of what is required for its solution. This sounds easy, but it can be the most critical part of problem solving. A good problem solver must be able to recognize and define the problem precisely. If the problem is not totally defined, you must study the problem carefully, eliminating the aspects that are unimportant and zeroing in on the root problem.
Analysis: Identify problem inputs, desired outputs, and any additional requirements of or constraints on the solution. Identify what information is supplied as problem data and what results should be computed and displayed. Also, determine the required form and units in which the results should be displayed (for example, as a table with specific column headings).
Design: Develop a list of steps (called an algorithm) to solve the problem and verify that the algorithm solves the problem as intended. Writing the algorithm is often the most difficult part of the problem-solving process. Once you have the algorithm, you should verify that it is correct before proceeding further.
Test plan: Develop a strategy for proving to yourself and to others that your algorithm will get the proper results. It is highly advisable to write a plan for testing the program you will write, even before you have written it. Which test cases will you choose? What are the special cases that must be tested? Pretend you are a potential purchaser of the program and ask, “Which tests would I require to be convinced that this program behaves as advertised?”
Implementation or coding: Implement the algorithm as a program. This requires knowledge of a particular programming language. Each algorithm step must be converted into a statement in that programming language.
Testing: Run the completed program, testing it with the test cases specified in the test plan.

If the first three steps in the list above are not done properly, you will either solve the wrong problem or produce an awkward, inefficient solution. To perform these steps successfully, it is most important that you read the problem statement carefully before attempting to solve it. You may need to read each problem statement two or three times. The first time, you should get a general idea of what is being asked. The second time, you should try to answer the questions:

What information should the solution provide?
What data do I have to work with?

The answer to the first question will tell you the desired results, or the problem outputs. The answer to the second question will tell you the data provided, or the problem inputs. It may be helpful to underline the phrases in the problem statement that identify the inputs and outputs.

As was indicated above, the design phase is often the most difficult part of the problem-solving process. When you write an algorithm, you should first list the major steps of the problem that need to be solved (called subproblems). Don’t try to list each and every step imaginable; instead, concentrate on the overall strategy. Once you have the list of subproblems, you can attack each one individually, adding detail or refining the algorithm. The process of solving a problem by breaking it up into its smaller subproblems, called divide and conquer, is a basic strategy for all kinds of problem solving activities.

If you do not develop a proper test plan, you risk just running the program with casually chosen inputs, thereby missing important test cases which, should they arise after the program is completed and delivered, may cause the program to fail unexpectedly. A program’s behavior must be, to the greatest extent possible, predictable, even if the user makes errors in operating it.

The principle of predictable performance requires that a test plan should include cases of “bad” as well as “good” input. An especially tragic, and true, story of unpredictable software is a certain radiation machine that, in treating several cancer patients, responded to some unexpected operator keystrokes by giving the patients lethally high radiation dosages, killing them instead of treating their cancer.

The software development method can be used with any actual programming language; indeed, only the implementation phase really requires detailed knowledge of a language or a particular computer. Even the testing phase is, in industry, often carried out by individuals who do not know programming but specialize in developing good tests of programs.

Now let us look at two examples. The first is a real-life example, changing a flat tire on a car; we will develop a tire-changing algorithm. The second is a small software development problem.

An Example from "Real Life": Changing a Flat Tire

Problem Specification

You are driving a car with two friends and suddenly get a flat tire. Fortunately, there is a spare tire and jack in the trunk.

Analysis

After pulling over to the side of the road, you might decide to subdivide the problem of changing a tire into the subproblems below.

Design

Here are the main steps in the algorithm to change a tire.

Algorithm

1. Loosen the lug nuts on the flat tire; don’t remove them yet.
2. Get the jack and jack up the car.
3. Remove the lug nuts from the flat tire and remove the tire.
4. Get the spare tire, place it on the wheel, and tighten the lug nuts.
5. Lower the car.
6. Secure the jack and flat tire in the trunk.

Because these steps are relatively independent, you might decide to assign subproblem 1 to friend A, subproblem 2 to friend B, subproblem 3 to yourself, and so on. If friend B has used a jack before, the whole process should proceed smoothly; however, if friend B does not know how to use a jack, you need to refine step 2 further.

Step 2 Refinement

2.1. Get the jack from the trunk.
2.2. Place the jack under the car near the flat tire.
2.3. Insert the jack handle in the jack.
2.4. Place a block of wood under the car to keep it from rolling.
2.5. Jack up the car until there is enough room for the spare tire.

Step 2.4 requires a bit of decision making on your friend’s part. Because the actual placement of the block of wood depends on whether the car is facing uphill or downhill, friend B needs to refine step 2.4.

Step 2.4 Refinement

2.4.1 If the car is facing uphill, then place the block of wood in back of a tire that is not flat; if the car is facing downhill, then place the block of wood in front of a tire that is not flat. This is actually a conditional action: One of two alternative actions is executed, depending on a certain condition.

Finally, step 2.5 involves a repetitive action: moving the jack handle until there is sufficient room to put on the spare tire. Often, people stop when the car is high enough to remove the flat tire, forgetting that an inflated tire requires more room. It may take a few attempts to complete step 2.5.

Step 2.5 Refinement

2.5.1. Move the jack handle repeatedly until the car is high enough off the ground that the spare tire can be put on the wheel.

Refined Algorithm

Here is the refined algorithm thus far. You can continue refining it until you are satisfied that every detail has been properly specified.

1. Loosen the lug nuts on the flat tire; don’t remove them yet.
2. Get the jack and jack up the car.
2.1. Get the jack from the trunk.
2.2. Place the jack under the car near the flat tire.
2.3. Insert the jack handle in the jack.
2.4. Place a block of wood under the car to keep it from rolling.
2.4.1. If the car is facing uphill, then place the block of wood in back of a tire that is not flat; if the car is facing downhill, then place the block of wood in front of a tire that is not flat.
2.5. Jack up the car until there is enough room for the spare tire.
2.5.1. Move the jack handle repeatedly until the car is high enough off the ground that the spare tire can be put on the wheel.

3. Loosen the lug nuts from the flat tire and remove the tire.
4. Get the spare tire, place it on the wheel, and tighten the lug nuts.
5. Lower the car.
6. Secure the jack and flat tire in the trunk.

The algorithm for changing a flat tire has three categories of action: sequential actions, conditional actions, and repeated actions. Steps 2.1 through 2.5 are carried out in the sequence listed. Step 2.4.1 illustrates a conditional action in that placement of the block of wood depends on the angle of inclination of the car. Step 1.5.1 illustrates repetition.

In general, the order of steps in an algorithm is very important. For example, the car cannot be lowered before it has been raised. Sometimes, there are several sequences for the steps in an algorithm, any one of which will produce a proper result, but in any case the steps cannot be written in a careless, arbitrary order. To succeed in software development, you must be willing to focus on solving problems in a careful, step-by-step fashion.

A Computer Example: Your Sister's Piggy Bank

Problem Specification

Your little sister has been saving nickels (U.S. five-cent coins) and pennies (U.S. one-cent coins) for quite a while. Because she is getting tired of lugging her piggy bank with her whenever she goes to the store, she would like to trade in her collection for one-dollar banknotes (a dollar is 100 cents) and some change. To do this, she would like to know the value of her coin collection in dollars and cents.

Analysis

To solve this problem, we must be given the count of nickels and the count of pennies in the collection. The first step is to determine the total value of the collection in cents. Once we have this figure, we can do an integer division using 100 as the divisor to get the dollar value; the remainder of this division will be the loose change that she should receive. In the data requirements below, we list the total value in cents (totalCents) as a program variable because it is needed as part of the computation process; it is not a required problem output.

Data Requirements and Formulas

Problem Inputs:

nickels - the number of nickels, an integer
pennies - the number of pennies, an integer

Problem Outputs:

dollars - the number of dollars she should receive, an integer
change - the loose change she should receive, an integer

Additional Program Variables:

total cents - the total number of cents, an integer

Relevant Formulas

One nickel equals five pennies.

Design

The algorithm is straightforward and is displayed next.

Initial Algorithm

1. Prompt the user and read in the number of nickels and pennies.
2. Compute the total value in cents.
3. Find the value in dollars and loose change.
4. Display the value in dollars and loose change.

Steps 2 and 3 need refinement.

Step 2 Refinement

2.1. total cents is 5 times nickels plus pennies.

Step 3 Refinement:

3.1. dollars is the integer quotient of total cents and 100.
3.2. change is the integer remainder of total cents and 100.

Algorithm with Refinements

1. Prompt the user and read in the number of nickels and pennies.
2. Compute the total value in cents.
2.1. total cents is 5 times nickels plus pennies.
3. Find the value in dollars and loose change.
3.1. dollars is the integer quotient of total cents and 100.
3.2. change is the integer remainder of total cents and 100.
4. Display the value in dollars and loose change.

Test Plan

In addition to testing some typical values, there are several special cases in our test plan: zero nickels and/or zero pennies, and negative input values. Let’s put the test plan in the form of a table.

**Test Plan for Coin Collection**
Test Case	Nickels	Pennies	Reason	Expected Result
1	30	77	typical	$2.27
2	0	59	no nickels	$0.59
3	13	0	no pennies	$0.65
4	0	0	no coins	$0.00
5	13	-5	negative	?
6	xyz	4	bad input	?

The last two cases test for out of range input (a negative number when a natural number is required) and “bad” input (letters instead of digits). The question marks indicate that we won’t know the result until we run the test. It is important always to test programs with “bad” as well as “good” input: The programmer cannot control which keys will be pressed by the human user, and a program’s behavior must always be predictable.

Implementation

Developers seldom start off with a blank slate (or empty screen) when they develop a program; to save time and effort, they try to make use of their documentation, and of their existing programs.

Start with an Existing Source File

Using an existing program as a starting point for a new one will save you from typing in the entire new file from scratch. For example, in this course you can always start with a file called ProjectTemplate.c. You simply copy this file from the course distribution into your own file system, changing the file name to the one that will name your project. Here is the source listing for this template:

   1. /*------------------------------------------------------------
   2. | ProjectTemplate.c
   3. | You can use this as a starting point for your projects.
   4. | Author: <your name>, The George Washington University
   5. | Last Modified: January 2, 2006
   6. ------------------------------------------------------------*/
   7. #include <stdio.h>
   8. int main()
   9. {
10.   /* Put your own program statements here! */
11.   return 0; /* indicate that program ended successfully */
12. }

This file has the proper basic "structure" for a C application. It has no compilation errors in it, but it does nothing. It's just a starting point.

Make a "framework file" for your program

Starting with the template, make the necessary name changes, then copy the problem data requirements into the program declaration section, editing those lines to conform to the C syntax for constant and variable declarations. This approach is especially helpful if the documentation file was created with a word processor and is in a file from which you can copy lines and paste them into the code file.

Fill in the program statements

To develop the program body,

Write the initial algorithm steps as program comments. The comments describe each algorithm step and provide program documentation that guides your C code.
Save the file and compile it. If there are any errors, correct these immediately. You will then have a correct framework into which you can add the program statements.
Begin to add the C statements, after the appropriate comments. Place the code for an unrefined step directly under that step. For a refined step, either edit the refinement to convert it from English to C or just replace it with C code.

Here is the listing for CoinCollection after Step 2:

1. /*------------------------------------------------------------ 2. | CoinCollection.c 3. | Finds the value of a coin collection, 4. | given pennies and nickels 5. | Author: M.B. Feldman, The George Washington University 6. | Last Modified: January 2, 2006 7. ------------------------------------------------------------*/ 8. #include <stdio.h> 9. int main() 10. { 11. int pennies; /* input - number of pennies */ 12. int nickels; /* input - number of nickels */ 13. int dollars; /* output - dollars part of value */ 14. int change; /* output - cents part of value */ 15. 16. int totalCents; /* internal variable */ 17. 18. /* Prompt the user and read in the number of nickels and pennies. */ 19. /* Compute the total value in cents. */ 20. /* Find the value in dollars and loose change. */ 21. /* Display the value in dollars and loose change. */ 22. 23. return 0; /* indicate that program ended successfully */ 24. 25. }

Here's the listing for the final result:

1. /*------------------------------------------------------------ 2. | CoinCollection.c 3. | Finds the value of a coin collection, 4. | given pennies and nickels 5. | Author: M.B. Feldman, The George Washington University 6. | Last Modified: January 2, 2006 7. ------------------------------------------------------------*/ 8. #include <stdio.h> 9. int main() 10. { 11. int pennies; /* input - number of pennies */ 12. int nickels; /* input - number of nickels */ 13. int dollars; /* output - dollars part of value */ 14. int change; /* output - cents part of value */ 15. 16. int totalCents; /* internal variable */ 17. 18. /* Prompt the user and read in the number of nickels and pennies. */ 19. printf ("How many nickels do you have? "); 20. scanf("%d", &nickels); 21. printf ("How many pennies do you have? "); 22. scanf("%d", &pennies); 23. 24. /* Compute the total value in cents. */ 25. totalCents = 5 * nickels + pennies; 26. 27. /* Find the value in dollars and loose change. */ 28. dollars = totalCents / 100; 29. change = totalCents % 100; 30. 31. /* Display the value in dollars and loose change. */ 32. printf ("Your collection is worth %d dollars and %d cents.\n", 33. dollars, change); 34. 35. return 0; /* indicate that program ended successfully */ 36. 37. }

Comments on the Program

The statements in lines 20, 22, 25, 28, 29, and 32-33 need a bit of discussion. In line 20, the variable nickels is set to the result of calling a special input function, scanf. This statement allows the user to enter one integer value from the keyboard. Line 22 similarly sets pennies to an integer value entered from the keyboard. Note in both cases the string "%d", which indicates that the value is an integer value (the d stands for "decimal"). Note also that in a call to scanf, the variable name in which the input value is stored must be preceded immediately by an ampersand (&); Later in the course, we'll discuss why this is so. For now, just treat it as a rule you must learn.

Line 25 computes the value of an arithmetic expression and stores it in the integer variable totalCents. The asterisk (*) is used in programming to indicate multiplication; the expression is evaluated as though it were written (5 * nickels) + pennies, that is, first the number of nickels is multiplied by 5, then the number of pennies is added in.

Line 28 contains the expression totalCents / 100. The slash (/) is used in programming to indicate division. Because dollars, totalCents, and 100 are all integers (whole numbers), the division operation finds and keeps the quotient of the division, and throws the remainder away. That is, if totalCents is 1256, dollars becomes 12.

Line 29 contains the expression totalCents % 100. The percent sign (%) is used in C as the remainder operation, which is a counterpart to the integer division operation. The operation divides totalCents by 100, keeps the remainder, and throws away the quotient.That is, if totalCents is 1256, change becomes 56.

Finally, the statement in lines 32-33 is a call to the output function printf, which displays the results on the screen. Between the parentheses are three items separated by commas. The second and third items are the variables whose values we wish to display; the first item gives the surrounding titles. printf substitutes the value of dollars for the first %d and the values of change for thye second %d.

Testing

Run the program and enter the required data according to your test plan. In this case, the program handles only one set of data per run, so each test case will require a separate run of the program. Make sure your actual results agree with the ones you predicted in the test plan. Running the test plan for this program will be the first part of your first project in this course.

(end of article)