← Back to Subjects ororo.world

Chapter 3: Implementation of Algorithms to Solve Problems

Think of looking up a name in a printed telephone directory. Nobody starts at page one. You open somewhere near the middle, see whether the name you want falls before or after that page, and throw away the half that cannot contain it. Repeat, and a directory of a hundred thousand names surrenders in about seventeen looks. The method is so natural that most people invent it without being taught.

That method is an algorithm — a method of solution set out as a finite sequence of exact steps. It is also one of the most instructive failures in the history of computing. Donald Knuth, who traced its published history, records that the idea appeared in print as early as 1946, and yet well over a decade passed before a published version was correct for arrays of every size. The idea was obvious. The details were not. Programmers who understood the method perfectly still lost a name that sat at the very first position, or ran forever on a directory with a single entry, or slipped one place past the end of the list.

The lesson is the one this chapter is built on. Knowing roughly what to do is not the same as knowing exactly what to do, in what order, and for every possible input. Getting from the first to the second is the whole craft of algorithm design.

Diagram

Fig. 3.0-1 – a sorted list of eleven boxed names drawn as a horizontal strip; the middle box shaded and labelled “look here first”; a curly brace under the left half labelled “discarded in one step”; below it, the same strip redrawn with only the right half remaining and its own middle box shaded, showing the second look; caption strip on the right reading “each look halves what is left”

NoteCuriosity Corner

Q1. What turns an ordinary list of instructions into an algorithm? Are there conditions every algorithm must satisfy? Q2. Two students solve the same problem, one in Java and one in some other language. In what sense have they used the same algorithm? Q3. Halving a list sounds too simple to get wrong. Where exactly do the mistakes hide? Q4. How can you convince yourself that a method is correct before you ever type it into a computer? Q5. The word “algorithm” is not an English word at all. Whose name is it, and how did it reach English?

Each of these questions is answered somewhere in this chapter. Watch for them as you read.

3.1 Algorithms and Algorithmic Problem Solving

Every program you have written so far began, whether you noticed it or not, with a decision about method. Before a single line of Java was typed, you had already settled what the program would be given, what it had to produce, and roughly how it would get from one to the other. The typing came afterwards.

This chapter takes that hidden first stage and brings it into the open. The habit it builds is simple to state and slow to acquire: work out the method completely, in ordinary language, before you commit it to a programming language. A method written out this way is what we have been calling an algorithm.

The reason for the discipline is practical. A mistake in method that survives into code is expensive to find, because the compiler will not help you — a program can compile perfectly, run without complaint, and be wrong. A mistake in method caught on paper costs a pencil stroke.

3.1.1 What an Algorithm Is

Consider a task from a school office: given the marks a student has scored in five subjects, produce the total and the average. Written out as a method, it looks like this.

1. Read the five marks.
2. Add them to get the total.
3. Divide the total by 5 to get the average.
4. Display the total and the average.
5. Stop.

Four things are worth noticing about those steps, because they are the four things that make the difference between a method and a vague intention. The steps are finite in number. Each one is exact — there is no step that says “handle the marks somehow”. The steps are in an order, and the order matters, since you cannot divide a total you have not computed. And the method ends.

Notice also what the steps do not say. They do not say whether the marks are read from a keyboard, a file or a printed register. They do not say whether the average is stored in a variable called avg or average, or whether the language used is Java or any other. An algorithm fixes the method, not the machinery.

NoteDefinition

(An algorithm is a finite sequence of well-defined steps which, when carried out on any valid input, terminates after a finite number of steps and produces the required output.)

Read that definition slowly, because every phrase in it is doing work. Finite sequence rules out a method that goes on for ever. Well-defined rules out a step that two careful readers could carry out differently. Any valid input rules out a method that happens to work on the one example you tried. And terminates rules out a method that is still running when the examination hall closes.

Q. A cooking recipe has ordered steps and it ends. Is a recipe an algorithm?

A. Almost, but not quite. A recipe says “add salt to taste” and “bake until golden”, and two cooks will act on those differently. An algorithm allows no such latitude: every step must have exactly one meaning.

3.1.2 Where the Word Came From

The word is not an English one, and it is not really a word at all — it is a person’s name, worn down by nine centuries of use.

Muhammad ibn Musa al-Khwarizmi was a Persian mathematician and astronomer who worked in Baghdad in the early ninth century. He wrote a book explaining the Hindu–Arabic numerals and the methods of calculating with them — the place-value system with a symbol for zero that the whole world now uses. He wrote a second book on solving linear and quadratic equations, and from a phrase in its title, al-jabr, English gets the word “algebra”.

When European scholars translated his work into Latin in the twelfth century, they rendered his name as Algoritmi. The English scholar Adelard of Bath was among the translators who carried this material westward. For several hundred years afterwards, “algorism” meant simply calculating with the new numerals rather than with counters or Roman numerals. Only much later did the word broaden into its present sense: any finite, exact, step-by-step method for solving a problem.

The history is not decoration. Al-Khwarizmi’s contribution was precisely the modern one — he did not merely solve particular equations, he set down general procedures that anyone could follow to solve any equation of that form, without needing to be clever. That is what an algorithm still is.

Q5. The word “algorithm” is not an English word at all. Whose name is it, and how did it reach English?

A. It is the name of Muhammad ibn Musa al-Khwarizmi, a Persian mathematician and astronomer working in Baghdad in the early ninth century, whose book explained calculation with the Hindu–Arabic numerals. Twelfth-century Latin translators wrote his name as Algoritmi, which entered English as “algorism”, meaning calculation with those numerals. The word later widened to mean any finite, exact, step-by-step method of solution.

3.1.3 Properties of a Well-formed Algorithm

The definition in 3.1.1 packs several requirements into one sentence. It helps to separate them out, because when an algorithm goes wrong it is almost always because one specific requirement has been broken.

Finiteness means the algorithm stops after a finite number of steps, for every valid input. It is not enough that it stops on the input you tested. A method that halves a quantity again and again, waiting for it to reach exactly zero, will halt on some inputs and run for ever on others.

Definiteness means every step has exactly one meaning. A step such as “adjust the value suitably” fails this test; a step such as “subtract 1 from the value” passes it. Definiteness is what makes an algorithm mechanical, and being mechanical is the point — a machine cannot use judgement.

Every algorithm has zero or more input values, supplied to it before or during execution, and at least one output value, which is its whole reason for existing. An algorithm that computes something and displays nothing has done no useful work.

Effectiveness means every step is simple enough to be actually carried out, in finite time, with pencil and paper if necessary. “Divide 22 by 7” is effective. “Write down the exact decimal value of \(\pi\)” is not, because the writing never finishes.

Table 3.1 – the five properties of an algorithm, what each demands, and the symptom when it is violated

Property What it demands Symptom when violated
Finiteness Stops after a finite number of steps, on every valid input The program hangs; the loop never ends
Definiteness Every step has exactly one possible meaning Two people implement the same step differently
Input Zero or more values supplied to the algorithm The method has nothing to work on
Output At least one value produced as a result The program computes but reports nothing
Effectiveness Every step can actually be carried out in finite time A step is stated but cannot be performed

Finiteness is the property students break most often, and almost always in the same way: a repetition whose stopping condition never becomes true. Suppose a method is meant to keep subtracting 3 from a number until the number is exactly 0. For 12 it terminates. For 13 it never does — the value passes straight through 0 to \(-2\), and the condition it is waiting for is gone for ever. The flow in Fig. 3.1-1 shows the shape of that failure.

Diagram

Fig. 3.1-1 – flow: start → read value N → check “is N equal to 0?” → if no, N ← N − 3 → arrow returning to the check → if yes, display “finished” → stop; label the return arrow “for N = 13 this path is taken for ever” and mark the two branches “yes” and “no”

The repair is not to test more inputs but to state a condition that must eventually become true: keep subtracting while the value is greater than 0. Now the value strictly decreases at every pass and cannot avoid crossing the boundary, so the method halts for every starting number.

Q1. What turns an ordinary list of instructions into an algorithm? Are there conditions every algorithm must satisfy?

A. There are five. The steps must be finite in number and must stop for every valid input (finiteness); each step must have exactly one meaning (definiteness); the method takes zero or more inputs and must produce at least one output; and every step must be one that can actually be carried out in finite time (effectiveness). A list of instructions that fails any of these is not an algorithm, however sensible it sounds.

3.1.4 What Algorithms Give You, and What They Do Not

Writing the method down before coding it buys you four things.

It separates thinking from typing. Deciding what to do and deciding how to say it in Java are different kinds of work, and doing them at the same time is why students stare at a half-written program without knowing what is wrong.

It is independent of language. The same algorithm can be implemented in Java by one person and in another language by someone else, and it remains the same algorithm. This is why algorithms outlive the languages they were first coded in.

It can be checked before it is coded. You can trace an algorithm on paper with a sample input and see what it produces, which is the subject of section 3.4.

And it can be discussed. Two people can argue about a method written in ordinary steps far more easily than about two hundred lines of code.

Against this, three honest limitations.

Writing an algorithm takes time, and for a task of three or four steps that time is not repaid. Nobody writes an algorithm to swap two variables.

Repetition and branching are clumsy to express on paper. Code has braces and indentation to show exactly where a loop ends; a written algorithm has to say endwhile and hope the reader is paying attention. This is why the conventions in section 3.2.2 matter so much.

And for a genuinely large problem, a single flat list of steps becomes unreadable long before it becomes complete. Large problems are broken into smaller named methods, each with its own small algorithm — which is exactly what you did in Class XI when you first wrote a method instead of one enormous main.

There is one further limitation worth stating plainly, because it is easy to forget. An algorithm can be perfectly finite, perfectly definite and perfectly effective, and still solve the wrong problem. Correctness is always correctness with respect to a specification. If the specification was misread, no amount of care in the steps will rescue it.

Take a procedure you carry out without thinking — issuing a book at the school library counter, or working out the change due at a shop till — and write it as numbered steps, on paper. Then hand it to a classmate and ask them to point at any step that could be carried out in more than one way. Rewrite those steps until none is left.

3.2 Ways of Representing an Algorithm

An algorithm is a method, and a method has to be written down somehow before anyone else can read it. There is no single official notation. What matters is that the reader can carry out your steps without guessing, and that you can see at a glance where a repetition begins and ends.

Three forms are in common use: the step-and-description form, pseudocode, and the flowchart. They are not three different algorithms. They are three ways of writing the same one, and it is worth seeing a single method in all three so that the differences stand out.

The method we shall use throughout this section is deliberately small. A city bus charges a flat fare of ₹10 for the first 5 kilometres of a journey, and ₹4 for every kilometre after that. Given the distance travelled, compute the fare.

3.2.1 The Step-and-Description Form

This is the form you will see most often in Computer Science answer scripts, and it has two parts.

First comes a short preamble in square brackets, naming the quantities the algorithm works with and saying what each one holds. This is not decoration; a reader who does not know what DIST stands for cannot check your steps.

Then come the steps themselves, numbered in Roman or ordinary numerals. Each step opens with its purpose in square brackets — a one-line description of what this step achieves — followed by the actions that achieve it.

[DIST is the distance of the journey in kilometres and FARE is the amount payable.
 The fare is ₹10 for the first 5 km and ₹4 for every kilometre beyond that.]

I.    [Read the journey distance]
      Read DIST

II.   [Compute the fare according to the distance]
      if (DIST <= 5) then
          FARE ← 10
      else
          FARE ← 10 + 4 × (DIST − 5)
      endif

III.  [Report the result]
      Display("Fare = ", FARE)

IV.   Stop

The bracketed descriptions are what make this form readable. Strip them away and you are left with a small block of near-code that a reader has to decipher line by line. Keep them, and the shape of the method — read, decide, report — is visible in a single glance.

Notice the symbol ←. It means “gets the value of”, and it is the standard way of writing assignment in an algorithm. Writing FARE = 10 invites confusion with the mathematical claim that FARE and 10 are equal; the arrow says clearly that a value is being placed into a named store.

3.2.2 Pseudocode Conventions Used in This Book

Pseudocode is a way of writing an algorithm that borrows the structure of a programming language — assignment, conditions, loops, indentation — while keeping the vocabulary of ordinary English. It obeys no compiler, so no punctuation is compulsory; but it must be consistent, or it stops being readable.

The conventions in Table 3.2 are used for every algorithm in this book. Learn them once and you will not have to decode a fresh notation in each section.

Table 3.2 – pseudocode notation used throughout this book, with the meaning of each form

Notation Meaning
X ← expression Assignment: evaluate the expression and store the result in X
Read X or Accept X Take a value from the user and store it in X
Display(...) Show the listed values to the user
if (condition) then ... else ... endif Selection: carry out one of two alternatives
Repeat while (condition) ... endwhile Repetition: test first, repeat as long as the condition holds
Repeat for I = a, a+1, ..., b ... endfor Repetition a known number of times, I taking each value in turn
[ ... ] A comment: the purpose of a step, or a note about the variables
Stop End of the algorithm
Return End of a named sub-algorithm, giving control back to the caller

Two rules matter more than the rest.

Indent the body of every selection and every repetition, and close it explicitly with endif, endwhile or endfor. On paper there are no braces, so the closing word is the only thing telling your reader where the repeated part stops. An algorithm whose loop has no visible end is a genuine ambiguity, and by the standard of section 3.1.3 it fails definiteness.

Use Repeat while when you do not know in advance how many passes are needed, and Repeat for when you do. The bus fare method needs neither, since it makes one decision and stops.

Here is the same method in pseudocode, without the step-and-description scaffolding.

Read DIST
if (DIST <= 5) then
    FARE ← 10
else
    FARE ← 10 + 4 × (DIST − 5)
endif
Display("Fare = ", FARE)
Stop

Q. If pseudocode is closer to code, why not simply write the Java and skip a stage?

A. Because Java forces decisions the method does not yet need — the type of every variable, the exact class name, where the semicolons go. Deferring those decisions lets you concentrate on whether the method is right, which is the harder question.

3.2.3 Flowcharts

A flowchart is a diagram of an algorithm, in which each step is a labelled shape and arrows show the order in which the steps are carried out. The shape itself carries meaning, so a reader can tell a decision from a calculation without reading a word. The five standard symbols are shown in Fig. 3.2-1.

Diagram

Fig. 3.2-1 – the five flowchart symbols drawn in a vertical column, each with its name to the right: an oval labelled “Terminal – Start or Stop”; a parallelogram labelled “Input / Output – Read or Display”; a rectangle labelled “Process – calculation or assignment”; a diamond labelled “Decision – a condition with two exits, Yes and No”; a plain arrow labelled “Flow line – order of execution”

