What a Program Is, and What an Algorithm Is

5. Effectiveness. Every step must be basic enough that a person could carry it out exactly, with a pencil, in a finite time.

"Set X to the exact decimal value of one third" is not such a step. It is perfectly definite, and you know exactly what is meant, but the digits never end, so nobody can finish performing it. "Set X to 0.3333, correct to four decimal places" is a step. The test is not whether the instruction can be described; it is whether it can be performed.

A useful way to remember the five: an algorithm must stop, must be unambiguous, must know what it is given, must say what it found, and must be made of steps a human could actually perform.

Writing one out: simple interest

This is the first program on your practical list, so it is the first algorithm here.

To calculate simple interest taking principal, rate of interest and number of years as input from user.

The formula is the easy part. Simple interest is SI = (P R T) / 100, where P is the principal, R is the annual rate as a percentage, and T is the time in years.

The algorithm is written as numbered steps, with a Start and a Stop, and nothing else:

Step 1: Start
Step 2: Read P, R, T from the user
Step 3: Set SI = (P * R * T) / 100
Step 4: Display SI
Step 5: Stop

Read it against the five properties. It stops at step 5, so it is finite. Every step means one thing. Step 2 names its inputs. Step 4 produces the output. Every step could be done by hand. It is an algorithm.

Notice what is not in it: no mention of C, no printf, no data types, no semicolons. An algorithm is language independent, and that is the point of writing one. The same five steps become a C program, a Python program or a set of instructions to a clerk with a calculator.

Tracing it

An algorithm is checked by tracing: choosing values, walking the steps in order, and writing down what every quantity holds after each one. A trace table is how you prove to yourself, and to an examiner, that the thing works before a compiler is involved.

Take P as Rs 12,000, R as 8.5 per cent and T as 3 years.

The arithmetic: 12000 times 8.5 is 1,02,000, times 3 is 3,06,000, divided by 100 is Rs 3,060. A trace table with one row per step, and one column per quantity, is a habit worth forming now. In the loop chapters it stops being a formality and becomes the only reliable way to find a bug.

A second one, where a decision appears: the greatest of three numbers

Write a program to find greatest of three numbers using conditional operator.

Her practical names the C construct she wants, and the chapter on the conditional operator writes that program. The algorithm below names no construct at all, because an algorithm never does, and it is the same algorithm whichever one you finally reach for.

Simple interest had no decision in it. Most problems do. The moment a step depends on a comparison, the algorithm branches.

Step 1: Start
Step 2: Read A, B, C
Step 3: If A > B and A > C, then set MAX = A
Step 4: Otherwise, if B > C, then set MAX = B
Step 5: Otherwise, set MAX = C
Step 6: Display MAX
Step 7: Stop

Steps 3, 4 and 5 are one decision with three outcomes, not three separate decisions. Exactly one of them runs, and step 5 can afford to carry no condition at all precisely because steps 3 and 4 have already failed by the time it is reached.

Write them instead as three independent tests and that stops being true. Every one of them would then have to carry a condition of its own, including the last, or MAX would be overwritten with C on every run whatever steps 3 and 4 decided. All three would also be evaluated even after the answer was known.

Trace it with A as 14, B as 27 and C as 9. Step 3 asks whether 14 is greater than both 27 and 9; it is not, so MAX is not set to A. Step 4 asks whether 27 is greater than 9; it is, so MAX becomes 27. Step 5 is skipped because step 4 ran. Step 6 displays 27, which is correct.

Now trace it with all three equal, say 5, 5 and 5. Step 3 fails, because 5 is not greater than 5. Step 4 fails for the same reason. Step 5 runs and MAX becomes C, which is 5. Correct, but only just: the algorithm reaches the right answer through its last resort. Testing the equal case, the all-negative case and the two-equal case is what separates an algorithm that works from one that has only been tried once.

A third one, where the rule itself is the difficulty: the leap year

Write a program to check if the year entered is leap year or not.

Here the coding is trivial and the rule is the whole problem. Most students remember "divisible by 4" and stop. The full rule, as fixed by the Gregorian calendar, has three parts:

• a year divisible by 4 is a leap year,
• except that a year divisible by 100 is not,
• except that a year divisible by 400 is.

So 2024 is a leap year, 1900 was not, and 2000 was. Any algorithm that gets 1900 and 2000 both right has the rule; one that gets either wrong does not.

Step 1: Start
Step 2: Read Y
Step 3: If Y is divisible by 400, then set R = "Leap year"
Step 4: Otherwise, if Y is divisible by 100, then set R = "Not a leap year"
Step 5: Otherwise, if Y is divisible by 4, then set R = "Leap year"
Step 6: Otherwise, set R = "Not a leap year"
Step 7: Display R
Step 8: Stop

This has the same shape as the greatest of three: one decision with four outcomes, exactly one of which runs, and then a single Display that every path reaches. An algorithm with one way out is easier to check and easier to draw than one that finishes in four different places.

The order of the tests is the algorithm. Test 400 first, then 100, then 4, and each test can be simple because the ones before it have already removed the exceptions. Reverse the order and every test needs conditions bolted onto it.

Check it on the years that settle whether a rule is right:

From algorithm to program

Once the algorithm is right, writing the C is mechanical, and the rest of this book is how. The order never changes:

1. Understand the problem, and write down what is given and what is wanted.
2. Write the algorithm, in steps, in ordinary words.
3. Trace it by hand on values you have chosen to be awkward.
4. Only then, translate it into C.
5. Compile it, run it, and check it against the trace you already did.

Step 3 is the one that gets skipped, and skipping it is why a program that compiles cleanly still prints the wrong number. The compiler checks your grammar. Nothing but a trace checks your thinking.

What an examiner can ask on this, and how to answer it

"Define an algorithm and state its characteristics." Give the one-line definition, then the five properties with a word of explanation each. A bare list of five nouns is a weak answer; each property with the failure it prevents is a full one.

"Write an algorithm to ..." Number the steps, open with Start and close with Stop, name your inputs in a Read step, and finish with a Display step. Keep the steps in ordinary words: an algorithm written in C statements is no longer language independent, which is the one thing it exists to demonstrate.

"What is the difference between an algorithm and a program?" An algorithm is a finite sequence of unambiguous steps solving a problem, written in ordinary language, independent of any programming language and not executable by a machine. A program is that algorithm expressed in a particular programming language, following that language's grammar, and executable once translated. One is the solution; the other is the solution written down for a computer.

A trace question. You may be given a short algorithm and asked what it displays for stated inputs. Build the trace table. Do not read the algorithm and guess.