This chapter is really not a part of data structures per se, but there are several facts that you should learn. We will go over this chapter quickly so here is a summary of what you should know.
Problem Solving and Software Engineering
In
general you should never read a programming problem and then just start writing
code. You need time to analyze the problem, talk about it with other
programmers, jot down notes on how to solve the problem, define terms, then
write a general algorithm, etc. before you actually write code.
What is Problem Solving?
- “the entire process of taking the statement of a problem and developing a computer program that solves that problem.”
-
A solution usually consist of an algorithm and data
(structures)
All large software programs go thru what is known as the Software Life Cycle. The major portions of the life cycle are:
1.
Specification
2.
Design
3.
Risk Analysis
4.
Verification
5.
Coding
6.
Testing
7.
Refining
8.
Production
9.
Maintenance
Notice where “Coding” appears in
the cycle – only toward the middle of the whole process.
Phase 1: Specification
Take the statement of the problem and specify it in terms
of what you will need to solve it on a computer. What is the input data? What
is valid or invalid data? Who will use the software? What should the user
interface look like? What errors should be detected and reported? Will there be
special cases? What documentation is necessary? Also you will have to
“translate” the definition of the problem that the customer gives you. He/she
probably will not couch the problem in computer terms so it is up to you to
rewrite the problem in terms a computer scientist or engineer can understand.
You may also want
to write a prototype program in this phase. A prototype program sort of solves
the problem but perhaps not all of it. It is a tool to see if the problem is
solvable. However you should remember that there is an unwritten rule that all
prototype programs will be thrown away!
Phase 2: Design
Divide the problem into smaller manageable steps. These
will later become modules or groups of modules. The modules should be loosely
coupled so that they can be reused elsewhere in the project. Determine how the
data will flow thru the program and what actions will be appropriate at each
stage. Each module should have a “contract” that specifies how it can be used.
This involves defining what are called preconditions and postconditions. These
are usually very strict. For example:
move(x,y)
// Moves a shape to coordinate (x,y) on the screen.
//Precondition: The calling program provides an (x,y)
pair, both integers,
//where 0 <=x<=MAX_XCOOR, 0<=y<=MAX_YCOOR,
where MAX_XCOOR
//and MAX_YCOOR are class constants that specify the
maximum coordinate values.
//Psotcondition: The shape is moved to coordinate (x,y)
I cannot emphasize enough that students must learn to document their programs! I will expect LOTS of documentation in programs you write in this course. For more complicated methods you will be expected to write preconditions and postconditions as comments in your method. You should also look for other solutions to the problem or part of the problem. In other words, do some research. Are there programmers who are using the same language as you and have solved similar problems? Can you obtain that code rather than writing it yourself? If someone else has written a module that you need to solve your problem, you should not rewrite your own.
Here is where you make some decisions. Is it possible
to solve the problem? Will there be other problems that may crop up during the
software life cycle? For example, if the problem is to predict the personal
income of every individual college student in the USA 2 years after he/she
graduates, then the problem is probably impossible to solve. Ethically you
should not attempt to write the program.
Phase 4: Verification:
There are ways of “proving” that an algorithm that solves
a problem is correct. These usually involve things called “assertions” and
“invariants”. The methods use to actually prove the correctness of an algorithm
involve higher mathematics. For those of you who know a little higher math,
consider trying to prove that a certain program will work on any set of N
values. To do this you need to know how to prove an assertion using a technique
called mathematical induction. This is far beyond the scope of this class and
we will not go into it.
Phase 5: Coding
If you have done all of the work correctly in the first
four stages, then coding simply becomes a matter of translating your design
into a particular programming language. What you have done already is design
the algorithms and data structures to solve the problem. They may be in
pseudo-language, but the translation process into an actual programming
language should be fairly simple.
Phase 6: Testing
This not only involves getting rid of obvious errors in
the program, but also testing it on normal and abnormal data to make sure it
will not cause harm to the system. Sometimes this is called “fault tolerance”.
Not only do you give it a “monkey test” but you deliberately try to cause the
program to do something “bad”. Then you can go back and fix code to make sure
those “bad” things are kept to a minimum.
Phase 7: Refining the solution
Can you make it better? Is there something you forgot? Is
there something that perhaps you should add to make the program easier to use?
Just remember that if you change ANYTHING, you go back to Phase 6.
Phase 8: Production
This is usually something you are not going to do. This
is done by another part of the company. It involves making the program
saleable. It also involves regular production lines for packaging,
distribution, etc.
Phase 9: Maintenance
So your customer gets your program and calls you up and
says it doesn’t work. You have to fix it and retest the solution. Maintenance
can be short term or long term depending on the contract. In fact, it is an
unfortunate fact that many computer scientists, when they get their first job,
are asked to fix problems in software programs that other people wrote long
before. I’m sure that if you were in that position, you would want
well-documented programs. So “Do unto others ….”
Your textbook uses this definition: “A solution is
good if the total cost it incurs over all phases of its life cycle is minimal.”
You
may say, “What a minute! That definition doesn’t even say that the program has
to work!” But it actually does. If the program does not work then the cost of
the testing and maintenance phases will be high. If the program really works
well, then the cost of all phases is kept at a minimum.
We
all know that we should solve a problem by breaking it into smaller parts and
that these smaller parts should become modules or methods in our program. When
you design modules, you should always concentrate on WHAT” it does, not how it
does it. Modules perform actions. You should specify what the action is and
what the assumptions are on the inputs and what the characteristics of the
output should be. By looking at only what a module does, you are ABSTRACTING
the problem. You put off implementation details (code) until later.
The
problem is broken down into modules. The modules are broken down even more
until we get to the level where we can identify an actual METHOD, some
self-contained piece if code. Yet even before we code the method, we must
define it without code first. This is called PROCEDURAL ABSTRACTION.
Also,
as you design the solution to the problem, you will need data. Data can be
simple or complex. The more complex it becomes, the more necessary it is to
define something called an ABSTRACT DATA TYPE (or ADT). An ADT defines a
particular collection of data and it also defines what actions can be taken on
that data by a user (i.e. a programmer). As a simple example, one ADT may be:
Data: Array of N integers
Operations: Insert number
Delete
number
Sort
array
Print
array
In
CSC-117 you probably studied the reserved words in Java, public and private. Java uses these words to help
you in your procedural abstractions. Only you should decide what kinds of data
in a method will be made public (usable by others) and which should remain
private (usable by only you). In general a person who uses a method you create
should only see it abstractly. They should know what actions are available to
them, but they should not need to know how you perform those actions on any
given piece of data. As long as you do your part correctly, they need not know
how it is done. As a brief example, how many ways can you think of storing a
date inside a method?
By
making things private inside of a method, you are using a concept called
INFORMATION HIDING.
As
we spoke of an ADT defining data and actions that can be performed on that
data, a bell should have gone off in your head. Aha! We are getting close to
Object-Oriented Programming with classes and objects. You are right. OOP was
the next phase of the ADT. But with OOP, computer scientists developed some
more powerful concepts.
Encapsulation:
A technique used to hide inner details.
Inheritance:
Classes can inherit properties from other classes.
Polymorphism:
Objects can determine appropriate operations at execution time.
This technique for problem solving has been around for a long time. It simply means try to state the problem in the form of a verb perhaps with an object. Then try to break the problem up using other verbs. We will look at examples of this later as we get into larger programs.
1.
Modularity
a.
Constructing the program
b.
Debugging the program
c.
Reading the program
d.
Modifying the program
e.
Eliminating redundant code
2.
Modifiability
a.
Methods
b.
Named Constants
3.
Ease of use
a.
Prompting for input
b.
Echoing input
4.
Fail-safe programming
5.
Guarding against
a.
Guarding against errors in input data
b.
Guarding against errors in program logic
6.
Style
a.
Extensive use of methods
b.
Use of private data fields
c.
Error handling
d.
Readability
e.
Documentation
7.
Debugging
a.
Debugging methods
b.
Debugging loops
c.
Debugging if statements
d.
Using System.out.println statements
e.
Using special dump methods
IN CLASS EXERCISES:
2. (p. 42) A date consists of a month, day and year. Frequently, we represent each of these items as integers. For example, July 4, 1776, is month 7, day 4, and year 1776.
a. Write a specification for a method that advances any given
date by one day. Include a statement of purpose, the pre- and post conditions,
and a description of the parameters.
b. Write a Java implementation of this method. Design and
specify any other methods that you need. Include comments that will be helpful
to someone who will maintain your implementation in the future.
4. This chapter stressed the importance of adding fail-safe checks to a program wherever possible. What can go wrong with the following method? How can you protect yourself?
public static double computation (double x) {
return java.lang.Math.sqrt(x)/java.lang.Math.cos(x);
} // end computation
You are to do either Programming Problem
# 2 or # 3 on page 44-45 in your text. I will make sure you understand each of
them before you start.