Introduction to Algorithms and Programming

Software development life cycle

Waterfall model

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.

  1. System requirements
    • Identify, select and document functional, scheduling and financial requirements.
    • Defines the purpose of the information system.
  2. 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.
  3. Analysis
    • Methodically work through the details of each requirement.
    • Document inputs, outputs, processing and algorithms.
    • Resolve problems, handle dependencies and develop plans to mitigate risks.
  4. 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.
  5. Coding
    • Implement the program as designed in the earlier stages.
    • The deliverable at the end of this stage is the software program.
  6. Testing
    • 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.
  7. Operations
    • 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

Other software development models

Types of debugging errors

Syntax 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:

Logic errors 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 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:

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)
  int ret=2;
  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 )
    return 1;

  int previousButOne = 1;
  int previous = 1;
  int answer = 2;
  for (int n = 2; n < position; ++n )
    previousButOne = previous;
    previous       = answer;
    answer         = previous + previousButOne;

  return answer;

Write source code comments to explain why – not how

Develop a methodical testing approach

Testing can prove the presence of problems, but, it can't prove the absence of problems.

Common examples of test values and conditions

Develop a methodical debugging approach

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.

  1. #include <stdio.h>
  3. int main( void )
  4. {
  5.   int card = 0;
  6.   int sum = 0;
  7.   int counter = 0;
  9.   do
  10.   {
  11.     scanf( "%d", &card );
  12.     sum = sum + card;
  13.     counter++;
  14.   } while ( counter < 3 );
  16.   printf( "Sum of cards is %d", sum );
  17. }