Read the symbols this way. Every flowchart begins and ends with an oval. A parallelogram is where data enters or leaves. A rectangle changes the value of something. A diamond asks a question and has exactly two outgoing arrows, one marked Yes and one marked No. The arrows, not the position on the page, decide the order.

Fig. 3.2-2 is the bus fare method as a flowchart. Compare it with the pseudocode above, line for shape: the Read becomes a parallelogram, the if becomes a diamond, each of the two fare calculations becomes a rectangle, and the two branches rejoin before the result is displayed.

Diagram

Fig. 3.2-2 – flowchart of the bus fare method; oval “Start” at the top; parallelogram “Read DIST”; diamond “DIST <= 5 ?” with the Yes branch on the left leading to a rectangle “FARE ← 10” and the No branch on the right leading to a rectangle “FARE ← 10 + 4 × (DIST − 5)”; both branches joined by arrows into a parallelogram “Display FARE”; oval “Stop” at the bottom

The rejoining is worth dwelling on. Both branches lead to the same display step, because the fare is reported once, whichever way it was worked out. A flowchart in which the two arms of a decision never come back together is usually a sign that the same step has been drawn twice by mistake.

Flowcharts are excellent for small methods and for explaining control flow to someone seeing it for the first time. They stop being useful quickly. A method of forty steps with three nested repetitions produces a diagram that spills across pages and is harder to follow than the pseudocode it came from. For anything beyond a page, write the steps.

3.2.4 Algorithm, Program and Language Independence

A program is an algorithm expressed in a programming language, in a form a computer can be made to execute. The relationship is one of expression, not of identity — the algorithm is the method, the program is one particular way of saying it.

That distinction explains the single most useful property of an algorithm: it is language independent. The bus fare method above says nothing about Java. Rendered in Java it would need a class, a main method, a declared type for DIST, and a semicolon after every statement. Rendered in another language it would need a different set of ceremonies. The method underneath — read, compare against 5, compute one of two amounts, display — does not change, and two students who write those different programs have implemented the same algorithm.

Table 3.3 – Algorithm vs Program

Feature Algorithm Program
Nature A method of solution, written for a human reader An implementation of that method, written for a machine
Language Ordinary language with a fixed notation; no compiler A specific programming language, such as Java
Rules of form Conventions only; no error is possible in the notation itself Strict syntax; a missing semicolon prevents compilation
Execution Cannot be executed; it is carried out by hand or implemented first Executed directly after compilation
Detail required Types, declarations and class structure are left out Every type, declaration and structure must be stated
Checking Verified by reasoning and by tracing on paper Verified by compiling, running and testing on inputs

There is one direction of travel that is not symmetric. Every program embodies some algorithm, even a badly written one. But not every algorithm needs to become a program — it may be carried out by a person, or used only to compare two possible approaches before either is coded.

Q2. Two students solve the same problem, one in Java and one in some other language. In what sense have they used the same algorithm?

A. In the sense that matters. An algorithm fixes the method — what is read, what is compared, what is computed, in what order — and says nothing about the language used to express it. The two programs will differ in declarations, syntax and class structure, all of which belong to the language rather than to the method. If the sequence of decisions and calculations is the same, the algorithm is the same.

Redraw the bus fare flowchart of Fig. 3.2-2 for a revised rule: the flat fare of ₹10 covers the first 5 km, the next 10 km cost ₹4 each, and every kilometre beyond 15 costs ₹3. How many diamonds does your flowchart now need, and where do the branches rejoin?

3.3 Designing an Algorithm

Knowing what an algorithm is does not tell you how to produce one. Faced with a fresh problem, most students begin in the middle — they start writing steps before they have decided what the steps are meant to achieve, and then patch the result until it looks plausible.

There is a better order of work, and it is the order this section follows. Read the problem until you can state exactly what goes in and what must come out. Decide the shape of the method from the three building blocks available to you. Choose your variables and say what each one holds. Only then write the steps.

The problem we shall build is this. A class of N students has appeared in a test. Given each student’s marks, find how many students scored at least the qualifying mark of 35, and report that count together with the percentage of the class it represents.

3.3.1 Reading the Problem: Input, Output and Constraints

Three questions have to be answered before anything is written, and answering them badly is the commonest cause of a correct-looking method that solves the wrong problem.

What is the input? Not “the marks”, but precisely: one integer N giving the number of students, followed by N marks. Notice that N is itself an input, and that it arrives before the marks — you cannot read the marks until you know how many there are.

What is the output? Two values: a count of qualifying students, and a percentage. Saying this now prevents the common slip of computing the count and forgetting the percentage entirely.

What constraints apply? A class size must be positive. Marks in a test lie in a fixed range. Constraints matter because they tell you which inputs your method must cope with and which it may refuse.

Table 3.4 – specification of the qualifying-count problem

Aspect Statement
Input An integer N, the number of students; then N marks, one per student
Output The number of students scoring 35 or more, and that number as a percentage of N
Constraints N must be greater than 0; marks are whole numbers
Behaviour on invalid input If N is not positive, report the fact and stop without computing anything

The last row is the one students leave out. A specification that says nothing about bad input leaves the decision to whoever writes the code, and it will be made carelessly. Here the decision is deliberate: with no students there is nothing to count and no percentage to compute, since dividing by zero is not defined.

Q. Why refuse N = 0 rather than simply reporting a count of zero?

A. The count would indeed be zero, but the percentage would require dividing zero by zero. Rather than produce a meaningless second output, the method declines the input outright — and says so, so the user knows why nothing was computed.

3.3.2 Building Steps from Sequence, Selection and Repetition

Whatever the problem, the steps of an algorithm are assembled from just three ways of arranging work. This is not a rule of thumb; it is a result about computation, and it is why every programming language you will meet offers the same three facilities under different names.

Sequence is one step after another, each carried out exactly once, in written order. Selection is a choice between alternatives, governed by a condition — one arm is carried out and the other is not. Repetition is a group of steps carried out again and again while some condition holds. Fig. 3.3-1 shows the three shapes side by side.

Diagram

Fig. 3.3-1 – three small flow fragments drawn side by side and labelled; left, “Sequence”: three stacked rectangles joined by downward arrows; centre, “Selection”: a diamond with a Yes branch to one rectangle and a No branch to another, both arrows rejoining below; right, “Repetition”: a diamond labelled “condition true?” with a Yes branch into a rectangle whose arrow loops back up to the diamond, and a No branch leaving downwards

Designing the method now becomes a question of arrangement. The outer shape of our problem is a sequence of three things: read the class size, examine every student, report the findings. The middle one of those must happen once per student, so it is a repetition. Inside that repetition, each student either qualifies or does not, so there is a selection. The structure is visible before a single detail is filled in.

Read N
Repeat once for each student
    if this student qualifies then record the fact
Report the count and the percentage

That skeleton is worth writing down on rough paper for any problem. It is much easier to notice that a step is missing from four lines than from forty.

Filling in the detail needs one further idea. To know at the end how many students qualified, something must remember how many have qualified so far. A variable used for this purpose is a counter: it is set to zero before the repetition begins, and increased by one each time the event it counts occurs.

The placement of that initialisation is not a detail. Set the counter to zero before the repetition and it accumulates across all N students. Set it to zero inside the repetition and it is wiped clean on every pass, so the final value can never exceed one. The step is in the right place only if it happens once, and the repetition is exactly the region where “once” is not guaranteed.

Counting the students who qualify Input: An integer N greater than 0, followed by N marks. Output: The number of students scoring 35 or more, and that number as a percentage of N. Method:

[N is the number of students; MARK holds one student's marks as it is read;
 COUNT is the number who have qualified so far; I is the loop counter;
 PCT is the percentage of the class that qualified.]

I.    [Read the class size and reject an impossible one]
      Read N
      if (N <= 0) then
          Display("Invalid class size")
          Stop
      endif

II.   [Nobody has qualified yet]
      COUNT ← 0

