ALGORITHMS
References
Problem Solving and Program Design in C
Jeri R. Hanly, Elliot B. Koffman
C How to Program
Paul Deitel, Harvey Deitel
Software Development Method
1. Specify the problem requirements.
2. Analyze the problem.
3. Design the algorithm to solve the problem.
4. Implement the algorithm.
5. Test and verify the completed program.
6. Maintain and update the program.
PROBLEM
Specifying the problem requirements forces you to state the
problem clearly and unambiguously and to gain a clear
understanding of what is required for its solution.
Your objective is to eliminate unimportant aspects and zero in on
the root problem.
This goal may not be as easy to achieve as it sounds. You may
find you need more information from the person who posed the
problem.
ANALYSIS
Analyzing the problem involves identifying the problem
(a) inputs, that is, the data you have to work with;
(b) outputs , that is, the desired results; and
(c) any additional requirements or constraints on the solution.
At this stage, you should also determine the required format in which the
results should be displayed (for example, as a table with specific column
headings) and develop a list of problem variables and their relationships.
These relationships may be expressed as formulas.
ANALYSIS
If steps 1 and 2 are not done properly, you will solve the wrong problem.
Read the problem statement carefully, first, to obtain a clear idea of the
problem and second, to determine the inputs and outputs. You may find it
helpful to underline phrases in the problem statement that identify the inputs
and outputs, as in the problem statement below.
Compute and display the total cost of apples given the number of
pounds of apples purchased and the cost per pound of apples .
Next, summarize the information contained in the underlined phrases:
ANALYSIS
Problem Inputs
quantity of apples purchased (in pounds)
cost per pound of apples (in dollars per pound)
Problem Output
total cost of apples (in dollars)
ANALYSIS
Once you know the problem inputs and outputs, develop a list of
formulas that specify relationships between them. The general formula
Total cost = Unit cost X Number of units
computes the total cost of any item purchased. Substituting the
variables for our particular problem yields the formula
Total cost of apples = Cost per pound X Pounds of apples
ANALYSIS
In some situations, you may need to make certain assumptions or
simplifications to derive these relationships.
This process of modeling a problem by extracting the essential
variables and their relationships is called abstraction .
DESIGN
Designing the algorithm to solve the problem requires you to
develop a list of steps called an algorithm to solve the problem
and to then verify that the algorithm solves the problem as
intended.
Writing the algorithm is often the most difficult part of the
problem-solving process. Don’t attempt to solve every detail of
the problem at the beginning; instead, discipline yourself to use
top-down design.
In top-down design (also called divide and conquer ), you first
list the major steps, or subproblems, that need to be solved. Then
you solve the original problem by solving each of its
subproblems. Most computer algorithms consist of at least the
following subproblems.
ALGORITHM FOR A PROGRAMMING
PROBLEM
1. Get the data.
2. Perform the computations.
3. Display the results.
ALGORITHM FOR A PROGRAMMING
PROBLEM
Once you know the subproblems, you can attack each one individually.
For example, the perform-the-computations step may need to be
broken down into a more detailed list of steps through a process called
stepwise refinement .
You may be familiar with top-down design if you use an outline when
writing a term paper. Your first step is to create an outline of the major
topics, which you then refine by filling in subtopics for each major
topic. Once the outline is complete, you begin writing the text for each
subtopic.
ALGORITHM FOR A PROGRAMMING
PROBLEM
Desk checking is an important part of algorithm design that is often
overlooked. To desk check an algorithm, you must carefully perform
each algorithm step (or its refinements) just as a computer would and
verify that the algorithm works as intended. You’ll save time and effort
if you locate algorithm errors early in the problem-solving process.
ALGORITHM FOR A PROGRAMMING
PROBLEM
Desk checking is an important part of algorithm design that is often
overlooked. To desk check an algorithm, you must carefully perform
each algorithm step (or its refinements) just as a computer would and
verify that the algorithm works as intended. You’ll save time and effort
if you locate algorithm errors early in the problem-solving process.
IMPLEMENTATION
Implementing the algorithm (step 4 in the software development
method) involves writing it as a program. You must convert each
algorithm step into one or more statements in a programming
language.
TESTING
Testing and verifying the program requires testing the completed
program to verify that it works as desired. Don’t rely on just one
test case. Run the program several times using different sets of
data to make sure that it works correctly for every situation
provided for in the algorithm.
MAINTENANCE
Maintaining and updating the program involves modifying a
program to remove previously undetected errors and to keep it
up-to-date as government regulations or company policies
change. Many organizations maintain a program for five years or
more, often after the programmers who originally coded it have
left or moved on to other positions.
A disciplined approach is essential if you want to create programs
that are easy to read, understand, and maintain. You must follow
accepted program style guidelines and avoid tricks and
programming shortcuts.
Caution: Failure Is Part of the Process
Although having a step-by-step approach to problem solving is helpful, we must
avoid jumping to the conclusion that if we follow these steps, we are guaranteed a
correct solution the first time, every time. The fact that verification is so important
implies an essential truth of problem solving: The first (also the second, the third, or
the twentieth) attempt at a solution may be wrong. Probably the most important
distinction between outstanding problem solvers and less proficient ones is that
outstanding problem solvers are not discouraged by initial failures. Rather, they see
the faulty and near-correct early solutions as a means of gaining a better
understanding of the problem.
One of the most inventive problem solvers of all time, Thomas Edison, is noted for
his positive interpretation of the thousands of failed experiments that contributed to
his incredible record of inventions. His friends report that he always saw those
failures in terms of the helpful data they yielded about what did not work.
CASE STUDY Converting Miles to Kilometers
PROBLEM
Your summer surveying job requires you to study some maps
that give distances in kilometers and some that use miles. You
and your coworkers prefer to deal in metric measurements. Write
a program that performs the necessary conversion.
CASE STUDY Converting Miles to Kilometers
ANALYSIS
The first step in solving this problem is to determine what you are asked to do. You
must convert from one system of measurement to another, but are you supposed to
convert from kilometers to miles, or vice versa? The problem states that you prefer
to deal in metric measurements, so you must convert distance measurements in
miles to kilometers. Therefore, the problem input is distance in miles and the
problem output is distance in kilometers . To write the program, you need to know
the relationship between miles and kilometers. Consulting a metric table shows that
one mile equals 1.609 kilometers.
The data requirements and relevant formulas are listed below. Miles identifies the
memory cell that will contain the problem input and kms dentifies the memory cell
that will contain the program result, or the problem output.
CASE STUDY Converting Miles to Kilometers
DATA REQUIREMENTS
Problem Input
miles /* the distance in miles*/
Problem Output
kms /* the distance in kilometers */
Relevant Formula
1 mile = 1.609 kilometers
CASE STUDY Converting Miles to Kilometers
DATA REQUIREMENTS
Problem Input
miles /* the distance in miles*/
Problem Output
kms /* the distance in kilometers */
Relevant Formula
1 mile = 1.609 kilometers
CASE STUDY Converting Miles to Kilometers
DESIGN
Next, formulate the algorithm that solves the problem. Begin by listing the
three major steps, or subproblems, of the algorithm.
ALGORITHM
1. Get the distance in miles.
2. Convert the distance to kilometers.
3. Display the distance in kilometers.
Now decide whether any steps of the algorithm need further refinement or
whether they are perfectly clear as stated. Step 1 (getting the data) and step
3 (displaying a value) are basic steps and require no further refinement.
Step 2 is fairly straightforward, but some detail might help:
CASE STUDY Converting Miles to Kilometers
Step 2 Refinement
2.1 The distance in kilometers is 1.609 times the distance in miles.
We list the complete algorithm with refinements below to show you how it all
fits together. The algorithm resembles an outline for a term paper. The
refinement of step 2 is numbered as step 2.1 and is indented under step 2.
CASE STUDY Converting Miles to Kilometers
ALGORITHM WITH REFINEMENTS
1. Get the distance in miles.
2. Convert the distance to kilometers.
2.1 The distance in kilometers is 1.609 times the distance in miles.
3. Display the distance in kilometers.
Let’s desk check the algorithm before going further. If step 1 gets a distance
of 10.0 miles, step 2.1 would convert it to 1.609 X 10.00 or 16.09 kilometers.
This correct result would be displayed by step 3.
The Software Development Method
abstraction the
process of modeling a
algorithm a list of problem by extracting
steps for solving a the essential variables
problem and their relationships
stepwise refinement
development of a
detailed list of steps to
solve a particular step in
the original algorithm
top-down design desk checking the
breaking a problem into step-by-step simulation
its major subproblems of the computer
and then solving the execution of an
subproblems algorithm