Introduction to Algorithms and Programming
Software development life cycle
The waterfall model
of software development consists of sequential stages
described by Dr Winston Royce in 1970 based on his experience developing software for spacecraft mission planning
- System requirements
- Identify, select and document functional, scheduling and financial requirements.
- Defines the purpose of the information system.
- Software requirements
- Identify, select and document the software features necessary to satisfy the system requirements.
- A deliverable at the end of this stage is the record of software requirements.
- Methodically work through the details of each requirement.
- Document inputs, outputs, processing and algorithms.
- Resolve problems, handle dependencies and develop plans to mitigate risks.
- Program design
- Use programming techniques to design software and hardware within the constraints and objectives set in the earlier stages.
- A deliverable at the end of this stage is the design specification.
- Another deliverable is the test plan.
- Implement the program as designed in the earlier stages.
- The deliverable at the end of this stage is the software program.
- Test the software and record the results.
- A deliverable at the end of this stage is the updated test plan.
- Another deliverable is the updated design specification.
- The deliverable at the start of this stage is the operating manual.
- Deliver, install and configure the completed software.
- Provide maintenance and support of the software.
Importance of documentation
This is a quote from the original paper by Dr Winston Royce in 1970 to emphasize the importance of documentation as an indicator of project success:
"Occasionally I am called upon to review the progress of other software design efforts. My first step is to investigate the state of the documentation. If the documentation is in serious default my first recommendation is simple. Replace project management. Stop all activities not related to documentation. Bring the documentation up to acceptable standards. Management of software is simply impossible without a very high degree of documentation. As an example, let me offer the following estimates for comparison. In order to procure a 5 million dollar hardware device, I would expect that a 30 page specification would provide adequate detail to control the procurement. In order to procure 5 million dollars of software I would estimate a 1500 page specification is about right in order to achieve comparable control."
Benefits of software models that are based on the waterfall model
- Covers all aspects of a software project from conception until it is no longer in use.
- Predictable and suitable for project management techniques.
- Effective for projects that have well defined and stable requirements.
- Provides clear guidelines for allocation of skills and staff.
- Effective for new software that can be developed entirely within one project.
Other software development models
- V model
- Increase the emphasis on testing by making it a stage in parallel with coding.
- Provide a simulation for a subset of functionalities to clarify requirements between all participants in a software project.
- Rapid application development
- Emphasis on shorter iterations of the analysis, design, coding and testing stages for projects with frequently changing requirements.
- Spiral model
- Addition and emphasis on risk analysis stage at the start of each life cycle iteration.
- Addtional stages that support object oriented analysis and design.
- Agile methods
- An umbrella term for specific methods such as Extreme Programming and Scrum.
- Emphasis on short iterations where progress is measured by working software deliverables.
- Reduce documentation by increasing the use of code as design and documentation.
- Use automated and continuous regression tests.
Types of debugging errors
are caused by mistakes with the C language source code
. The compiler will not
run a program with syntax errors. Instead, it will try to display error messages as close as possible to the source of the syntax errors.
Habits to reduce syntax errors:
- Learn C language syntax
- Use spaces and indentation to make it easier to read source code
- Align opening and closing curly braces to make it easier to identify source code blocks
- Write source code in small incremental steps
- Compile source code frequently and save your work
are caused by mistakes in the algorithm or steps implemented by the programmer
. The program compiles and runs, but, the output or functions do not work as expected. These are often the most difficult to find and fix
Habits to reduce logic errors:
Run time errors
- Write source code in small incremental steps
- Display temporary messages while developing
- Do not write more source code than necessary
- Initialize variables at the time of declaration
- Organise your source code similar to program logic
- Use # to define constant values rather than raw numbers or text
are caused by input data or user actions which the program is not prepared to handle
. The program compiles normally and runs. But, the program runs into problems when unexpected input data is received
or the user performs an unexpected action.
Habits to reduce run time errors:
- Frequent source code testing
- Verify requirements and constraints of the problem
Examples of software errors
This quote is about a runtime error:
"Back in 1962, NASA sent the Mariner 1 probe to study Venus, but before the rocket carrying the probe could make its way into outer space, it veered off course and NASA had to prematurely detonate the rocket. According to one story, the program was supposed to contain a FOR NEXT loop that told the computer to loop three times, as in the following example:
FOR I = 1, 3
But, instead of a comma, the programmer had accidentally typed in a period, as follows:
FOR I = 1.3
So, instead of telling the computer to loop three times, this command told the computer to set the value of the variable I to 1.3. The end result was that this error managed to give the computer a valid but incorrect command, causing NASA to lose a multimillion dollar rocket and payload as a result."
This quote is about a logic error:
"The trouble with eradicating all logic bugs from a program is that you must examine your entire program for mistaken assumptions. Although programs may work perfectly fine during testing, they may encounter unexpected situations in the real world, causing the programs to fail catastrophically.
One prominent example of a logic bug occurred during the Falkland Islands War between Great Britain and Argentina. The British destroyer the H.M.S. Sheffield used an advanced computer air-defense system designed to protect the ship from air and missile attack. To prevent this air-defense system from shooting down its own missiles, the computers were programmed to allow certain friendly missiles to fly unmolested through its defenses. These friendly missiles included all the types of missiles that the British Navy used, which included the French-built Exocet antiship missile.
Unfortunately for the British, Argentina had also bought Exocet antiship missiles from the French, so when the Sheffield's computers detected the incoming Exocet missiles, they assumed the missiles were friendly and allowed them to pass uncontested through the Sheffield's air-defense system – and right into the Sheffield, sinking the ship with several direct hits.
Write source code to be read by people
int fval(int i)
for (int n1=1, n2=1, i2=i-3; i2>=0; --i2)
n1=n2; n2=ret; ret=n2+n1;
return (i<2) ? 1 : ret;
int fibonacci( int position )
if ( position < 2 )
int previousButOne = 1;
int previous = 1;
int answer = 2;
for (int n = 2; n < position; ++n )
previousButOne = previous;
previous = answer;
answer = previous + previousButOne;
Write source code comments to explain why – not how
- Do not write comments that duplicate the source code
- Re-write the source code if that could provide the same information as writing comments
- Do not use comments to explain how the source code was in the past
- Do not use comments to save unwanted or unused source code
- Do not use comments to make jokes or sarcasm
Develop a methodical testing approach
Testing can prove the presence of problems, but, it can't prove the absence of problems.
- Keep a written list of test conditions
- Think about testing before starting to write the program
- Black box testing checks that the program functions correctly and satisfy the required solution
- White box testing checks that the source code syntax and design are valid and correct
- Aim for a wide variety of tests to cover as much of the program functionalities as possible
- Avoid the use of global variables because they increase the dependency of source code in the program, which increase the complexity of testing
Common examples of test values and conditions
- Boundary values
- Minimum or maximum values
- One less
- One more
- Random values
- Ask random person next to you
- Pick random values from a website
- Zero values
- Divide by zero
- Empty text strings
- Missing input
- Carriage returns and other control characters
- Wrong data type values
- Text instead of numbers
- Numbers instead of text
- Fractions instead of whole numbers
- Negative values
Develop a methodical debugging approach
- Do not try to make random changes!
- For syntax and run time errors, use a divide and conquer approach to narrow down the area within the source code that is most likely to contain the fault
- For logic errors, try using a dry run table to verify that the source code is implementing the correct steps
- Make changes in small steps in order to avoid creating new faults while trying to fix the current fault
- Once you've fixed a fault, look in the source code to see if the fault occurs elsewhere
- Save source code regularly when debugging!
A dry run
is a manual step by step trace of the program logic and algorithm
. It uses a table where the first column is the step number and one column is added for each data variable used in the program. Each statement in the program increases the dry run table by one step.
int main( void )
int card = 0;
int sum = 0;
int counter = 0;
scanf( "%d", &card );
sum = sum + card;
} while ( counter < 3 );
printf( "Sum of cards is %d"
, sum )