III.  [Examine each student's marks in turn]
      Repeat for I = 1, 2, ..., N
          Read MARK
          if (MARK >= 35) then
              COUNT ← COUNT + 1
          endif
      endfor

IV.   [Report both results]
      PCT ← COUNT × 100 / N
      Display("Qualified = ", COUNT)
      Display("Percentage = ", PCT)

V.    Stop

Why it works: Before the repetition begins, COUNT correctly records the qualifiers among the zero students examined so far. Each pass reads one further student and increases COUNT exactly when that student qualifies, so if COUNT was correct before the pass it is correct after it. After N passes every student has been examined once, so COUNT is the total number of qualifiers. Cost: N marks are read and N comparisons are made. The work grows in direct proportion to the size of the class, and no student is examined twice.

The argument under Why it works is the useful part of the box, and it is the part students skip. It is a statement about what remains true every time round the loop — that COUNT holds the number of qualifiers among the students seen so far. A claim of that kind, true before the loop and preserved by each pass, is what turns “it seems to work” into “it must work”.

3.3.3 Choosing and Describing the Variables

Every variable in an algorithm should have exactly one job, and its name should say what that job is. COUNT holds a count; PCT holds a percentage. A variable named X holds whatever the reader can guess, which is the problem.

Three habits keep the variable list honest.

Give a variable one purpose only. Reusing MARK later in the same method to hold a percentage saves nothing and costs a reader their bearings.

Do not introduce a variable you never read back. A variable that is assigned and then ignored is either a leftover from an earlier attempt or a step you meant to write and did not; both are worth noticing.

Introduce a variable at the point where it first has a meaning. PCT appears only in step IV, because before the count is complete there is no percentage to speak of.

The variable description table sets all of this out for the reader: every variable the method uses, the kind of value it holds, and its purpose. It is written alongside the algorithm, not afterwards from memory, and it is a required part of the documentation for any program you submit.

Table 3.5 – variable description for the qualifying-count algorithm

Variable Type Purpose
N Integer Number of students in the class
MARK Integer Marks of the student currently being examined
COUNT Integer Number of students who have qualified so far
I Integer Loop counter, running from 1 to N
PCT Real Percentage of the class that qualified

Notice that PCT is the only real quantity in the table. Everything else counts things, and things are counted in whole numbers. Deciding this at the design stage saves you from discovering it later, when the program reports that 3 students out of 8 are 0 per cent of the class.

3.3.4 Guidelines for Writing Clear Steps

The rules below are not style preferences. Each one prevents a specific failure that appears again and again in written algorithms.

Say what a step is for

Give every step its bracketed purpose. If you cannot state in one line what a step achieves, the step is doing more than one thing and should be split.

Keep each step unambiguous

“Adjust the total” and “process the array” are not steps. Write the operation itself: COUNT ← COUNT + 1. The test is simple — could two readers carry this out differently? If so, rewrite it.

Make the order of operations explicit

In step IV the percentage is written COUNT × 100 / N rather than COUNT / N × 100. On paper the two look equal, and in exact arithmetic they are. In a program they are not: with 3 qualifiers out of 8, dividing first gives zero and multiplying afterwards leaves it zero. Multiply first and the answer is 37.5. Write the form you actually want, and do not rely on the reader to rearrange it kindly.

Close every branch and every loop

Every if needs its endif and every repetition its endwhile or endfor. An unclosed branch leaves the reader guessing which steps are inside it, and a method that can be read two ways has failed the test of definiteness from section 3.1.3.

Use no more variables than the method needs

Extra variables do not make an algorithm safer; they make it harder to check, because every one of them is a value that has to be kept correct. Before adding a variable, ask what question it answers that no existing variable answers.

Make sure the repetition can end

Every loop must contain something that moves it towards its stopping condition. In step III the counter I advances on every pass, so after N passes the repetition is over. When a loop is controlled by a condition rather than a count, check explicitly that the condition can become false — this is the finiteness requirement, and it is not automatic.

Deal with the awkward input in the algorithm, not afterwards

Step I rejects a class size of zero or less. It is tempting to leave such checks out of the written method and add them when coding, but an input the algorithm never considered is an input nobody has thought about.

Rewrite the qualifying-count algorithm so that it also reports how many students did not qualify, using no variable other than the five already in Table 3.5. Then say in one line why no sixth variable is needed.

3.4 Checking an Algorithm: The Dry Run

An algorithm on paper cannot be run. There is no compiler to reject it and no machine to execute it, which is exactly why a written method can look convincing and still be wrong. Something has to take the place of the computer, and that something is you.

A dry run is the act of carrying out an algorithm by hand on a chosen input, writing down the value of every variable after every step, and comparing the result the method produces with the result the specification demands. It is slow, it is unglamorous, and it finds more errors per hour than any other technique available to a student.

NoteDefinition

(A dry run is the manual execution of an algorithm on a specific input, recording the value of every variable after each step, in order to check that the output produced is the output required.)

3.4.1 Tracing Step by Step

The discipline of a dry run lies in the record. Working the steps in your head proves nothing, because the head quietly corrects small mistakes as it goes; the point of writing every value down is that the paper does not.

Set the trace out as a table. Give one column to each variable that changes, one row to each pass of the repetition, and a final column for anything the algorithm displays. Then work strictly by what the steps say, not by what you meant them to say.

Take the qualifying-count algorithm of section 3.3.2 and run it on a class of five, with marks 41, 28, 35, 60 and 12. By hand, three of those five reach 35, so the method should report a count of 3 and a percentage of 60.

the qualifying-count algorithm, on N = 5 with marks 41, 28, 35, 60, 12

Pass (I) MARK read Is MARK ≥ 35? COUNT after the pass Displayed
— (before the loop) — — 0 —
1 41 Yes 1 —
2 28 No 1 —
3 35 Yes 2 —
4 60 Yes 3 —
5 12 No 3 —
— (after the loop) — — 3 Qualified = 3
— — — 3 Percentage = 60

Result: the method reports a count of 3 and a percentage of 60, which agrees with the hand answer. The trace also shows the counter behaving as the correctness argument claimed — after each pass, COUNT holds the number of qualifiers among the students examined so far, and never anything else.

Three habits make a trace trustworthy.

Include a row for the state before the loop begins. Errors of initialisation are invisible if the table starts at the first pass, and initialisation is where a large share of them live.

Record the value after every pass, even when nothing changed. Pass 2 above changes nothing, and writing the unchanged 1 is what confirms you actually considered it.

Never write the value you expect. Write the value the step produces. A trace that agrees with your expectations at every point has usually been copied from your expectations.

Q. If the trace matches the hand answer, is the algorithm proved correct?

A. No. A trace tests one input. It can show that a method is wrong, but no number of successful traces can show that it is right for every input. Proof comes from the reasoning argument; the trace is what catches the places where the reasoning was careless.

3.4.2 Boundary Values and Special Cases

If a trace can only ever test one input, the inputs you choose matter enormously. Testing 5, then 6, then 7 tells you almost nothing beyond what 5 told you. The inputs that find errors are the ones sitting at the edges of the method’s behaviour.

A boundary value is an input lying exactly at the point where the behaviour of an algorithm changes: the smallest value it accepts, the largest, the value at which a condition switches from false to true, or a case where a repetition runs the fewest possible number of times.

Table 3.6 lists the boundary cases worth trying for the qualifying-count problem, and what each one is designed to catch.

Table 3.6 – boundary cases for the qualifying-count algorithm, and the error each is meant to expose

Case to try Input What must happen Error it exposes
Smallest valid class N = 1, mark 50 Count 1, percentage 100 A loop written to run N − 1 times
Invalid class size N = 0 Message displayed, nothing computed Division by zero
Mark exactly at the qualifying value N = 1, mark 35 Count 1, percentage 100 The wrong comparison operator
Mark just below it N = 1, mark 34 Count 0, percentage 0 The same, in the other direction
Nobody qualifies N = 4, marks 10, 20, 30, 12 Count 0, percentage 0 A counter never initialised
Everyone qualifies N = 4, marks 40, 50, 60, 90 Count 4, percentage 100 A loop that stops one pass early

The third case is worth working through, because it is the one that separates a method that happens to be right from one that is right on purpose. The specification says a student qualifies on scoring at least 35, so a mark of exactly 35 must be counted.

the qualifying-count algorithm, on N = 1 with a single mark of exactly 35

Pass (I) MARK read Is MARK ≥ 35? COUNT after the pass Displayed
— (before the loop) — — 0 —
1 35 Yes 1 —
— (after the loop) — — 1 Qualified = 1
— — — 1 Percentage = 100

Result: the student is counted, as the specification requires. Had step III been written if (MARK > 35), this same trace would end with a count of 0 and a percentage of 0 — and the earlier trace, on 41, 28, 35, 60, 12, would have reported 2 instead of 3. One character decides it.

A mistake of this kind, where a method is correct except at the very edge of a range, is an off-by-one error. It comes in a small number of recognisable shapes: > written for ≥, a loop running from 1 to N − 1 when it should reach N, an array index one past the last element. None of them shows up when you test a comfortable input in the middle of the range, which is precisely why comfortable inputs are the wrong ones to test.

There is a further class of special cases to think about: inputs that are valid but unusual. An empty list, a list with one element, a list in which every value is identical, a list already in the order you were asked to produce. Methods that assume “there will be at least two of them” tend to fail on exactly these.

3.4.3 Why an Algorithm Terminates

A trace that runs for ever cannot be completed on paper, and a trace that you stop after six passes tells you nothing about the seventh. Termination therefore has to be argued, not observed.

The argument has a standard shape. Find some quantity that changes on every pass of the repetition, show that it moves steadily in one direction, and show that the stopping condition must be reached once it has moved far enough. In the qualifying-count algorithm that quantity is the counter I: it increases by one every pass, and the repetition ends when it has passed N. Since N is fixed before the loop begins, the end is guaranteed.

Now consider a repetition written like this, intended to visit every second position from 0 up to N.

I ← 0
Repeat while (I ≠ N)
    Display(I)
    I ← I + 2
endwhile

For N = 8 it displays 0, 2, 4, 6 and stops. For N = 7 it displays 0, 2, 4, 6 and then 8, 10, 12, and never stops, because I steps straight over 7 and the equality it is waiting for never occurs. The quantity does move steadily, but the stopping condition is a single point that the movement can miss.

The repair is to test a direction rather than a point.

I ← 0
Repeat while (I < N)
    Display(I)
    I ← I + 2
endwhile

Now the condition is not a target to be hit but a region to be left, and I cannot increase for ever without leaving it. As a working rule: when a loop variable advances by more than one, or by an amount you compute, never control the loop with ≠ or =.

Termination can also depend on the input rather than on the method. A loop that keeps reading values until the user enters a sentinel value — a special value such as −1, agreed in advance to mean “no more data” — ends only if that value is eventually supplied. Such a method is finite for every valid input, which is what the definition of an algorithm requires; but the specification must say what the sentinel is, or the user has no way of stopping it.

Q4. How can you convince yourself that a method is correct before you ever type it into a computer?

A. By doing three things, none of which needs a machine. First, argue why it works: state what remains true after every pass of each repetition, and show that this is enough to give the required output at the end. Second, dry run it — carry out the steps by hand on chosen inputs, recording every variable’s value in a table, and compare the result with the answer worked out independently. Choose the inputs at the boundaries, where behaviour changes, rather than comfortable ones in the middle. Third, show that every repetition must end, by identifying a quantity that moves steadily towards the stopping condition. A dry run alone cannot prove correctness, because it tests one input at a time; combined with the reasoning argument, it is what catches the places where the reasoning was careless.

Dry run the qualifying-count algorithm on a class of four whose marks are 34, 35, 36 and 33, writing out the full table on paper. Then repeat the trace with step III altered to if (MARK > 35) and note in one line which rows of the table differ.

3.5 Algorithms for Number Problems

The problems in this section share a family resemblance. Each takes one or two numbers, works on them arithmetically, and reports something the numbers do not display on their face — the nature of the roots of an equation, the largest divisor two numbers have in common, whether a number has any divisors at all, what its digits add up to.

They are worth studying together because the techniques recur. Guarding against an input the formula cannot handle, replacing a pair of values by a smaller pair that has the same answer, searching for a divisor without searching further than necessary, peeling a number apart one digit at a time — these appear again in problems that look nothing like these.

3.5.1 Roots of a Quadratic Equation

A quadratic equation is written \(ax^2 + bx + c = 0\), and its roots are given by the familiar formula. What makes it an interesting algorithm rather than a single line of arithmetic is that the formula behaves in three different ways, and the method has to decide which one applies before it computes anything.

The deciding quantity is the discriminant, \(d = b^2 - 4ac\). If \(d\) is negative, the square root cannot be taken among the real numbers and the roots are imaginary. If \(d\) is zero, the two roots coincide and there is really only one value, \(-b/2a\). If \(d\) is positive, there are two distinct real roots. Fig. 3.5-1 shows what the three cases look like as curves.

Diagram

Fig. 3.5-1 – three small graphs side by side, each showing a parabola against a horizontal x-axis; left graph labelled “d > 0 : two real distinct roots” with the curve cutting the axis at two marked points; centre graph labelled “d = 0 : two equal roots” with the curve touching the axis at one marked point; right graph labelled “d < 0 : roots are imaginary” with the curve lying entirely above the axis and not meeting it

One constraint has to be stated before any of this is safe. If \(a\) is zero the equation is not quadratic at all, and worse, the formula divides by \(2a\) — that is, by zero. A method that silently accepts \(a = 0\) is not incomplete, it is wrong, so the check belongs in step I.

Finding the roots of a quadratic equation Input: Three coefficients A, B and C of the equation \(Ax^2 + Bx + C = 0\), with A not equal to 0. Output: The nature of the roots, and the roots themselves when they are real. Method:

[A, B and C are the coefficients of the equation. D is the discriminant.
 R holds the single value when the roots are equal; R1 and R2 hold the two
 roots when they are real and distinct.]

I.    [Read the coefficients and reject an equation that is not quadratic]
      Read A, B, C
      if (A = 0) then
          Display("Not a quadratic equation")
          Stop
      endif

II.   [Compute the discriminant]
      D ← B × B − 4 × A × C

III.  [Decide the nature of the roots and compute them]
      if (D < 0) then
          Display("Roots are imaginary")
      else
          if (D = 0) then
              R ← −B / (2 × A)
              Display("Roots are equal, both are ", R)
          else
              R1 ← (−B + √D) / (2 × A)
              R2 ← (−B − √D) / (2 × A)
              Display("Roots are real and distinct : ", R1, R2)
          endif
      endif

IV.   Stop

Why it works: The sign of D decides which of the three cases holds, and the three cases are exhaustive — a real number is negative, zero or positive and nothing else. Within each case the formula for that case is applied unchanged. Cost: A fixed number of steps, whatever the coefficients. Nothing here is repeated.

Two details in step III repay attention.

The brackets around \(2 \times A\) are not optional. Written as −B / 2 × A, the expression divides by 2 and then multiplies by A, which is a different number entirely. On paper the notation \(\frac{-b}{2a}\) makes the grouping obvious; in a linear expression you must supply it yourself.

The nested selection tests D < 0 first and splits the remaining possibilities afterwards. Any of the three orders would work, but each branch must be reached under exactly one condition. A method that tests D < 0, then D > 0, then assumes the rest is D = 0 is correct; a method that tests D <= 0 and then D = 0 inside it is a trap waiting to be sprung.

the quadratic-roots algorithm, on A = 1, B = −5, C = 6

Step Quantity computed Value
I A, B, C read; A ≠ 0 so the method continues 1, −5, 6
II D ← B × B − 4 × A × C 25 − 24 = 1
III D < 0 ? No
III D = 0 ? No
III R1 ← (5 + 1) / 2 3
III R2 ← (5 − 1) / 2 2
III Displayed Roots are real and distinct : 3, 2

Result: the roots 3 and 2 are produced, which is right — \(x^2 - 5x + 6\) factorises as \((x-3)(x-2)\). Substituting either value back into the equation is a check you can make in seconds, and it is worth making.

Trace the same algorithm on A = 1, B = 4, C = 4 and on A = 1, B = 1, C = 5, writing down D in each case. Which branch of step III does each input take, and what is displayed?

3.5.2 Greatest Common Divisor by Euclid’s Method

The greatest common divisor of two positive integers is the largest number that divides both of them exactly. The obvious method is to try every number from the smaller of the two downwards until one divides both; for 84 and 36 that means testing 36, 35, 34 and so on down to 12. It works, and for large numbers it is hopeless.

Euclid’s method replaces the obvious search with an observation. Any number that divides both A and B also divides the remainder when A is divided by B — and conversely. So the pair \((A, B)\) and the pair \((B, A \bmod B)\) have exactly the same set of common divisors, and therefore the same greatest one. The second pair is smaller. Keep replacing, and the numbers shrink rapidly until one of them becomes zero; the other is then the answer, because every number divides 0 and the largest divisor of A is A itself.

Here A mod B means the remainder left when A is divided by B, the operation written % in Java.

Greatest common divisor by Euclid’s division method Input: Two integers M and N, both greater than 0. Output: The greatest common divisor of M and N. Method:

[M and N are the numbers whose greatest common divisor is required.
 A and B hold the current pair, and R holds the remainder at each stage.]

I.    [Read the numbers and reject non-positive input]
      Read M, N
      if (M <= 0 or N <= 0) then
          Display("Both numbers must be positive")
          Stop
      endif

II.   [Begin with the given pair]
      A ← M
      B ← N

III.  [Replace the pair by (B, A mod B) until the second becomes 0]
      Repeat while (B ≠ 0)
          R ← A mod B
          A ← B
          B ← R
      endwhile

IV.   [The first of the pair is now the answer]
      Display("GCD = ", A)

V.    Stop

Why it works: Replacing (A, B) by (B, A mod B) leaves the set of common divisors unchanged, so the greatest common divisor is the same before and after every pass. The process must end, because B is a remainder and so is strictly smaller than the previous B, and it cannot fall below 0. When B reaches 0, the pair is (A, 0), whose greatest common divisor is A. Cost: Each pass replaces B by a strictly smaller remainder, so the number of passes is small even for large numbers — for 84 and 36 it needs two passes, where repeated subtraction needs four.

Table 3.7 – Repeated subtraction vs Euclid’s division method

Feature Repeated subtraction Division method
Operation per pass Subtract the smaller from the larger Replace the pair by (B, A mod B)
Passes for 84 and 36 4 2
Passes for 1000 and 3 Over 300 2
Stopping condition The two values become equal The second value becomes 0
Arithmetic needed Subtraction and comparison only Integer remainder
Behaviour on very unequal numbers Very slow; subtracts 3 from 1000 again and again Unaffected; one division does the work of many subtractions

The final row is the reason the division method is the one worth learning. Both are correct. Only one of them stays usable when the numbers are far apart.

Translating this method into Java is direct, because the three assignments of step III map one-to-one onto Java statements. The only real decision is where the input comes from; here it is read from the keyboard using Scanner.

Greatest common divisor of two positive integers Problem: Read two integers from the user. If either is not positive, report the fact. Otherwise display their greatest common divisor, computed by Euclid’s division method.

import java.util.Scanner;

class GCDFinder
{
    // Displays the greatest common divisor of two positive integers,
    // using Euclid's division method.
    public static void main(String args[])
    {
        Scanner in = new Scanner(System.in);
        System.out.print("Enter the first number : ");
        int m = in.nextInt();
        System.out.print("Enter the second number : ");
        int n = in.nextInt();

        if (m <= 0 || n <= 0)
        {
            System.out.println("Both numbers must be positive");
        }
        else
        {
            int a = m;
            int b = n;
            while (b != 0)
            {
                int r = a % b;
                a = b;
                b = r;
            }
            System.out.println("GCD of " + m + " and " + n + " = " + a);
        }
    }
}

Sample output:

Enter the first number : 84
Enter the second number : 36
GCD of 84 and 36 = 12

Variable description:

[Table:] Table 3.8 – variable description for the GCDFinder program [/Table] | Variable | Type | Purpose | |—|—|—| | in | Scanner | Reads the two numbers from the keyboard | | m | int | First number as entered, kept unchanged for the final message | | n | int | Second number as entered, kept unchanged for the final message | | a | int | First member of the current pair | | b | int | Second member of the current pair; the loop ends when it becomes 0 | | r | int | Remainder when a is divided by b |

Notes: m and n are copied into a and b rather than being changed directly, so that the original values are still available when the result is displayed. The loop condition is b != 0 rather than b > 0; both are correct for positive input, but != 0 states exactly the condition the method’s reasoning depends on. Nothing is printed inside the loop, because the intermediate pairs are working values and not results.

the GCDFinder program, on m = 84 and n = 36

Pass a at start b at start r = a % b a after b after
1 84 36 12 36 12
2 36 12 0 12 0
— 12 0 — loop ends —

Result: the program prints GCD of 84 and 36 = 12. The trace shows the pair shrinking while the answer stays fixed: 84 and 36 have greatest common divisor 12, and so do 36 and 12, and so do 12 and 0.

3.5.3 Testing for a Prime and Finding Prime Pairs

A prime number is a whole number greater than 1 whose only exact divisors are 1 and itself. Testing for primality is therefore a search: look for a divisor, and report success only if the search fails.

The question worth asking is how far the search must go. Testing every number from 2 up to N − 1 certainly works, but it does far more work than necessary. Suppose N has some divisor D other than 1 and itself, so that \(N = D \times E\). If both D and E were larger than \(\sqrt{N}\), their product would be larger than N, which it is not. So at least one of the two is no larger than \(\sqrt{N}\) — and a search that reaches \(\sqrt{N}\) cannot miss it.

That single observation reduces the work on a number near 10 000 from about ten thousand divisions to about a hundred. It is a good example of a saving that comes from thinking about the problem rather than from writing faster code.

Testing whether a number is prime Input: An integer N. Output: true if N is prime, false otherwise. Method:

[N is the number under test and D is the trial divisor.]

I.    [Numbers below 2 are not prime by definition]
      if (N < 2) then
          Return false
      endif

II.   [Look for a divisor no larger than the square root of N]
      D ← 2
      Repeat while (D × D <= N)
          if (N mod D = 0) then
              Return false
          endif
          D ← D + 1
      endwhile

III.  [No divisor was found, so N is prime]
      Return true

Why it works: If N has a divisor other than 1 and itself, then N = D × E for some pair of divisors, and at least one of them is no larger than the square root of N. Step II examines every candidate up to that limit, so no divisor can escape it. Cost: At most about \(\sqrt{N}\) trial divisions, and often far fewer — every even number is settled on the very first one.

The condition is written D × D <= N rather than D <= √N deliberately. Comparing whole numbers avoids taking a square root at all, and so avoids any question of rounding at the boundary. For N = 49 the loop tests D = 2, 3, 4, 5, 6 and 7; at D = 7 the condition \(7 \times 7 \le 49\) still holds, the remainder is 0, and 49 is correctly reported composite. Had the loop stopped one step earlier, it would have declared 49 prime.

searching for a divisor all the way up to the number itself What students write:

int flag = 1;
for (int d = 2; d <= n; d++)
{
    if (n % d == 0)
    {
        flag = 0;
    }
}

What happens: The loop eventually reaches d equal to n, and n % n is always 0. So flag is cleared for every number, and even 7 and 13 are reported composite. There is no compile error and no crash — just an answer that is wrong for every input. The fix: Stop before the number itself, with d < n, or better d * d <= n. The divisor 1 is excluded by starting at 2, and the divisor n must be excluded by the stopping condition.

With a primality test in hand, a second problem becomes easy. Given an even number N below 100, display every pair of primes that adds up to N. The direct method needs no array at all: for each candidate P from 2 upwards, ask whether P and N − P are both prime.

Taking P only as far as N / 2 avoids reporting the same pair twice with its members swapped.

Displaying all pairs of primes that add up to a given even number Input: An even integer N with \(0 < N < 100\). Output: Every pair of prime numbers whose sum is N, each pair listed once. Method:

[N is the given even number and P is the smaller member of a candidate pair.
 isPrime(X) is the test of the previous algorithm.]

I.    [Reject input that does not satisfy the stated condition]
      Read N
      if (N <= 0 or N >= 100 or N mod 2 ≠ 0) then
          Display("Invalid input")
          Stop
      endif

II.   [Try every possible smaller member of a pair]
      Repeat for P = 2, 3, ..., N / 2
          if (isPrime(P) and isPrime(N − P)) then
              Display(P, " + ", N − P, " = ", N)
          endif
      endfor

III.  Stop

Why it works: In any pair adding to N, the smaller member is at most N / 2, so step II considers every possible pair exactly once. A pair is displayed precisely when both members pass the primality test. Cost: About N / 2 candidates are examined, and each costs two primality tests. No pair is examined twice, and nothing is stored.

the prime-pairs algorithm, on N = 18

P Is P prime? N − P Is N − P prime? Displayed
2 Yes 16 No —
3 Yes 15 No —
4 No 14 not tested —
5 Yes 13 Yes 5 + 13 = 18
6 No 12 not tested —
7 Yes 11 Yes 7 + 11 = 18
8 No 10 not tested —
9 No 9 not tested —

Result: the two pairs 5 + 13 and 7 + 11 are displayed. Note the column headed not tested — the second test is only reached when the first succeeds, which is why an and between two conditions is worth more than it looks.

Q. Why does the loop stop at N / 2 rather than at N?

A. Because a pair adding to N has one member at or below N / 2 and the other at or above it. Running P all the way to N would find every pair a second time, with the two members exchanged, and report 5 + 13 and 13 + 5 as though they were different answers.

3.5.4 Extracting and Using the Digits of a Number

A great many problems ask for something about the digits of a number rather than about its value — the sum of the digits, the number reversed, whether it reads the same both ways, how many digits it has. None of these can be answered without first getting at the digits, and the technique for that is worth learning once and reusing everywhere.

Two operations do all the work. The remainder on division by 10 gives the last digit; integer division by 10 removes it. Applying them alternately peels the number apart from the right.

For 4073: the remainder on division by 10 is 3, and dividing by 10 leaves 407. Repeat, and the digits emerge as 3, 7, 0, 4 — in reverse order, which is a fact worth remembering rather than fighting.

Sum of the digits of a number Input: An integer N, N ≥ 0. Output: The sum of the digits of N. Method:

[N is the given number, T is a working copy that is destroyed as it is used,
 R is the digit just removed and S is the sum of the digits so far.]

I.    [Prepare]
      Read N
      T ← N
      S ← 0

II.   [Peel off one digit at a time from the right]
      Repeat while (T > 0)
          R ← T mod 10
          S ← S + R
          T ← T / 10        [integer division; the digit just used disappears]
      endwhile

III.  [Report]
      Display("Sum of digits = ", S)

IV.   Stop

Why it works: After each pass, T holds the number with its rightmost digit removed and S holds the sum of the digits removed so far. When T reaches 0 there are no digits left, so S is the sum of all of them. Cost: One pass per digit, so the work grows with the number of digits, not with the size of the number.

the digit-sum algorithm, on N = 4073

Pass T at start R = T mod 10 S after T after
1 4073 3 3 407
2 407 7 10 40
3 40 0 10 4
4 4 4 14 0
— 0 — 14 loop ends

Result: the sum 14 is displayed, which agrees with \(4 + 0 + 7 + 3\). Pass 3 is the one to look at — the digit 0 contributes nothing to the sum, but the pass still has to happen, because it is what removes the 0 and exposes the 4 behind it.

Two remarks about this method, both of which matter when you code it.

The division must be integer division. In Java, t / 10 on an int discards the fractional part automatically, which is what the method wants. Store t in a double and the loop never terminates, because dividing a positive real number by 10 makes it small but never zero.

The working copy matters. If the original value is needed later — to display it, or to compare against a result built from its digits — destroy a copy and keep the original, exactly as a and b did in the GCD program.

The same peeling gives more than a sum. Adding one line builds the number reversed:

REV ← REV × 10 + R

Each new digit is appended at the right of what has been built so far, and since the digits arrive right-to-left, the result is the original number written backwards. Starting REV at 0 and running this alongside the digit sum turns 4073 into 3704 with no extra loop. That one line is the whole basis of reversing a number, checking whether a number is a palindrome, and — with 10 replaced by another base — writing a number in a different number system.

Extend the digit-sum algorithm so that it also reports how many digits the number has and the number written in reverse, still using a single repetition. Then dry run it on N = 0 and on N = 1000 and say what each of the three outputs comes to. One of the three is arguably wrong for N = 0 — which, and why?

3.6 Algorithms on Single Dimensional Arrays

Everything in the previous section worked on one or two numbers at a time. Most real problems arrive as a collection — the marks of a whole class, the readings from a meter over a month, the prices in a stock register — and a collection has to be held somewhere before it can be examined as a whole.

You met arrays in Class XI, so a brief recall is enough. An array holds a fixed number of values of the same type under a single name, and the individual values are reached by position. Positions are numbered from 0, so an array of N elements has indices 0 to N − 1, and its last element is at index N − 1, never at N. Reaching any element costs the same as reaching any other, whatever its position and however large the array.

Diagram

Fig. 3.6-1 – a single dimensional array drawn as a horizontal row of five boxes containing the values 34, 12, 78, 5, 61; beneath each box its index 0, 1, 2, 3, 4; a bracket over the whole row labelled “A.length is 5”; an arrow to the last box labelled “last element is A[4], not A[5]”

That last point deserves the emphasis. The gap between “five elements” and “last index 4” is the single most productive source of errors in array code, and every algorithm in this section has been written with the boundary stated explicitly rather than left to be worked out later.

Six problems follow: finding the largest and smallest values, searching in two different ways, sorting by two different techniques, and combining two sorted arrays into one. They are the standard repertoire, and between them they demonstrate almost every idea you need for handling collections.

3.6.1 Finding the Maximum and the Minimum

The method is the one you would use with a printed list and a pencil. Look at the first value, and provisionally call it both the largest and the smallest you have seen. Then work down the list, and whenever a value beats the current champion, replace it.

The provisional answer is the interesting part. It must be an actual element of the array, and the natural choice is the first one, A[0]. Starting the search from index 1 then costs nothing, since element 0 has already been accounted for.

Finding the largest and smallest values in an array Input: An array A of N elements, with N greater than 0. Output: The largest and the smallest of the N values. Method:

[A is the array and N is the number of elements in it.
 MAX holds the largest value found so far, MIN the smallest, and I is the index.]

I.    [Take the first element as the provisional answer for both]
      MAX ← A[0]
      MIN ← A[0]

II.   [Compare every remaining element against the current answers]
      Repeat for I = 1, 2, ..., N − 1
          if (A[I] > MAX) then
              MAX ← A[I]
          endif
          if (A[I] < MIN) then
              MIN ← A[I]
          endif
      endfor

III.  [Report]
      Display("Maximum = ", MAX)
      Display("Minimum = ", MIN)

IV.   Stop

Why it works: After step I, MAX and MIN correctly describe the single element examined so far. Each pass of step II examines one further element and updates the answers only when that element beats them, so if MAX and MIN were correct for the elements seen before the pass, they are correct for the elements seen after it. After the last pass every element has been examined. Cost: N − 1 passes, each making two comparisons. Every element is examined exactly once, and the array is not disturbed.

the maximum-and-minimum algorithm, on A = {34, 12, 78, 5, 61}

I A[I] A[I] > MAX ? A[I] < MIN ? MAX after MIN after
— (after step I) — — — 34 34
1 12 No Yes 34 12
2 78 Yes No 78 12
3 5 No Yes 78 5
4 61 No No 78 5

Result: maximum 78 and minimum 5, which is right. Notice pass 4: 61 is a large value but not large enough to displace 78, and the pass correctly changes nothing.

starting the search from zero instead of from an element What students write:

int max = 0;
int min = 0;
for (int i = 0; i < n; i++)
{
    if (a[i] > max) max = a[i];
    if (a[i] < min) min = a[i];
}

What happens: With all-positive data it appears to work, which is why the mistake survives. Give it an array of temperatures below freezing — say {−4, −11, −7} — and it reports a maximum of 0, a value that is not in the array at all. The minimum has the mirror fault: on all-positive data it reports 0. The fix: Start both from an actual element, int max = a[0]; and int min = a[0];, and run the loop from i = 1. A provisional answer must always be a real candidate.

3.6.4 Bubble Sort

Sorting arranges the elements of an array into order — here, ascending order. Bubble sort does it by comparing neighbours: it walks along the array, and wherever two adjacent elements are in the wrong order, it exchanges them.

One walk along the array is called a pass. Watch what a single pass achieves. The largest value, wherever it starts, is bigger than its right-hand neighbour at every comparison, so it is exchanged forward again and again and finishes at the end of the array. After one pass, the last position holds the largest element, and it never has to move again.

That is the whole method. Each pass places one more element correctly at the end, so the region still needing attention shrinks by one every time, and N − 1 passes are enough — once all but one element are in place, the one left over has nowhere else to be.

Diagram

Fig. 3.6-3 – one pass of bubble sort over the array 29, 13, 42, 7, 21 drawn as four stacked rows of five boxes; in each row the pair of adjacent boxes being compared is outlined and marked with the comparison, and an arrow marked “exchange” or “no change” leads to the next row; the final row shows 13, 29, 7, 21, 42 with the last box shaded and labelled “42 is now in its final position”

Bubble sort in ascending order Input: An array A of N elements. Output: The same elements arranged in ascending order. Method:

[A is the array and N is the number of elements. I counts the passes,
 J is the position of the left-hand element of the pair being compared,
 and T is a temporary store used while exchanging two elements.]

I.    [Make N − 1 passes over the array]
      Repeat for I = 1, 2, ..., N − 1

II.       [Compare each adjacent pair in the region not yet settled]
          Repeat for J = 0, 1, ..., N − 1 − I
              if (A[J] > A[J + 1]) then
                  T ← A[J]
                  A[J] ← A[J + 1]
                  A[J + 1] ← T
              endif
          endfor
      endfor

III.  [Report]
      Display the elements of A in order
      Stop

Why it works: After pass I, the largest I elements occupy the last I positions in their correct order, because each pass carries the largest element of the unsettled region to the end of that region. After N − 1 passes only one element is unsettled, and it must already be in the only place left. Cost: The inner repetition runs N − 1 times in the first pass, N − 2 in the second, and so on. Altogether about half of N × N comparisons are made, however the data was arranged to start with.

The upper limit of the inner repetition, N − 1 − I, is what stops the method from re-examining the tail that is already settled. Writing N − 2 there instead would still sort correctly, but it would compare pairs whose order was decided passes ago.

bubble sort, on A = {29, 13, 42, 7, 21}

Pass Comparisons made (left element in bold order of J) Array after the pass
1 29 with 13 exchange; 29 with 42 keep; 42 with 7 exchange; 42 with 21 exchange 13, 29, 7, 21, 42
2 13 with 29 keep; 29 with 7 exchange; 29 with 21 exchange 13, 7, 21, 29, 42
3 13 with 7 exchange; 13 with 21 keep 7, 13, 21, 29, 42
4 7 with 13 keep 7, 13, 21, 29, 42

Result: the array is sorted as 7, 13, 21, 29, 42. Two things are visible in the trace. The tail fills up from the right — 42 is fixed after pass 1, 29 after pass 2, 21 after pass 3. And pass 4 changes nothing, because the array was already in order by then; bubble sort as written has no way of noticing that and makes the pass anyway.

exchanging two elements without a temporary store What students write:

a[j] = a[j + 1];
a[j + 1] = a[j];

What happens: The first line overwrites a[j], and the old value is gone. The second line then copies back the value that is now in a[j] — which is the value from a[j + 1]. Both positions end up holding the same value, and one element of the array has been destroyed. The array does not crash; it quietly grows duplicates. The fix: Park one value before overwriting it.

int t = a[j];
a[j] = a[j + 1];
a[j + 1] = t;

The temporary variable is not clutter — it is the only place the first value exists between the two assignments.

3.6.5 Selection Sort

Selection sort reaches the same destination by a different route. Instead of exchanging neighbours repeatedly, it finds the right element for each position directly.

Consider position 0. The element that belongs there is the smallest in the whole array, so find it — by the search of section 3.6.1, restricted to the region from 0 onwards — and exchange it into position 0. Position 0 is now correct and never needs touching again. Now consider position 1, the smallest of what remains, and so on. After N − 1 positions have been filled this way, the last position holds the only element left.

Notice the difference in effort. Bubble sort may exchange on every comparison; selection sort compares just as much but exchanges at most once per position.

Selection sort in ascending order Input: An array A of N elements. Output: The same elements arranged in ascending order. Method:

[A is the array and N is the number of elements. I is the position being filled,
 J scans the unsorted region, POS is the index of the smallest element found in
 that region, and T is a temporary store used while exchanging.]

I.    [Fill each position in turn, from the first to the second last]
      Repeat for I = 0, 1, ..., N − 2

II.       [Find the smallest element in the region from I onwards]
          POS ← I
          Repeat for J = I + 1, I + 2, ..., N − 1
              if (A[J] < A[POS]) then
                  POS ← J
              endif
          endfor

III.      [Put it in position I, if it is not already there]
          if (POS ≠ I) then
              T ← A[I]
              A[I] ← A[POS]
              A[POS] ← T
          endif
      endfor

IV.   [Report]
      Display the elements of A in order
      Stop

Why it works: When the repetition of step I reaches position I, the elements in positions 0 to I − 1 are already the I smallest values of the array in order. Step II finds the smallest of what remains and step III places it at position I, so positions 0 to I are now correct. After position N − 2 has been filled, only one element is left over and it is necessarily the largest. Cost: The same number of comparisons as bubble sort — about half of N × N — but at most N − 1 exchanges in total, compared with one exchange per out-of-order pair.

selection sort, on A = {46, 8, 31, 19, 4}

I (position being filled) Region scanned Smallest found, at index Exchange Array after
0 46, 8, 31, 19, 4 4, at index 4 46 with 4 4, 8, 31, 19, 46
1 8, 31, 19, 46 8, at index 1 none needed 4, 8, 31, 19, 46
2 31, 19, 46 19, at index 3 31 with 19 4, 8, 19, 31, 46
3 31, 46 31, at index 3 none needed 4, 8, 19, 31, 46

Result: the array is sorted as 4, 8, 19, 31, 46, using two exchanges in all. The rows where no exchange was needed are worth noticing — the test POS ≠ I in step III is what prevents an element being pointlessly exchanged with itself.

Table 3.11 – Bubble sort vs Selection sort

Feature Bubble sort Selection sort
Basic operation Compare and exchange adjacent elements Find the smallest of the remaining region and place it
Where the sorted part grows From the right-hand end From the left-hand end
Comparisons About half of N × N About half of N × N
Exchanges One for every out-of-order pair; many At most one per position; at most N − 1
Data movement Values shuffle a step at a time Values move directly to their place
Behaviour on data already sorted Still makes every pass; no exchanges Still scans every region; no exchanges

Neither technique is a clear winner on comparisons, because both examine every pair of positions. Selection sort wins on movement, which matters when the elements being moved are large. Both are studied here as designs rather than as production tools; bubble, selection and insertion are the three standard techniques, and all three are treated in detail when arrays are studied in their own right.

Q. Bubble sort exchanges nothing when the array is already sorted. Could it detect that and stop?

A. Yes. Record whether any exchange happened during a pass; if a whole pass passes without one, the array is in order and the remaining passes can be abandoned. It costs one extra variable and saves every pass after the array happens to become sorted.

3.6.6 Merging Two Sorted Arrays

Two arrays are each already in ascending order, and a single sorted array containing all their elements is wanted. Sorting the combined collection from scratch would work and would throw away everything you already know.

The efficient method uses the ordering. The smallest element overall must be the first element of one array or the first of the other — there is nowhere else for it to be. Compare those two, copy the smaller into the result, and move past it in the array it came from. Repeat: at every stage the smallest element not yet copied is at the front of one of the two remaining stretches.

Eventually one array is used up. The other is already sorted, and everything left in it is larger than everything copied so far, so it can simply be copied across in order.

Merging two sorted arrays into one Input: An array A of M elements and an array B of N elements, each in ascending order. Output: An array C of M + N elements containing all their elements in ascending order. Method:

[A and B are the sorted input arrays with M and N elements. C is the result array
 with M + N positions. I indexes A, J indexes B and K indexes C.]

I.    [Nothing has been copied yet]
      I ← 0
      J ← 0
      K ← 0

II.   [While both arrays still have elements, copy the smaller front element]
      Repeat while (I < M and J < N)
          if (A[I] <= B[J]) then
              C[K] ← A[I]
              I ← I + 1
          else
              C[K] ← B[J]
              J ← J + 1
          endif
          K ← K + 1
      endwhile

III.  [One array is exhausted; copy whatever remains of the other]
      Repeat while (I < M)
          C[K] ← A[I]
          I ← I + 1
          K ← K + 1
      endwhile

      Repeat while (J < N)
          C[K] ← B[J]
          J ← J + 1
          K ← K + 1
      endwhile

IV.   [Report]
      Display the elements of C in order
      Stop

Why it works: At every point, everything already copied into C is in ascending order and is no larger than any element still uncopied. Step II preserves this, because the element it copies is the smaller of the two smallest uncopied elements. When one array runs out, the remaining stretch of the other is sorted and entirely larger than what has been copied, so appending it keeps the order. Cost: Every element is looked at once and copied once, so M + N copies in all. Neither input array is disturbed, and a third array of exactly M + N positions is needed.

Only one of the two repetitions in step III can actually run, since step II ends the moment either array is exhausted. Writing both, rather than testing which case applies, keeps the method short and makes it impossible to get the test the wrong way round.

merging A = {3, 9, 14, 20} and B = {5, 9, 25}

Step A[I] B[J] Which is copied C so far
1 3 5 3, from A 3
2 9 5 5, from B 3, 5
3 9 9 9, from A 3, 5, 9
4 14 9 9, from B 3, 5, 9, 9
5 14 25 14, from A 3, 5, 9, 9, 14
6 20 25 20, from A 3, 5, 9, 9, 14, 20
7 A exhausted 25 25, by step III 3, 5, 9, 9, 14, 20, 25

Result: C holds 3, 5, 9, 9, 14, 20, 25 — seven elements, as it must, since 4 + 3 = 7. Step 3 is the one to study: the two front elements are equal, and the condition A[I] <= B[J] sends the one from A first. Both copies happen and neither value is lost, which is exactly what a strict < would have got wrong if it had been paired with a careless else.

Dry run the merge algorithm on A = {2, 4, 6} and B = {1, 3, 5, 7, 9}, writing the full table on paper. Which of the two repetitions in step III runs, and how many elements does it copy?

3.7 Algorithms on Double Dimensional Arrays

Some data is naturally a table rather than a list: the marks of every student in every subject, the daily rainfall of each month, a seating plan, a distance chart between towns. Squeezing a table into a single row of values loses the very thing that made it a table — the fact that each value has a row and a column.

A double dimensional array stores such data directly. It is an array whose elements are themselves arrays, so a value is identified by two indices: A[I][J] is the element in row I and column J. Both index ranges begin at 0, so an array of M rows and N columns has rows 0 to M − 1 and columns 0 to N − 1.

Diagram

Fig. 3.7-1 – a grid of three rows and four columns drawn as boxes; column indices 0, 1, 2, 3 written above the grid and row indices 0, 1, 2 written to the left; the box in row 1, column 2 shaded and labelled “A[1][2]”; a note below the grid reading “3 rows × 4 columns = 12 elements; last element is A[2][3]”

Almost every method in this section is a nested repetition: an outer one that moves from row to row and an inner one that moves along the columns of the current row. Getting comfortable with which loop controls which index is most of the work.

3.7.1 Traversing a Matrix

To visit every element of a table, two loops are needed. Which of them is on the outside decides the order in which the elements are visited, and that order matters more often than students expect.

In row-wise traversal the outer repetition runs over rows and the inner one over columns, so the elements are visited left to right along row 0, then along row 1, and so on — the order in which you would read a printed table. In column-wise traversal the loops are exchanged, and the elements are visited down column 0, then down column 1.

Table 3.12 – Row-wise vs Column-wise traversal

Feature Row-wise traversal Column-wise traversal
Outer repetition runs over Rows, I from 0 to M − 1 Columns, J from 0 to N − 1
Inner repetition runs over Columns, J from 0 to N − 1 Rows, I from 0 to M − 1
Order of visiting A[0][0], A[0][1], … then row 1 A[0][0], A[1][0], … then column 1
Natural use Totals or sorting within each row Totals or comparisons within each column
Element accessed A[I][J] in both cases A[I][J] in both cases

The last row is the point of the table. The two traversals differ only in the order of the loops, never in how an element is written. A student who has just exchanged the loops and then also exchanged the indices has changed the shape of the array being read, not the order of reading it, and the result is usually an error about the array bounds.

When the order does not matter — when every element is to be examined and nothing depends on the sequence — either traversal will do. Finding the largest element of a table is such a problem, and its method is the one from section 3.6.1 with one extra loop wrapped round it, plus two variables to remember where the largest was found.

Largest element of a matrix, with its row and column Input: A double dimensional array A of M rows and N columns, with M and N greater than 0. Output: The largest element, and the row and column at which it occurs. Method:

[A is the array with M rows and N columns. MAX holds the largest element found
 so far, MR and MC hold its row and column, and I and J are the two indices.]

I.    [Take the first element as the provisional answer]
      MAX ← A[0][0]
      MR ← 0
      MC ← 0

II.   [Visit every element row by row]
      Repeat for I = 0, 1, ..., M − 1
          Repeat for J = 0, 1, ..., N − 1
              if (A[I][J] > MAX) then
                  MAX ← A[I][J]
                  MR ← I
                  MC ← J
              endif
          endfor
      endfor

III.  [Report]
      Display("Largest = ", MAX)
      Display("Row = ", MR, "  Column = ", MC)

IV.   Stop

Why it works: After step I the answer is correct for the single element examined. Each pass of the inner repetition examines one further element and replaces the answer only when that element is larger, so the answer stays correct for everything seen so far. The two repetitions between them reach every element exactly once. Cost: M × N comparisons, one per element. The array is read but not changed.

The three assignments inside the if must stay together. Updating MAX without updating MR and MC leaves the position describing an element that is no longer the largest, and the error is invisible until the position is printed.

the largest-element algorithm, on the 3 × 3 matrix 8 3 17 / 12 6 25 / 9 14 2

I J A[I][J] Larger than MAX? MAX MR MC
— — — — 8 0 0
0 0 8 No (equal) 8 0 0
0 1 3 No 8 0 0
0 2 17 Yes 17 0 2
1 0 12 No 17 0 2
1 1 6 No 17 0 2
1 2 25 Yes 25 1 2
2 0 9 No 25 1 2
2 1 14 No 25 1 2
2 2 2 No 25 1 2

Result: the largest element is 25, at row 1 and column 2. The first row of the trace is A[0][0] being compared with itself, which changes nothing and costs nothing; starting the outer loop at 0 rather than complicating the method to skip one element is the simpler choice.

3.7.2 Sorting Each Row of a Matrix

“Sort the matrix” can mean two quite different things, and the specification has to say which. Sorting all M × N values together produces a single ordered sequence laid back into the table. Sorting each row separately leaves every value in the row it started in and merely rearranges it within that row. This subsection does the second.

The method needs no new sorting technique. Take the bubble sort of section 3.6.4 and apply it, unchanged, to each row in turn. A row of a double dimensional array behaves exactly like a single dimensional array of N elements, so the inner machinery is identical — only the array being sorted changes on each outer pass.

Sorting each row of a matrix in ascending order Input: A double dimensional array A of M rows and N columns. Output: The same array, with the elements of each row rearranged into ascending order. Method:

[A is the array with M rows and N columns. I is the row being sorted,
 P counts the passes within that row, J is the position of the left-hand element
 of the pair being compared, and T is a temporary store used while exchanging.]

I.    [Deal with one row at a time]
      Repeat for I = 0, 1, ..., M − 1

II.       [Bubble sort the elements of row I]
          Repeat for P = 1, 2, ..., N − 1
              Repeat for J = 0, 1, ..., N − 1 − P
                  if (A[I][J] > A[I][J + 1]) then
                      T ← A[I][J]
                      A[I][J] ← A[I][J + 1]
                      A[I][J + 1] ← T
                  endif
              endfor
          endfor
      endfor

III.  [Report]
      Display the elements of A, row by row
      Stop

Why it works: The two inner repetitions are exactly bubble sort applied to row I, which was shown in section 3.6.4 to leave its array in ascending order. The outer repetition applies that to every row, and sorting one row cannot disturb another, since the row index I is fixed throughout the inner work. Cost: About half of N × N comparisons for each of the M rows.

Three levels of nesting is as deep as anything in this chapter goes, and it is worth reading the structure aloud once: for each row, make N − 1 passes, and in each pass compare the adjacent pairs. If you can say that, you can write it.

Sorting each row of a matrix Problem: A 3 × 3 matrix of integers is given in the program. Display it, sort each row into ascending order using the bubble sort technique, and display the result.

class RowSorter
{
    // Sorts each row of a matrix into ascending order using bubble sort,
    // and displays the matrix before and after sorting.
    public static void main(String args[])
    {
        int m[][] = {{24, 6, 19}, {31, 8, 45}, {12, 27, 3}};
        int rows = m.length;
        int cols = m[0].length;

        System.out.println("Original matrix");
        display(m, rows, cols);

        for (int i = 0; i < rows; i++)
        {
            for (int p = 1; p < cols; p++)
            {
                for (int j = 0; j < cols - p; j++)
                {
                    if (m[i][j] > m[i][j + 1])
                    {
                        int t = m[i][j];
                        m[i][j] = m[i][j + 1];
                        m[i][j + 1] = t;
                    }
                }
            }
        }

        System.out.println("Matrix after sorting each row");
        display(m, rows, cols);
    }

    static void display(int a[][], int rows, int cols)
    {
        for (int i = 0; i < rows; i++)
        {
            for (int j = 0; j < cols; j++)
            {
                if (j > 0)
                {
                    System.out.print("\t");
                }
                System.out.print(a[i][j]);
            }
            System.out.println();
        }
    }
}

Sample output:

Original matrix
24  6   19
31  8   45
12  27  3
Matrix after sorting each row
6   19  24
8   31  45
3   12  27

Variable description:

[Table:] Table 3.13 – variable description for the RowSorter program [/Table] | Variable | Type | Purpose | |—|—|—| | m | int[][] | The matrix, sorted in place row by row | | rows | int | Number of rows, taken from m.length | | cols | int | Number of columns, taken from m[0].length | | i | int | Row currently being sorted | | p | int | Pass counter within the current row | | j | int | Position of the left-hand element of the pair being compared | | t | int | Temporary store used while exchanging two elements | | a, rows, cols | parameters of display | The matrix and its size, passed in for printing |

Notes: The number of rows and columns is taken from the array itself rather than written as 3, so the same program works unchanged on a matrix of a different size. Printing is separated into a method because it is needed twice, before and after sorting — writing it once and calling it twice is shorter and removes the risk of the two printouts disagreeing in format. The tab is printed before each element except the first, so no line ends in trailing whitespace.

Notice that the sorting happens in the array itself. After the loops have run, the original arrangement no longer exists anywhere, which is why the matrix is printed before the sorting begins. Any method that changes an array in place destroys what it started with, and if the original is needed later it must be copied first.

Q. Would sorting each column instead need a different sorting technique?

A. No, only a different traversal. Fix a column index J, let the inner loops compare A[I][J] with A[I + 1][J], and run the passes over the rows. The technique is unchanged; what changes is which index stays still.

3.7.3 Working with the Diagonals

When a table has as many rows as columns it is called a square matrix, and only then do its diagonals exist. Two of them do.

The left diagonal, also called the main diagonal, runs from the top left corner to the bottom right. Its elements are those whose row and column indices are equal: A[0][0], A[1][1], A[2][2] and so on, which is to say A[I][I].

The right diagonal runs from the top right corner to the bottom left. Here the two indices are not equal but add up to a constant: in an N × N matrix, the element in row I lies in column N − 1 − I, so its elements are A[I][N − 1 − I].

Diagram

Fig. 3.7-2 – a 3 × 3 grid holding the values 5, 2, 9 in the first row, 4, 7, 1 in the second and 6, 3, 8 in the third; row indices 0, 1, 2 on the left and column indices 0, 1, 2 above; the cells 5, 7, 8 shaded in one tint and labelled “left diagonal, A[I][I]”; the cells 9, 7, 6 shaded in a second tint and labelled “right diagonal, A[I][N−1−I]”; the centre cell 7 marked “belongs to both”

Once the index pattern is seen, the algorithm collapses. A diagonal has exactly N elements, one from each row, so a single repetition reaches all of them — no nesting is needed, and using nested loops here would visit N × N cells to make use of 2N of them.

Sum of the two diagonals of a square matrix Input: A double dimensional array A of N rows and N columns, N greater than 0. Output: The sum of the left diagonal and the sum of the right diagonal. Method:

[A is the square array of size N × N. LSUM is the sum along the left diagonal,
 RSUM the sum along the right diagonal, and I is the index of the current row.]

I.    [Nothing added yet]
      LSUM ← 0
      RSUM ← 0

II.   [One element of each diagonal lies in each row]
      Repeat for I = 0, 1, ..., N − 1
          LSUM ← LSUM + A[I][I]
          RSUM ← RSUM + A[I][N − 1 − I]
      endfor

III.  [Report]
      Display("Sum of left diagonal = ", LSUM)
      Display("Sum of right diagonal = ", RSUM)

IV.   Stop

Why it works: Every row of a square matrix contains exactly one element of each diagonal — the left one at column I and the right one at column N − 1 − I. Running I over all the rows therefore adds each diagonal element exactly once and no other element at all. Cost: N passes, and 2N of the N × N elements are ever touched.

the diagonal-sum algorithm, on the 3 × 3 matrix 5 2 9 / 4 7 1 / 6 3 8

I A[I][I] LSUM after Column N − 1 − I A[I][N−1−I] RSUM after
— — 0 — — 0
0 5 5 2 9 9
1 7 12 1 7 16
2 8 20 0 6 22

Result: the left diagonal sums to 20 and the right to 22. The element 7 at the centre is added to both sums, because it genuinely lies on both diagonals — which happens in every square matrix of odd size, and never in one of even size. If a specification asks for the sum of all diagonal elements, that shared element must be counted once, not twice, and the method needs an explicit correction.

One guard belongs in any diagonal method: check that the matrix really is square. Asking for A[I][I] in a table of 3 rows and 5 columns runs off nothing, but asking for it in a table of 5 rows and 3 columns reaches column 3 of a row that has only columns 0 to 2, and the program stops with an error about the array index. A diagonal of a non-square table is not a hard problem — it is a meaningless one, and the method should say so and stop.

A square matrix is called symmetric when the element at row I, column J equals the element at row J, column I for every pair of positions. Write an algorithm that reads an N × N matrix and reports whether it is symmetric. Then answer this: your loops need not visit all N × N positions — which half can be skipped, and why does skipping it cost nothing?

3.8 Algorithms on Strings

A string is a sequence of characters treated as one value — a name, a sentence, a line read from the keyboard. Like an array, it is indexed from 0, so the characters of a sentence of L characters occupy positions 0 to L − 1, and the space between two words is a character occupying a position of its own.

Diagram

Fig. 3.8-1 – the sentence “an ox” drawn as five boxed characters a, n, space, o, x with the space box shaded and labelled “the separator is a character too”; index numbers 0, 1, 2, 3, 4 written beneath the boxes; a bracket over positions 0 to 1 labelled “word 1” and over positions 3 to 4 labelled “word 2”

The operations used in this section are the ones you met in Class XI. Table 3.14 recalls them, with the exact result each produces, because most string errors are really errors about what a method returns.

Table 3.14 – string operations used in this section, with what each returns

Operation Returns Note
length() The number of characters, as an int The last valid position is length() - 1
charAt(i) The character at position i, as a char i must lie from 0 to length() - 1
substring(i) The part from position i to the end A new string; the original is unchanged
substring(i, j) The part from position i up to but not including j The second index is one past the last character wanted
indexOf(x) The first position at which x occurs, or −1 −1 is used because 0 is a valid position
equals(x) true if the two strings hold the same characters Compares contents, not identity

One property of strings shapes every algorithm here. A string in Java is immutable: no operation changes an existing string, and every operation that appears to modify one in fact produces a new string. Writing WORD ← WORD + CH does not append a character to WORD; it builds a fresh string from the old contents and the new character, and points WORD at that. The method still works, and for sentences of ordinary length the cost is of no consequence — it is the reason a separate class exists for text that is manipulated heavily, which is studied alongside strings in their own right.

3.8.1 Extracting Words from a Sentence

Almost every string problem set at this level begins with the same requirement: get at the individual words. Once you can do that reliably, counting them, measuring them, comparing them and rearranging them are small additions.

The reliable method is to scan the sentence one character at a time, collecting characters into a store as you go. A character that is not a space extends the word being collected. A space means the word just collected is complete — so it can be used, and the store emptied ready for the next one.

That leaves one difficulty, and it is the difficulty in every version of this problem. The last word of a sentence is not followed by a space, so the “word is complete” case never fires for it, and the word is silently lost. There are two repairs. Either handle the leftover word after the repetition ends, or append a single space to the sentence before starting, so that every word without exception ends in the ordinary way. The second is shorter and has one path through the code instead of two, so it is the one used here.

Listing the words of a sentence with their lengths Input: A sentence S, whose words are separated by one or more spaces. Output: Each word with its length, and the number of words. Method:

[S is the sentence and T is S with one space appended, so that the last word is
 completed like any other. WORD accumulates the characters of the word currently
 being collected, CH is the character being examined, I is the position in T,
 and COUNT is the number of words found so far.]

I.    [Prepare]
      Read S
      T ← S + " "
      WORD ← ""
      COUNT ← 0

II.   [Examine the characters one by one]
      Repeat for I = 0, 1, ..., length(T) − 1
          CH ← character at position I of T
          if (CH ≠ ' ') then
              WORD ← WORD + CH
          else
              if (length(WORD) > 0) then
                  COUNT ← COUNT + 1
                  Display(WORD, "  ", length(WORD))
                  WORD ← ""
              endif
          endif
      endfor

III.  [Report]
      Display("Number of words = ", COUNT)

IV.   Stop

Why it works: A word is a run of consecutive non-space characters. Each non-space character extends the run being collected; each space ends it. Appending one space to the sentence guarantees that the final run is ended in the same way as every other, so no word is left uncollected. Cost: One pass over the characters of the sentence. The work grows with the length of the sentence, not with the number of words.

The inner test length(WORD) > 0 does more than it appears to. Two consecutive spaces would otherwise end a word of no characters, count it, and display a blank line. With the test in place, extra spaces between words — and a sentence that begins with a space — are handled correctly without any further code.

Listing the words of a sentence with their lengths Problem: A sentence is given in the program. Display each of its words on a line of its own, followed by the number of characters in that word, and finally the total number of words.

class WordLister
{
    // Displays each word of a sentence with its length, followed by the
    // number of words. The sentence is fixed in the program.
    public static void main(String args[])
    {
        String s = "A quiet library on a rainy afternoon";
        String t = s + " ";
        String word = "";
        int count = 0;

        for (int i = 0; i < t.length(); i++)
        {
            char ch = t.charAt(i);
            if (ch != ' ')
            {
                word = word + ch;
            }
            else
            {
                if (word.length() > 0)
                {
                    count = count + 1;
                    System.out.println(word + "\t" + word.length());
                    word = "";
                }
            }
        }

        System.out.println("Number of words = " + count);
    }
}

Sample output:

A   1
quiet   5
library 7
on  2
a   1
rainy   5
afternoon   9
Number of words = 7

Variable description:

[Table:] Table 3.15 – variable description for the WordLister program [/Table] | Variable | Type | Purpose | |—|—|—| | s | String | The sentence as given | | t | String | The sentence with one space appended, so the last word ends normally | | word | String | Characters of the word currently being collected | | count | int | Number of words found so far | | i | int | Position of the character being examined | | ch | char | The character at position i |

Notes: s is left untouched and the scanning is done over t, so the original sentence is still available if it is needed again. word is emptied immediately after a word has been used, which is what makes the next word start clean. The loop condition uses t.length(), not s.length(), since it is t that is being scanned — using the wrong one here would skip the last word, the very fault the appended space was added to prevent.

the word-listing algorithm, on the sentence “an ox”

I CH Is CH a space? WORD after Displayed COUNT
— — — “” — 0
0 a No “a” — 0
1 n No “an” — 0
2 space Yes, and WORD is not empty “” an 2 1
3 o No “o” — 1
4 x No “ox” — 1
5 space (the appended one) Yes, and WORD is not empty “” ox 2 2

Result: both words are listed and the count is 2. Row 5 is the whole reason for appending the space: without it the loop would end after row 4 with “ox” still sitting unused in WORD, and the sentence would appear to contain one word.

Problems of this kind frequently ask you to compare a collected word against a given one — to delete it, count it, or replace it. That comparison has a trap of its own.

comparing two strings with == instead of equals() What students write:

if (word == "the")
{
    count = count + 1;
}

What happens: == asks whether the two names refer to the same string object, not whether they hold the same characters. A word built up character by character is a new object, so the test is false even when the word really is “the”. The program compiles, runs, and reports a count of 0. The fix: Compare the contents.

if (word.equals("the"))
{
    count = count + 1;
}

Use equals for strings and == only for primitive values such as int and char. Comparing ch == ' ' in the program above is correct precisely because ch is a char.

3.8.2 Rearranging and Transforming a Sentence

Extracting the words was the hard part. Once each word arrives, complete, at a known moment, what you do with it is a matter of choice — display it, measure it, test it, or store it towards a result.

Reversing the order of the words in a sentence shows this clearly. The scanning is unchanged, character for character. Only the action taken when a word is completed is different: instead of displaying the word, place it in front of everything built so far.

Why in front? Because the words arrive in the order they appear in the sentence, and the result needs them in the opposite order. Putting each new arrival at the head of the result reverses the sequence without any array, any second pass, or any counting.

Reversing the order of the words in a sentence Input: A sentence S. Output: The same words, in the reverse order, separated by single spaces. Method:

[S is the sentence and T is S with one space appended. WORD accumulates the word
 currently being collected, CH is the character being examined, and REV holds the
 result built so far.]

I.    [Prepare]
      Read S
      T ← S + " "
      WORD ← ""
      REV ← ""

II.   [Collect each word and place it at the front of the result]
      Repeat for I = 0, 1, ..., length(T) − 1
          CH ← character at position I of T
          if (CH ≠ ' ') then
              WORD ← WORD + CH
          else
              if (length(WORD) > 0) then
                  if (REV = "") then
                      REV ← WORD
                  else
                      REV ← WORD + " " + REV
                  endif
                  WORD ← ""
              endif
          endif
      endfor

III.  [Report]
      Display(REV)

IV.   Stop

Why it works: Each completed word is placed before everything collected earlier, so a word that appeared later in the sentence ends up earlier in the result. After the last word has been placed, the result contains all the words in exactly the reverse of their original order. Cost: One pass over the characters, as before. No array is needed, and the words are never stored twice.

The test for an empty result is not fussiness. Without it, the very first word would be joined to nothing by a space, and the finished sentence would carry a stray space at its end. Small blemishes of this kind are the difference between output that matches a specification and output that nearly matches it.

the word-reversal algorithm, on the sentence “the cat sat”

Word completed REV before REV after
the “” “the”
cat “the” “cat the”
sat “cat the” “sat cat the”

Result: the sentence displayed is sat cat the. The trace is short because the character-level scanning has already been established; once you trust the collecting mechanism, a trace at the level of whole words is enough to check the new part of the method.

The same skeleton answers a whole family of questions. Display only the words longer than four characters, and the change is a test before the display. Display the words in the order they came but each spelt backwards, and the change is in how WORD is built — add each character at the front rather than the end. Count how many words begin with a vowel, and the change is a test on the first character of WORD. In every case the scanning stays as it is, and only the moment of completion is rewritten. Recognising that one skeleton, rather than memorising a separate method for each question, is what this section is for.

Practical link: Strings and sentence processing. File this under the string-handling assignments in your work file. Write and run a program that reads a sentence terminated by a full stop and displays it with every vowel replaced by an asterisk, followed by the number of vowels replaced. Test it on A quiet evening in the old town. and then on the unseen input Rhythm., which contains no vowel at all — your program must report zero replacements and print the word unchanged apart from the full stop.

3.9 From Algorithm to Java Program

Everything so far has produced methods on paper. This section closes the gap: it takes a method that has been designed, argued and traced, and turns it into a program that compiles, runs and can be trusted.

The translation is largely mechanical, and that is exactly the point of having done the design work first. But three decisions are made here and nowhere else — the type of every variable, where the input comes from, and what the output looks like — and each of them can turn a correct method into an incorrect program.

3.9.1 Translating Each Step into Code

Every form used in the pseudocode of this book has a direct Java counterpart. Table 3.16 gives them together, so that translation becomes a matter of substitution rather than invention.

Table 3.16 – pseudocode forms and their Java equivalents

Pseudocode form Java form
X ← expression x = expression;
Read X x = in.nextInt(); with a Scanner named in
Display(...) System.out.println(...);
if (c) then ... endif if (c) { ... }
if (c) then ... else ... endif if (c) { ... } else { ... }
Repeat while (c) ... endwhile while (c) { ... }
Repeat for I = a, ..., b for (int i = a; i <= b; i++) { ... }
Exit the repetition break;
Stop The end of main, or return; to leave it early
A[I] and A[I][J] a[i] and a[i][j]

Two things in the table are not substitutions but decisions.

The first is the type of every variable. Pseudocode says S ← 0 and leaves it there; Java demands to know whether S counts things, in which case it is an int, or measures something divisible, in which case it is a double. The variable description table you wrote at design time already records this, which is one of the reasons for writing it.

The second is where the input comes from. A method that says Read N says nothing about a keyboard. In a program the value must be obtained from somewhere, and the choice — read with Scanner, or fixed in the program — should be stated plainly rather than left for a reader to discover.

Here is a complete method carried through both stages. A school library charges no fine on a book returned on time. A book returned late is charged ₹2 for each of the first five overdue days, and ₹5 for every day beyond the fifth. Given the number of days each of N returned books was overdue, report how many were late and what the total fine comes to.

Total library fine for a set of returned books Input: An integer N greater than 0, followed by N values, each the number of days a book was overdue (0 or more). Output: The number of books returned late, and the total fine payable. Method:

[N is the number of books, D is the number of days the current book was overdue,
 FINE is the fine on that one book, LATE counts the books returned late,
 TOTAL accumulates the fine, and I is the loop counter.]

I.    [Read the number of books and reject an impossible one]
      Read N
      if (N <= 0) then
          Display("Number of books must be positive")
          Stop
      endif

II.   [Nothing charged and nothing late yet]
      TOTAL ← 0
      LATE ← 0

III.  [Charge each book in turn]
      Repeat for I = 1, 2, ..., N
          Read D
          FINE ← 0
          if (D > 0) then
              LATE ← LATE + 1
              if (D <= 5) then
                  FINE ← 2 × D
              else
                  FINE ← 10 + 5 × (D − 5)
              endif
          endif
          TOTAL ← TOTAL + FINE
      endfor

IV.   [Report]
      Display("Books returned late : ", LATE)
      Display("Total fine : ", TOTAL)

V.    Stop

Why it works: FINE is reset to 0 at the start of every pass, so a book returned on time contributes nothing and cannot inherit the previous book’s charge. The two rules are applied under conditions that cannot both hold, and together they cover every positive value of D. TOTAL and LATE are set before the repetition and updated once per book, so after N passes they describe all N books. Cost: One pass per book, with at most two comparisons and one addition in each. Nothing is stored, so the method works for any number of books.

The expression 10 + 5 × (D − 5) deserves one sentence. The first five days are charged in full at ₹2 each, which is ₹10, and only the days beyond the fifth are charged at ₹5. Writing 5 × D for a long delay would silently recharge the first five days at the higher rate — a specification error, not a coding one, and no compiler will find it.

Now the translation. Each step becomes the Java form from Table 3.16, the types come from the variable description, and the input is read from the keyboard.

Total library fine for a set of returned books Problem: Read the number of books returned and, for each, the number of days it was overdue. A book returned on time attracts no fine; otherwise ₹2 is charged for each of the first five overdue days and ₹5 for every day beyond the fifth. Display the number of books returned late and the total fine. Reject a book count that is not positive.

import java.util.Scanner;

class LibraryFine
{
    // Reads the number of days each returned book was overdue and displays
    // the number of books returned late and the total fine payable.
    public static void main(String args[])
    {
        Scanner in = new Scanner(System.in);
        System.out.print("Number of books : ");
        int n = in.nextInt();

        if (n <= 0)
        {
            System.out.println("Number of books must be positive");
            return;
        }

        int total = 0;
        int late = 0;

        for (int i = 1; i <= n; i++)
        {
            System.out.print("Days overdue for book " + i + " : ");
            int d = in.nextInt();
            int fine = 0;
            if (d > 0)
            {
                late = late + 1;
                if (d <= 5)
                {
                    fine = 2 * d;
                }
                else
                {
                    fine = 10 + 5 * (d - 5);
                }
            }
            total = total + fine;
        }

        System.out.println("Books returned late : " + late);
        System.out.println("Total fine : " + total);
    }
}

Sample output:

Number of books : 4
Days overdue for book 1 : 0
Days overdue for book 2 : 3
Days overdue for book 3 : 8
Days overdue for book 4 : 5
Books returned late : 3
Total fine : 41

Variable description:

[Table:] Table 3.17 – variable description for the LibraryFine program [/Table] | Variable | Type | Purpose | |—|—|—| | in | Scanner | Reads the values from the keyboard | | n | int | Number of books returned | | i | int | Loop counter, running from 1 to n | | d | int | Days the current book was overdue | | fine | int | Fine on the current book alone | | late | int | Number of books returned late so far | | total | int | Total fine accumulated so far |

Notes: d and fine are declared inside the loop because each belongs to one book only; late and total are declared outside it because they must survive from one pass to the next. Every amount here is a whole number of rupees, so int is correct throughout — had the rates involved paise, double would have been needed and the output would have had to say so. The return; in the rejection branch is the Java form of Stop: it leaves main at once, so nothing after it runs.

The prompts printed before each nextInt are not part of the method, and the algorithm quite properly says nothing about them. They are there because a program that waits silently for input looks to the user like a program that has hung.

3.9.2 Testing on Seen and Unseen Inputs

A program that produces the right answer on the one input you designed with has demonstrated very little. The input you designed with is the input your method was shaped around, and it will be the input your method handles best.

Useful testing has two halves. The seen input is the one given with the specification — the example whose answer is already known, so that any disagreement is unarguable. The unseen inputs are the ones you choose afterwards, and they should be chosen for the same reasons that guided the boundary values of section 3.4.2: the smallest permitted input, the value where a rule changes, the value just past it, an input where nothing happens at all, and an input the program is meant to refuse.

The essential discipline is to work out the expected output by hand before running the program. A result computed after the event is not a prediction; it is an excuse, and it will agree with whatever the program did.

Table 3.18 – test plan for the LibraryFine program, with expected results worked out by hand

Test Input Expected output What it checks
Seen input n = 4; days 0, 3, 8, 5 Late 3, total 41 The specification’s own example
Smallest input, nothing late n = 1; day 0 Late 0, total 0 The loop runs once; a punctual book costs nothing
Exactly at the rule change n = 1; day 5 Late 1, total 10 ₹2 a day still applies on the fifth day
Just past the rule change n = 1; day 6 Late 1, total 15 ₹10 for five days plus ₹5 for the sixth
Every book late n = 2; days 1, 1 Late 2, total 4 The counter accumulates across passes
Refused input n = 0 Message; nothing computed The guard in step I

The third and fourth rows are the pair that earns its place. A program that charges ₹5 a day from the fifth day onwards instead of from the sixth gives 25 for day 5 and 20 for day 6 — visibly wrong to anyone who has worked the numbers out first, and completely invisible to anyone who has not.

Notice also what the fourth row is really testing. It is not the code; it is whether the code and the specification agree about the phrase “beyond the fifth”. Most disputes about a program’s correctness turn out, on inspection, to be disputes about what it was supposed to do.

Q. The program gave the right answer on all six tests. Is it correct?

A. It is correct on those six inputs. Testing can only ever show the presence of errors, never their absence. What justifies believing the program is right in general is the correctness argument made when the method was designed; the tests are what catch the places where that argument was applied carelessly.

3.9.3 Finding and Correcting Errors

Errors come in three kinds, and knowing which kind you are looking at tells you where to look.

A syntax error breaks the rules of the Java language — a missing semicolon, an unmatched brace, a misspelt keyword. The compiler refuses to produce a class file and names the line. These are the cheapest errors to have, because they cannot escape into a finished program.

A runtime error appears while the program is running and stops it. An index outside the bounds of an array, an attempt to divide an integer by zero, a Scanner asked for a number when the user typed a word — the program halts and reports what happened. The message names the fault, and it is worth reading rather than glancing at.

A logical error is the dangerous one. The program compiles, runs to completion, and produces the wrong answer. Nothing reports it, because nothing has been violated except your intention.

Table 3.19 – Syntax, runtime and logical errors

Feature Syntax error Runtime error Logical error
When it is discovered At compilation While the program runs Only when the output is checked
What happens No class file is produced The program stops part-way The program finishes normally
Who reports it The compiler, with a line number The runtime system, with a message Nobody
Typical cause Missing semicolon or brace, misspelt name Index out of bounds, division by zero Wrong condition, wrong formula, wrong order of steps
How it is found Read the compiler message Read the message and the line it names Compare the output with the expected result
How it is fixed Correct the form of the statement Guard the operation or correct the index Re-examine the method, then the code

The cycle a program goes through is shown in Fig. 3.9-1. It is worth noticing how many of the arrows point backwards.

Diagram

Fig. 3.9-1 – flow: design the algorithm → dry run on paper → write the Java code → compile → decision “any syntax errors?” with Yes returning to “write the Java code” and No continuing → run on the seen input → decision “output as expected?” with Yes continuing and No branching to “locate the error” which returns to “dry run on paper” → run on unseen and boundary inputs → decision “all correct?” with No returning to “locate the error” and Yes leading to “program accepted”; label the backward arrows “correct and repeat”

Locating a logical error is a search, and it responds to the same discipline as any other search: halve the region you are looking in. Display the value of a key variable half-way through the method. If it is already wrong there, the fault is before that point; if it is right, the fault is after it. Two or three such probes will usually corner an error that could not be found by staring at the whole program.

Two habits shorten the hunt considerably.

Re-dry-run the failing input, on paper, following the code exactly as written rather than as intended. This is how you find that the loop runs one pass too few, or that a variable is reset where it should not be.

Check the boundaries first. If the program is right on 3 and wrong on 5, and 5 is where a rule changes, the fault is almost certainly in the condition that separates the two rules — not in the arithmetic on either side of it.

writing = where == was meant What students write:

if (d = 5)
{
    fine = 10;
}

What happens: d = 5 is an assignment, not a comparison. It stores 5 in d and yields the value 5, which is not a condition. Java rejects this outright — an int cannot be used where a boolean is required — so here the compiler saves you. The same slip written as if (found = true), where found is a boolean, compiles perfectly: it sets found to true and then tests the value it just stored, so the branch is taken every single time. The fix: Use == for comparison, as in if (d == 5). For a boolean variable, write if (found) and the confusion cannot arise at all.

When a program finally passes every test, the last step is to read it once more against the algorithm it came from. Programs drift during debugging — a condition is loosened to make one test pass, a line is moved to silence an error — and a program that no longer matches its documented method is a program whose correctness argument has quietly expired.

Type in the LibraryFine program and run it on the six tests of Table 3.18, checking each against the expected column. Then change one line: replace if (d <= 5) with if (d < 5). Which of the six tests now fails, which still pass, and what does that tell you about the value of a test placed exactly at a boundary?

3.10 Summary

What an algorithm is
  1. An algorithm is a finite sequence of well-defined steps which, for any valid input, terminates after a finite number of steps and produces the required output.
  2. Five properties are demanded of it: finiteness, definiteness, zero or more inputs, at least one output, and effectiveness. A set of instructions failing any one of them is not an algorithm.
  3. Finiteness is the property most often broken, and almost always in the same way — a repetition whose stopping condition can never become true.
  4. The word comes from the name of Muhammad ibn Musa al-Khwarizmi, rendered as Algoritmi by twelfth-century Latin translators; it first meant calculating with the Hindu–Arabic numerals and later widened to mean any exact step-by-step method.
Representing an algorithm
  1. The step-and-description form pairs each step with a bracketed statement of its purpose, and is preceded by a description of the quantities used.
  2. Pseudocode borrows the structure of a programming language while keeping ordinary vocabulary. This book uses ← for assignment, Read, Display, if ... then ... else ... endif, Repeat while ... endwhile, Repeat for ... endfor, Stop and Return.
  3. Every selection and repetition must be indented and closed explicitly, because on paper there are no braces to show where a block ends.
  4. A flowchart draws the method with five standard symbols — oval for start and stop, parallelogram for input and output, rectangle for a process, diamond for a decision with two exits, and arrows for the order of execution. It suits small methods and becomes unreadable for large ones.
  5. A program is an algorithm expressed in a programming language. The algorithm fixes the method and is language independent; the program adds types, declarations and syntax, and can be executed.
Designing and checking
  1. Design begins by stating the input, the output, the constraints, and what must happen when the input is invalid — not by writing steps.
  2. Every algorithm is assembled from three arrangements only: sequence, selection and repetition.
  3. A counter or an accumulator is initialised once, before the repetition that updates it. Initialising it inside the repetition destroys the running total on every pass.
  4. The variable description table records every variable, its type and its purpose, and is written alongside the method rather than afterwards.
  5. A dry run is the manual execution of an algorithm on a chosen input, recording every variable’s value after every step. It can show that a method is wrong; no number of dry runs can show that it is right.
  6. Correctness comes from an argument about what stays true after every pass of a repetition. The dry run catches the places where that argument was applied carelessly.
  7. Boundary values — the smallest input, the value where a rule changes, the value just past it — find errors that comfortable inputs never reveal. An error of this kind is called an off-by-one error.
  8. Termination must be argued: identify a quantity that moves steadily towards the stopping condition. A loop whose variable advances by more than one must be controlled by < or >, never by = or ≠.
Number problems
  1. The roots of a quadratic equation are decided by the discriminant \(d = b^2 - 4ac\): negative gives imaginary roots, zero gives two equal roots \(-b/2a\), positive gives two distinct real roots. The method must first reject \(a = 0\), which is both not quadratic and a division by zero.
  2. Euclid’s division method finds the greatest common divisor by replacing the pair \((A, B)\) with \((B, A \bmod B)\) until the second becomes zero, at which point the first is the answer. The replacement is valid because both pairs have the same common divisors.
  3. A search for a divisor need go no further than the square root of the number, because if \(N = D \times E\) then at least one of the two factors is no larger than \(\sqrt{N}\). The condition is written D × D <= N to avoid taking a square root at all.
  4. The digits of a number are obtained by repeatedly taking the remainder on division by 10 and then dividing by 10. The digits emerge from the right, and REV ← REV × 10 + R builds the number reversed as they arrive.
Arrays
  1. An array of N elements has indices 0 to N − 1, and its last element is at index N − 1.
  2. Searching for the largest or smallest value starts with the first element as the provisional answer, never with zero — a provisional answer must be a real candidate.
  3. Linear search examines elements in turn, needs no ordering, and costs up to N comparisons. It reports −1 for absence, because 0 is a valid position.
  4. Binary search requires a sorted array and halves the region under consideration at every step, settling a thousand elements in about ten comparisons. Its mistakes live in the boundaries: HIGH must start at N − 1, the middle element must be excluded from the surviving half, and the loop must continue while LOW <= HIGH.
  5. Bubble sort exchanges adjacent elements that are out of order; each pass carries the largest remaining element to the end, and N − 1 passes suffice.
  6. Selection sort finds the smallest element of the unsorted region and places it directly. It makes the same number of comparisons as bubble sort but at most N − 1 exchanges.
  7. Exchanging two values requires a temporary store; assigning one to the other first destroys the value being moved.
  8. Two sorted arrays are merged by repeatedly copying the smaller of the two front elements, then copying whatever remains of the array that is not exhausted. Every element is examined and copied once.
Double dimensional arrays and strings
  1. A double dimensional array is indexed by row and column, both from 0. Row-wise and column-wise traversal differ only in which loop is on the outside, never in how an element is written.
  2. Sorting each row of a matrix applies an ordinary sorting technique to each row in turn, with the row index held fixed; sorting one row cannot disturb another.
  3. In a square matrix the left diagonal is the set of elements A[I][I] and the right diagonal the set A[I][N − 1 − I]. A single repetition reaches both. When N is odd the centre element lies on both diagonals.
  4. A string is indexed from 0 and is immutable — every operation that appears to change one in fact builds a new string.
  5. Words are extracted by scanning character by character, collecting non-space characters and treating a space as the end of a word. Appending one space to the sentence ensures the last word is completed like every other; testing that the collected word is not empty makes repeated spaces harmless.
  6. The same scanning skeleton answers a whole family of questions; only the action taken at the moment a word is completed changes. Placing each completed word in front of the result reverses the order of the words in one pass.
  7. Strings are compared with equals, which tests the characters, not with ==, which tests whether two names refer to the same object.
From algorithm to program
  1. Translation is largely substitution, but three decisions are made only at this stage: the type of every variable, where the input comes from, and the form of the output.
  2. A variable that must survive from one pass to the next is declared outside the loop; one that belongs to a single pass is declared inside it.
  3. Testing uses the seen input given with the specification and unseen inputs chosen at the boundaries. The expected result is worked out by hand before the program is run, or the test proves nothing.
  4. Errors are of three kinds. A syntax error is caught by the compiler and no class file is produced. A runtime error stops the program while it runs and is reported. A logical error is reported by nobody — the program finishes and the answer is wrong.
  5. A logical error is located by halving the search: display a key value part-way through, and decide from it whether the fault lies before or after that point.
  6. After debugging, the program is read once more against the algorithm it came from, because a program that no longer matches its documented method has lost the argument that justified believing it correct.

3.11 Key Terms

  1. algorithm — a finite sequence of well-defined steps which, for any valid input, terminates after a finite number of steps and produces the required output.
  2. binary search — a search on a sorted array that examines the middle element of the region still under consideration and discards the half in which the value cannot lie.
  3. boundary value — an input lying exactly where the behaviour of a method changes, such as the smallest permitted value or the value at which a condition switches.
  4. bubble sort — a sorting technique that repeatedly compares adjacent elements and exchanges them when they are out of order, each pass placing one more element at the end.
  5. column-wise traversal — visiting the elements of a double dimensional array column by column, with the outer repetition running over the columns.
  6. counter — a variable set to zero before a repetition and increased by one each time the event it counts occurs.
  7. definiteness — the requirement that every step of an algorithm has exactly one possible meaning.
  8. discriminant — the quantity \(b^2 - 4ac\), whose sign decides whether the roots of a quadratic equation are imaginary, equal or real and distinct.
  9. double dimensional array — an array whose elements are identified by two indices, a row and a column, both numbered from 0.
  10. dry run — the manual execution of an algorithm on a chosen input, recording the value of every variable after every step.
  11. effectiveness — the requirement that every step of an algorithm can actually be carried out in a finite time.
  12. finiteness — the requirement that an algorithm stops after a finite number of steps for every valid input.
  13. flowchart — a diagram of an algorithm in which each step is a labelled shape and arrows show the order of execution.
  14. GCD — greatest common divisor; the largest number that divides two given numbers exactly.
  15. immutable — describing a value that cannot be changed once created; every operation on a Java String produces a new string rather than altering the existing one.
  16. input — the values, zero or more, supplied to an algorithm before or during its execution.
  17. left diagonal — in a square matrix, the elements whose row and column indices are equal, running from the top left corner to the bottom right.
  18. linear search — a search that examines the elements of an array one after another from the beginning until the value is found or the array is exhausted.
  19. logical error — a fault that leaves the program compiling and running normally but producing a wrong result; nothing reports it.
  20. off-by-one error — a fault in which a method is correct except at the extreme of a range, typically from > written for >= or from a loop that runs one pass too few or too many.
  21. output — the result an algorithm produces; every algorithm must produce at least one.
  22. pass — one complete walk of a repetition over the region of data it is examining.
  23. program — an algorithm expressed in a programming language, in a form that can be compiled and executed.
  24. pseudocode — a way of writing an algorithm that borrows the structure of a programming language while keeping ordinary vocabulary, and obeys no compiler.
  25. repetition — an arrangement in which a group of steps is carried out again and again while a condition holds.
  26. right diagonal — in a square matrix of size N, the elements in row I and column N − 1 − I, running from the top right corner to the bottom left.
  27. row-wise traversal — visiting the elements of a double dimensional array row by row, with the outer repetition running over the rows.
  28. runtime error — a fault that appears while the program is running and stops it, such as an index outside the bounds of an array or a division by zero.
  29. selection — an arrangement in which a condition decides which one of two alternatives is carried out.
  30. selection sort — a sorting technique that finds the smallest element of the unsorted region and exchanges it into the next position to be filled.
  31. sentinel value — a special value agreed in advance to mean that no more data will follow, used to end a repetition that reads input.
  32. sequence — an arrangement in which steps are carried out one after another, each exactly once, in written order.
  33. square matrix — a double dimensional array having as many rows as columns; only such an array has diagonals.
  34. syntax error — a breach of the rules of the language, caught by the compiler, which then produces no class file.
  35. variable description table — a table listing every variable a method uses, with its type and its purpose, written alongside the method as part of its documentation.

3.12 Points to Ponder

  1. A dry run can show that a method is wrong but can never show that it is right. Why, then, do most programmers spend far more time tracing than proving? Is that a failure of discipline, or is there something a trace gives you that an argument does not?

  2. Binary search beats linear search only when the array is already sorted, and sorting an array costs far more than searching it once. Under what circumstances does the faster method actually save anything — and how would you decide, before writing any code, which side of that line your problem falls on?

  3. Bubble sort and selection sort make the same number of comparisons, and selection sort moves the data less. If neither is clearly better on every count, on what grounds would you ever choose one over the other? What would you need to know about the data first?

  4. An algorithm is said to be language independent, yet every algorithm in this chapter used an assignment arrow, counted array positions from 0, and relied on division that discards the fractional part. Those conventions came from programming languages. How independent is an algorithm really, and does it matter?

  5. A program that passes every test you can devise is not the same as a program that is correct. What would it take to close that gap completely? Is it ever closed in practice, and if not, what makes us willing to use programs at all?

  6. The chapter insisted that awkward inputs be dealt with in the algorithm rather than patched in while coding. The finished program is the same either way. So what exactly is lost when the check is added later?

3.13 Objective Questions

  1. Which property of an algorithm is broken by a repetition whose stopping condition can never become true?
  1. Definiteness
  2. Finiteness
  3. Effectiveness
  4. Output [1 mark]
  1. In an array of N elements, the index of the last element is:
  1. N
  2. N + 1
  3. N − 1
  4. 1 [1 mark]
  1. Binary search may be applied only when the array is:
  1. of even size
  2. sorted
  3. made up of integers
  4. free of duplicate values [1 mark]
  1. After the first pass of a bubble sort in ascending order, which element is certainly in its final position?
  1. The smallest, at the beginning
  2. The largest, at the end
  3. The middle element
  4. None; no element is settled until the last pass [1 mark]
  1. A fault that allows a program to compile and run to completion but produces a wrong answer is called:
  1. a syntax error
  2. a runtime error
  3. a logical error
  4. a compilation error [1 mark]

  1. Fill in the blanks. For two int operands in Java, the value of 17 % 10 is ______ and the value of 17 / 10 is ______. [1 mark]

  2. State whether true or false: in a square matrix of odd order, the centre element lies on both the left diagonal and the right diagonal. [1 mark]

  3. Write the full form of GCD. [1 mark]

  4. Match each flowchart symbol in Column A with its use in Column B.

Column A Column B
a. Oval i. A calculation or an assignment
b. Parallelogram ii. A condition with two exits
c. Rectangle iii. The start or the stop of the method
d. Diamond iv. Input from, or output to, the user
  1. Assertion (A): A dry run that produces the expected output proves that the algorithm is correct. Reason (R): A dry run carries out the algorithm exactly as written, on one particular input. Based on the above statements, choose the appropriate option:
  1. Both Assertion (A) and Reason (R) are true and Reason (R) is the correct explanation of Assertion (A).
  2. Both Assertion (A) and Reason (R) are true and Reason (R) is not the correct explanation of Assertion (A).
  3. Assertion (A) is true but Reason (R) is false.
  4. Assertion (A) is false but Reason (R) is true. [1 mark]
  1. Assertion (A): Binary search may report that a value is absent from an array in which it is actually present. Reason (R): Binary search discards half of the region under consideration without examining any element in it. Based on the above statements, choose the appropriate option:
  1. Both Assertion (A) and Reason (R) are true and Reason (R) is the correct explanation of Assertion (A).
  2. Both Assertion (A) and Reason (R) are true and Reason (R) is not the correct explanation of Assertion (A).
  3. Assertion (A) is true but Reason (R) is false.
  4. Assertion (A) is false but Reason (R) is true. [1 mark]

3.14 Check Your Concepts

  1. Define an algorithm. State any two of the properties that every algorithm must satisfy. [2 marks]

  2. What is a dry run? State one thing a dry run can establish about an algorithm and one thing it cannot. [2 marks]

  3. A search method reports −1 when the value sought is not present. Give the reason why 0 cannot be used for this purpose. [2 marks]

  4. Differentiate between an algorithm and a program, giving any three points of difference. [3 marks]

  5. Differentiate between linear search and binary search on the basis of (i) what the method requires of the data, (ii) the worst-case number of comparisons on an array of N elements, and (iii) how the region still under examination shrinks. [3 marks]

  6. An algorithm sets a variable to 1 and then repeatedly adds 4 to it, stopping when the variable becomes exactly 20. Explain why this algorithm does not terminate, and state the correction needed. [3 marks]

  7. Write an algorithm that accepts a positive integer and displays both the sum of its digits and the number written in reverse, using a single repetition. Include the description of every variable used. [4 marks]

  8. The values 52, 7, 38, 15 and 26 are to be arranged in ascending order using the selection sort technique. Show the contents of the array after each pass, and state how many exchanges are made altogether. [4 marks]

  9. While finding the largest value in an array, a student initialises the provisional maximum to 0. Explain, with a suitable example, why this is wrong, and state the correct initialisation. [4 marks]

  10. Write an algorithm that accepts N integers into a single dimensional array and displays the second largest value among them. Your answer must include the algorithm, a statement of why it works, and the number of comparisons it makes in terms of N. Assume the array holds at least two distinct values. [6 marks]

  11. Compare bubble sort and selection sort with respect to the number of comparisons made, the number of exchanges made, the end of the array at which the sorted region grows, and their behaviour on data that is already in order. On that evidence, say which of the two you would prefer for arranging a large array of long names, and give your reason. [6 marks]

3.15 Output & Debugging

  1. Write the exact output of the following fragment, and state in one line what it computes.
int n = 4;
int f = 1;
for (int i = 1; i <= n; i++)
{
    f = f * i;
    System.out.println(i + " " + f);
}

[3 marks]

  1. The following fragment is meant to display the sum of the elements of the array. Identify the error, state what happens when the fragment is run, and rewrite the faulty line correctly.
int a[] = {5, 9, 2, 7};
int s = 0;
for (int i = 0; i <= a.length; i++)
{
    s = s + a[i];
}
System.out.println(s);

[3 marks]

  1. Write the output of the following fragment, and state what it computes for a general positive value of x.
int x = 27;
int c = 0;
while (x > 0)
{
    c = c + x % 10;
    x = x / 10;
}
System.out.println(c);

[2 marks]

  1. State what the following fragment prints. Explain why it prints that, and give the single change that would make it print matched.
String w = "";
w = w + 'y';
w = w + 'e';
w = w + 's';
if (w == "yes")
{
    System.out.println("matched");
}
else
{
    System.out.println("not matched");
}

[3 marks]

  1. How many times is the statement c = c + 1; executed? Write the value printed.
int c = 0;
for (int i = 1; i <= 4; i++)
{
    for (int j = 1; j <= 4 - i; j++)
    {
        c = c + 1;
    }
}
System.out.println(c);

[2 marks]

3.16 Programming Practice

  1. Write a single method boolean isPrime(int n) that returns true when n is a prime number and false otherwise. The method must not examine any trial divisor larger than the square root of n, and must give the correct answer for n = 1 and n = 2. Submit the method only, together with a variable description table for the variables it uses. [4 marks]

  2. Two single dimensional arrays hold M and N integers respectively, each already arranged in ascending order. Write a program that merges them into a third array of M + N elements which is also in ascending order, and displays the merged array. The two input arrays may be fixed in the program; state clearly which values you have used. Submit the algorithm, the complete class, and a variable description table.

Sample input: first array 4, 11, 19; second array 2, 11, 15, 30. The merged array must contain all seven values, with 11 appearing twice. [6 marks]

  1. Write a program that accepts a sentence terminated by a full stop and displays every word of more than four characters on a line of its own, followed by the total number of such words. Words are separated by one or more blank spaces, and the program must work correctly when the sentence contains extra spaces between words. Submit the algorithm, the complete class, and a variable description table.

Sample input: A crowded platform at the railway station. [6 marks]

  1. Write a program that accepts the order M of a square matrix, where M must be greater than 2 and less than 10, and then accepts M × M integers into the matrix. Display an appropriate message and stop if M is outside the permitted range. Otherwise display the matrix in the form of a square, followed by the sum of the elements of its left diagonal and the sum of the elements of its right diagonal, each on a line of its own. Submit the complete class and a variable description table.

Sample input: M = 3, with the values 5, 2, 9, 4, 7, 1, 6, 3, 8 entered row by row. [6 marks]