CSC133 Intro to CS Using C++

Algorithms

The System Development Process

There are four phases in the system development process:

Analysis and Specification
1. Analysis: develop a clear understanding of the problem to be solved.
2. Specification: determine the requirements for the new system. Be specific about what type of solution the system is supposed to provide.
Design
1. System Design: determine a general structure for the system that will provide the required solution. Map out main components, the responsibility of each component, and how the components will connect to solve the overall problem.
2. Detailed Design: Create a step by step plan (or algorithm) describing how each component of the system will solve its part of the problem.
3. Verification: Check the design on some test cases to make sure it works correctly.
Implementation
1. Coding: write the statements in a programming language to follow the steps in the algorithm.
2. Testing and Debugging: run the program on some test cases, and check the results. If necessary, modify the program to correct any errors and test again.
Maintenance
1. Release: release the program to the users.
2. Maintain: modify the program to fix bugs found by the users and to add new features. Adding new features requires starting again at phase I.

In our class, I will take care of the Analysis and Specification phase. You will be responsible for the Design and Implementation phases. We will not need the Maintenance phase.

Algorithms

An algorithm is similar to a recipe. It details the steps that need to be followed, in order, to solve a particular problem.

Example

Let's say we needed to write a manual on how to change a flat tire in Spanish. We will assume we know how to speak Spanish, but English is our native language.

We begin by listing the steps required to change a flat tire in English. We write the steps in English first in order to outline the logical steps without having to think about the rules of the Spanish language. Here's one possible algorithm:

1. Park the car on a flat level surface.
2. If the ground is soft,
      place a piece of wood on the ground where the jack will be.
3. Take out the jack and the spare tire.
4. If there is a wheel cover,
      remove the wheel cover.
5. Loosen all the lug nuts.
6. Place the jack under the axle.
7. While the tire is still touching the ground,
      press the handle of the jack down until it clicks.
8. etc
9. etc

It might take several tries to get the algorithm right. To make sure the algorithm is correct, try it out. In this case, we need to change a tire on an actual car, using our algorithm. If we realize there is a problem, we need to modify our algorithm, and try it again. Once we're sure the algorithm is correct, then we can translate it into Spanish.

The preceding example is a problem that can't be solved by a computer. For a problem that we want to solve on a computer, we will follow the same process. We will write an algorithm in "pseudocode". Pseudocode looks like a program, but it doesn't follow the rules of a programming language, so you can concentrate on the logic needed to solve the problem without worrying about the rules of the language. There are no declarations, no semicolons, and no braces. The indentation is very important because it is the only way to indicate which statements are inside an if or loop.

An algorithm must be detailed enough so that you can check whether it solves the problem correctly. This means that you need to include all the calculations so that you can check whether your algorithm will produce the right answer.

Example

Write an algorithm to calculate the cost of car insurance. Everyone is charged a flat fee of $500.00. Each driving violation increases the premium by an additional $300.00. Read in a person's insurance policy number and the number of violations they have received. Print the policy number and the cost of their car insurance.

Here is the corresponding algorithm:

  read in the policy number
  read in the number of violations
  cost = 500.00
  violation cost = number of violations * 300.00
  total cost = cost + violation cost
  print policy number and total cost

The algorithm should be detailed enough so that someone else can use it to write a program without asking any questions.

Test Data

To test an algorithm or program, it is necessary to test all possible conditions in the program. For example, in the algorithm above, there are two conditions: no violations, and one or more violations. Therefore, there should be two tests:

Policy Num    Number of Violations
  123                0
  345                2  [or some other number greater than zero]

Example

Let's modify the requirements to calculate the cost of car insurance. The base insurance rate is based on a code, which is assigned by the company based on factors such as age, gender, and residential location. If the code is 1, the base rate is $500. If the code is 2, the base rate is $600. If the code is 3, the base rate is $700. Each driving violation increases the premium by an additional $300.00. Read in a person's insurance policy number, insurance code, and the number of violations they have received. Print the policy number and the cost of their car insurance.

Here is the corresponding algorithm:

  read in the policy number
  read in the insurance code
  read in the number of violations
  if code == 1
     cost = 500
  else if code == 2
     cost = 600
  else
     cost = 700
  violation cost = number of violations * 300.00
  total cost = cost + violation cost
  print policy number, insurance code, and total cost

Test Data

The new algorithm needs more data to be fully tested. It is necessary to test each insurance code in addition to testing for no violations/one or more violations. Therefore, we might have the following tests:

Policy Num     Ins Code      Number of Violations
  123             1               0
  345             2               4  [or some other positive number]
  567             3               1

The choice of pairing insurance code 1 and no violations is arbitrary. What is important is that all decision points in the program and all calculations are executed so that you can see whether the correct answer is produced. For example, if you never run the program with insurance code 3, you will never know whether that part of the program might contain an error.