MGU Computer Science Series — Computer Science Foundations
Part II: Programming Foundations
Algorithms · Pseudocode · Flowcharts · Tracing · Correctness
Chapter 5 of 28
MGU Computer Science Series  ·  Computer Science Foundations  ·  Library Textbook Edition

Chapter 5:
Algorithms
and Instructions

What algorithms are, how to write them in pseudocode and flowcharts, how to trace them step by step, and how to evaluate whether they are correct — the conceptual foundation for every programming chapter that follows

■ CS Level: Foundations  ·  Part II ■

■ 10 Sections  •  Chapter 5 of 28 ■

Follows Chapter 4: Data, Representation, and Binary  ·  Prepares students for Chapter 6: Programming Languages and Code

Chapter 5 — Front Matter

Purpose and Overview

This chapter introduces algorithms as the central idea connecting problem solving to computing. An algorithm is a precise, step-by-step procedure for solving a problem or accomplishing a task. Before a programmer writes a single line of code, they need to understand what procedure that code will carry out. This chapter teaches students how algorithms are designed, described, traced, tested, and evaluated. Students will practice writing pseudocode, drawing flowcharts, tracing algorithms by hand, and judging whether a procedure is correct. These skills apply to every chapter in this textbook and to every course in computing that follows.

Every program you have ever used — from a navigation app to a search engine to a video game — is the expression of one or more algorithms. Understanding what algorithms are and how to think about them is not a preliminary step before real computer science. It is real computer science. The professional habits introduced here — specification, precision, tracing, testing, and systematic error-finding — will serve you throughout every computing course you take.

Opening Question

Imagine you want to teach someone who has never seen a deck of cards how to find the highest-value card in a shuffled hand of ten cards. You cannot just say "find the highest one" — that is not precise enough for someone who does not already know what to do. You must describe exactly what steps to follow, in what order, for any hand of cards they might be dealt. Writing that procedure out clearly, so it works every time for any valid input, is exactly what algorithm design requires. By the end of this chapter, you will know how to write procedures like that precisely — and how to check that they really work.

10Sections
10Objectives
19Key Terms
12+Worked Examples

Learning Objectives

  1. 1Define an algorithm and explain its four defining characteristics.
  2. 2Specify the inputs and outputs of a given algorithm precisely.
  3. 3Explain why the order of steps matters in a sequential algorithm.
  4. 4Write algorithms using the pseudocode conventions used in this textbook.
  5. 5Draw and read flowcharts using standard symbols for start/end, process, decision, and input/output.
  6. 6Trace an algorithm step by step using a trace table, recording variable values at each step.
  7. 7Identify and explain what total correctness requires of an algorithm.
  8. 8Test an algorithm against typical inputs, boundary values, and edge cases.
  9. 9Identify common algorithm errors including step-order errors, termination failures, and logic mistakes.
  10. 10Explain the relationship between an algorithm and the program that implements it.

Before You Begin

What you already know. Chapter 3 introduced computational thinking — including decomposition, pattern recognition, abstraction, and algorithmic thinking. Chapter 4 showed that computers work with data represented as bits. You have also been solving step-by-step problems your whole life: following a recipe, carrying out long division, navigating using directions, playing a game by its rules.

What you will learn. This chapter formalizes the idea of a procedure into the precise concept of an algorithm. You will learn how to write algorithms down in pseudocode and flowcharts, how to follow them mechanically using trace tables, and how to reason about whether they produce the correct result for any valid input.

What comes next. Chapter 6 will show how algorithms are expressed in programming languages — transforming the pseudocode you write here into real code a computer can run. Every programming chapter in Part II builds directly on the habits introduced in this chapter.

Chapter 5 — Contents

Sections at a Glance

Sections 5.1 – 5.4
What Algorithms Are and How to Specify Them
Definition · Inputs and Outputs · Sequence · Precision
Section 5.1

What an Algorithm Is

The word algorithm comes from the name of a ninth-century Persian mathematician, Muhammad ibn Musa al-Khwarizmi, whose work on systematic calculation methods laid important foundations for algebra and influenced European mathematics for centuries. Today the word refers to any precise, finite, step-by-step procedure that solves a problem or accomplishes a goal.

This definition has four key parts, and each one matters. An algorithm must be a procedure — a sequence of actions, not a single step. It must be precise — every step clear enough to follow without guessing. It must be finite — it must eventually stop and produce a result. And it must work on inputs to produce outputs, making it general enough to handle a class of problems, not just one specific case.

Notice that nothing in this definition requires a computer. Algorithms existed long before computers did. A recipe is an algorithm for preparing food. Long division is an algorithm for dividing large numbers. The rules of a card game define an algorithm for play. Computer science did not invent the idea of a precise procedure — it inherited it, and then made it the central object of study.

The Four Characteristics of an Algorithm

Precise — Every step is described clearly enough to follow without guessing or making assumptions.

Finite — The procedure eventually stops. An algorithm that runs forever produces no answer and solves no problem.

Input → Output — The algorithm accepts some starting information (possibly none) and produces a result.

General — The algorithm solves a class of problems, not just one particular case. It must work for any valid input, not only the one you happened to test.

The Everyday Algorithm Test

You can evaluate whether something is a true algorithm by asking four questions. Are the steps precise enough to follow without guessing? Does the procedure eventually stop? Does it produce a result? Does it work for different valid inputs, not just one specific case? If the answer to all four is yes, you have an algorithm. If any answer is no, you have a starting point that needs refinement.

Example 5.1.1
Evaluating whether a procedure is an algorithm
  • Candidate A"To make toast: put bread in the toaster, press the lever down, wait until it pops up, remove the toast."
  • Analysis AThis is a good algorithm. The steps are clear, the procedure terminates, it produces output (toast), and it works for any slice of bread.
  • Candidate B"To find the largest number in a list, keep looking through the list until you find the biggest one."
  • Analysis BThis is not an algorithm. "Keep looking until you find the biggest one" is too vague — it does not say how to decide which one is biggest. A person following this instruction literally does not know what to compare or when to stop.
  • Candidate C"To find the largest number in a list: record the first number as your current largest. Then look at each remaining number in order. If that number is larger than your current largest, replace your current largest with that number. After examining every number, your current largest is the answer."
  • Analysis CThis is a proper algorithm. It is precise, terminates after examining every element exactly once, produces the correct answer, and works for any list with at least one number.
Candidate C is the algorithm. A and C are good procedures; B fails the precision test.
Key Insight

The difference between Candidates B and C above is not the goal — both aim to find the largest number. The difference is how clearly the procedure is described. Candidate C tells you exactly what to do at every step. This is the essential discipline of algorithm design: achieving the right level of precision so the procedure can be followed consistently.

Practice 5.1Concept Check
  1. In your own words, state the four defining characteristics of an algorithm. Give a brief example of each.
  2. Why must an algorithm be general rather than solving only one specific case?
  3. Explain why "sort the list somehow" fails the precision test for an algorithm.
  4. Evaluate: "To find a name in a phone book, open to any page and check if the name is on it." Is this an algorithm? If not, which characteristics does it fail?
  5. Is the set of traffic laws an algorithm? Identify which characteristics are satisfied and which are not.
Section 5.2

Inputs and Outputs

Every algorithm works on some information. The information an algorithm receives before it begins is called its input. The information it produces when it finishes is called its output. Specifying both precisely before writing any steps is one of the most important habits in algorithm design — it forces you to think carefully about what the algorithm actually needs and what it promises to deliver.

Input specification questions matter more than they first appear. Consider an algorithm for computing a letter grade from a test score. You might think the input is simply "the test score." But a careful designer asks: What type of number — a whole number or a decimal? What range is valid — 0 to 100? Can the score be negative? What happens if someone provides a score of 150? Answering these questions before writing the algorithm prevents many errors. If you do not know what the algorithm is allowed to receive, you cannot know when it is correct.

Output specification is equally important. Does the grade algorithm return a single letter? A percentage alongside the letter? A message? Specifying this upfront prevents the algorithm from producing a result that does not match what the caller expected.

Algorithm Header Format

Begin every algorithm with a header that states its name, inputs, and outputs clearly.

Algorithm: ComputeLetterGrade

Input: A whole number score between 0 and 100 inclusive

Output: A letter grade — A, B, C, D, or F

Some algorithms take no input at all — an algorithm that returns the current system time or generates a random number does not need any starting information from the caller. Some algorithms produce multiple outputs. An algorithm that processes a list of test scores might output both the highest score and the class average. When multiple outputs exist, list them all in the header so the reader knows exactly what to expect.

Example 5.2.1
Specifying inputs and outputs precisely
  • TaskFor each task below, write an algorithm header specifying inputs and outputs.
TaskInputOutput
Find the sum of a list of numbersA list of numbers (at least one element)Their sum
Check whether a word is a palindromeA word (a non-empty string of letters)True or False
Convert Celsius to FahrenheitA temperature in degrees Celsius (any real number)The equivalent temperature in degrees Fahrenheit
Sort a list of namesA list of names (may be empty)The same names in alphabetical order
Find both the minimum and maximumA list of numbers (at least one element)The minimum value and the maximum value
Notice that each input specification states the type, the allowed range, and any constraints. These details are not bureaucracy — they directly affect how the algorithm must be written.
Practice 5.2Input and Output Specification
  1. Write an algorithm header (name, input, output) for an algorithm that computes the area of a rectangle.
  2. Write an algorithm header for an algorithm that determines whether a number is even or odd.
  3. Write an algorithm header for an algorithm that finds the second-largest number in a list.
  4. A classmate writes: "Input: a number. Output: its square root." Identify two things that should be specified more carefully in this header.
  5. Give an example of an algorithm that produces two separate outputs. Write its header.
Section 5.3

Sequence and Order

An algorithm is a sequence of steps, and the order of those steps matters enormously. When a computer executes a sequential algorithm, it performs step 1, then step 2, then step 3, in exactly that order — nothing skipped, nothing reordered. This is called sequential execution. It is the simplest form of algorithm control structure, and it forms the backbone of every program, even those that also include decisions and loops.

Consider a simple algorithm for making tea: boil water, place a tea bag in a cup, pour the boiling water into the cup, wait three to five minutes, remove the tea bag, add milk or sugar if desired. Now imagine reversing steps one and three: pour cold water into the cup, then boil the water already in the cup. Every individual step is present. But the result is wrong — cold tea — because the order is wrong.

Order errors are among the most common and most insidious algorithm mistakes. They are insidious because all the correct steps are there; only their positions are wrong. A quick glance at an algorithm with an order error can look correct. This is why tracing — following an algorithm step by step with a real input — is so important. Section 5.7 covers tracing in detail.

Example 5.3.1
Finding and correcting a step-order error
  • ProblemThe following algorithm contains a step-order error. Find it and state the correct order.
Pseudocode with ErrorAlgorithm: AverageOfThreeNumbers Input: Three numbers A, B, and C Output: Their average Step 1. SET sum TO 0 Step 2. SET average TO sum / 3 // ← error: divides before adding Step 3. SET sum TO sum + A Step 4. SET sum TO sum + B Step 5. SET sum TO sum + C Step 6. OUTPUT average
  • AnalysisStep 2 divides sum by 3 before Steps 3–5 have added anything to it. At Step 2, sum is still 0, so average will always be 0 regardless of the inputs A, B, and C.
  • FixMove the division step to after Steps 3, 4, and 5 have all completed. The corrected order is: 1, 3, 4, 5, then compute average, then output.
The error: Step 2 executes before the sum is populated. Correct order: initialize sum → add A → add B → add C → compute average → output.
Practice 5.3Sequence and Order
  1. Write a six-step algorithm for making a cup of instant coffee. Then deliberately introduce one step-order error and exchange with a classmate to find each other's error.
  2. The following steps are out of order for a "find the minimum value" algorithm. Arrange them correctly: (a) Output smallest. (b) If the current value is less than smallest, set smallest to that value. (c) Set smallest to the first element of the list. (d) Move to the next element. (e) Repeat steps (b) and (d) until no elements remain.
  3. Explain why a computer cannot automatically fix step-order errors the way a human reader sometimes can.
Section 5.4

Precision in Instructions

A good algorithm is not just ordered correctly — it is precise. Every step must be described specifically enough that the person or machine following it knows exactly what to do without making any assumptions. This is harder than it sounds, because natural language is full of ambiguity that human readers resolve automatically through context and experience. Computers have no such ability. If an instruction is vague, a computer cannot proceed.

Consider the instruction: "Find the biggest number." Biggest in what set? What does "find" mean — look at it, store it, print it? Where should the result go? A human reader might infer answers from context. A computer executes only what it is explicitly told. Algorithm instructions must leave no room for interpretation.

LevelExampleNotes
Informal"Sort the list somehow."Not algorithmic — too vague to execute
Semi-precise"Sort the list from smallest to largest."States the goal but not the procedure
Algorithmic"Compare adjacent pairs. Swap if left > right. Repeat until no swaps occur."Precise enough for consistent execution
Code-levelsorted_list = sorted(numbers)Ready for a computer to execute directly

Precision often requires naming the values your algorithm tracks. Rather than saying "take the first number and add it to the running total," a precise algorithm assigns names to these values. These named storage locations are called variables. A variable is a named location used to hold a value while the algorithm runs. Chapter 7 covers variables in detail. For now, think of a variable as a labelled box that holds one value at a time, where the label is the name you give it.

Design Habit — Name Your Values

Before writing any algorithm steps, list the values your algorithm will need to track, give each one a clear name, and describe what it holds. For example: total — the running sum of all numbers seen so far; count — how many numbers have been processed; average — the final result to be output. This naming step prevents vague instructions and makes the algorithm much easier to trace.

Practice 5.4Precision
  1. Rewrite the instruction "find the highest temperature in a list" at the algorithmic level of precision. Name any variables you introduce.
  2. Identify two things that are ambiguous about the instruction: "Divide the first number by the second and output the result."
  3. Choose a simple everyday procedure (tying a shoe, locking a door, sending a text message). Write it at the algorithmic level of precision. Test your algorithm by having someone else follow it literally.
Sections 5.5 – 5.6
Writing Algorithms: Pseudocode and Flowcharts
Pseudocode Conventions · Flowchart Symbols · Reading and Drawing Both
Section 5.5

Pseudocode

Pseudocode is a way of writing algorithms using structured, English-like language that resembles programming code but does not follow the exact syntax rules of any specific language. The word "pseudo" means false or imitation — pseudocode imitates the structure of code without requiring the precision a compiler demands.

Pseudocode matters for several reasons. It forces you to think through algorithm logic before worrying about a particular language's syntax rules. It is language-independent — the same pseudocode can guide implementations in Python, JavaScript, Java, or any other language. It is readable by non-programmers, which makes it useful for explaining algorithms to collaborators. And it is fast to write, because you are thinking about logic rather than looking up syntax.

The most common beginner mistake is to skip pseudocode and try to write real code immediately. This approach leads to programs whose logic is unclear, whose errors are hard to diagnose, and whose relationship to the original problem is difficult to explain. Professional programmers write pseudocode — or its equivalent in clear design notes — before writing code, even when they are experienced. The habit of thinking through an algorithm before expressing it saves time overall.

Pseudocode Conventions Used in This Textbook

Pseudocode Reference — Core Conventions

SET variable TO value  —  Assign a value to a named variable. Also written as variable ← value.

INPUT variable  —  Receive a value from outside the algorithm.

OUTPUT value  —  Produce a result. Also written as PRINT value.

IF condition THEN ... ELSE ... END IF  —  Conditional execution.

WHILE condition DO ... END WHILE  —  Repeat while a condition is true.

FOR EACH item IN list DO ... END FOR  —  Process each element of a collection.

// comment text  —  An explanatory note; not an algorithm step.

Example 5.5.1
Reading pseudocode for FindMaximum
Pseudocode// Algorithm: FindMaximum // Input: A list called values with at least one element // Output: The largest number in the list SET maximum TO values[0] // Start with the first element SET index TO 1 WHILE index < length(values) DO IF values[index] > maximum THEN SET maximum TO values[index] END IF SET index TO index + 1 END WHILE OUTPUT maximum
  • Q: values[0]?The first element of the list. Indexing starts at 0 in most computing conventions.
  • Q: length(values)?The number of elements in the list. For the list [3, 7, 1, 9, 4], this is 5.
  • Q: What happens when a larger value is found?maximum is updated to hold that larger value, replacing the old maximum.
  • Q: When does the loop stop?When index equals length(values) — meaning every element has been examined exactly once.
For input [3, 7, 1, 9, 4]: maximum starts at 3, updates to 7, stays 7, updates to 9, stays 9. Output: 9.
Example 5.5.2
Writing pseudocode for a grade calculator
Pseudocode// Algorithm: ComputeLetterGrade // Input: A whole number score between 0 and 100 inclusive // Output: A letter grade — A, B, C, D, or F INPUT score IF score >= 90 THEN SET grade TO "A" ELSE IF score >= 80 THEN SET grade TO "B" ELSE IF score >= 70 THEN SET grade TO "C" ELSE IF score >= 60 THEN SET grade TO "D" ELSE SET grade TO "F" END IF OUTPUT grade
Each ELSE IF is only reached if all previous conditions were false. A score of 85 passes the first test (85 ≥ 90? No), then matches the second (85 ≥ 80? Yes) and outputs "B".
Common Mistake — Writing Code Before Pseudocode

Many beginners try to write Python (or another language) before they have thought through the algorithm. When the code does not work, they have two problems: a logic error and a syntax problem at the same time, which makes debugging twice as hard. Write the pseudocode first, trace it to confirm the logic, and then translate to code. The translation step is quick; the design step is where the real thinking happens.

Practice 5.5Writing and Reading Pseudocode
  1. Write pseudocode for an algorithm that takes two numbers as input and outputs the larger of the two. Include the header.
  2. Write pseudocode for an algorithm that counts from 1 to 10, outputting each number.
  3. Write pseudocode for an algorithm that takes a list of numbers and outputs how many of them are greater than 50.
  4. Read the following pseudocode and describe in plain English what it does:
    SET result TO 1 SET i TO 1 WHILE i <= n DO SET result TO result * i SET i TO i + 1 END WHILE OUTPUT result
  5. Write pseudocode for an algorithm that takes three test scores, computes the weighted average (the first score is worth 30%, the second 30%, the third 40%), and outputs the average and the corresponding letter grade.
Section 5.6

Flowcharts

A flowchart is a visual diagram that represents an algorithm using standard symbols connected by arrows showing the direction of execution. Flowcharts are useful because they make an algorithm's structure visible at a glance. Sequential steps, decisions, and loops become obvious in a way that is harder to see in text.

Flowcharts do not replace pseudocode — they complement it. Pseudocode captures logic details precisely; flowcharts reveal overall structure quickly. A student learning a new algorithm often benefits from seeing both: the flowchart to understand the shape of the procedure, and the pseudocode to understand each step exactly.

Standard Flowchart Symbols

Flowchart Symbol Reference
Start / EndTerminal — rounded rectangle marks the start or end of the algorithm
ProcessRectangle — an action or calculation: set a variable, perform arithmetic
Decision Diamond — a yes/no question; two paths emerge labeled Yes and No
Input / OutputParallelogram — receiving input from outside or producing output

Arrows connect all symbols and show direction of flow. Every flowchart starts and ends with a terminal. Decision diamonds always have exactly two exit arrows.

Drawing Conventions

A well-drawn flowchart follows a few simple conventions. Every flowchart begins with a Start terminal and ends with an End terminal. Arrows show the direction of flow; the algorithm should read top-to-bottom and left-to-right wherever possible. Decision diamonds always have exactly two exit paths, each labeled with the condition that produces it — typically "Yes" and "No" or "True" and "False." Loops are shown by a path that returns upward to an earlier step. Never draw an arrow that points nowhere, and never draw a step that cannot be reached by following arrows from Start.

Example 5.6.1
Flowchart for a positive/negative/zero classifier
  • AlgorithmInput a number. If it is positive, output "Positive." If it is negative, output "Negative." If it is zero, output "Zero."
START INPUT number number > 0? Yes "Positive" No number < 0? Yes "Negative" No OUTPUT "Zero" END
Each decision diamond has exactly two labeled exit arrows. All three output paths converge at END. The structure makes the three-branch logic immediately visible.
Example 5.6.2
Comparing pseudocode and flowchart for the same algorithm
PseudocodeFlowchart
Text-based; captures detail preciselyVisual; reveals structure at a glance
Faster to write for complex logicEasier to present to non-programmers
Closer to programming codeLoops and branches are visually obvious
Preferred when working through detailsPreferred when explaining or presenting
Neither format is better in every situation. Professional algorithm designers use both: pseudocode when designing, flowcharts when communicating.
Practice 5.6Drawing and Reading Flowcharts
  1. Draw a flowchart for: "Input two numbers. Output their sum, difference, and product."
  2. Draw a flowchart for: "Input a number. If it is greater than 100, output 'Large.' If it is 10 to 100 inclusive, output 'Medium.' If it is less than 10, output 'Small.'"
  3. Draw a flowchart for a loop that inputs 5 numbers one at a time and keeps a running total. After all 5 are entered, output the total.
  4. Convert the ComputeLetterGrade pseudocode from Section 5.5 into a flowchart.
  5. Describe in words the algorithm represented by this flowchart sequence: Start → Input N → Set count = 0 → [Is count < N?] → Yes: Output count, increment count, loop back → No: End.
Sections 5.7 – 5.10
Tracing, Correctness, and the Algorithm–Program Connection
Trace Tables · Correctness · Algorithms in Life · From Algorithm to Program
Section 5.7

Tracing an Algorithm

Tracing an algorithm means following it step by step, exactly as a computer would execute it, keeping careful track of every variable's value after each step. Tracing is the primary tool for checking whether an algorithm is correct before writing code, and it is the primary debugging tool once code has been written.

Students often want to skip tracing because it feels slow. This is a mistake. Experienced programmers trace algorithms — or their equivalent in code — constantly, because tracing reveals logic errors that look fine on paper but fail in execution. Tracing makes the behavior of loops concrete. It catches off-by-one errors (processing one too many or too few steps). And it shows exactly what happens with unusual or boundary inputs. The habit of tracing saves far more time than it costs.

The Trace Table

A trace table is an organized table used to record the state of an algorithm at each step. The columns are the algorithm's variables (and sometimes the step number and the action taken). Each row records the values of every variable after one step of execution. A trace table makes it impossible to lose track of a variable's value, which is the most common cause of tracing errors.

Example 5.7.1
Tracing a loop — computing an average
Algorithm to Trace — Input: values = [4, 2, 7, 1]SET total TO 0 SET count TO 0 FOR EACH number IN values DO SET total TO total + number SET count TO count + 1 END FOR SET average TO total / count OUTPUT average
StepActiontotalcountnumberaverage
StartInitialize00——
Iter 1number=4; total=0+4; count=0+1414—
Iter 2number=2; total=4+2; count=1+1622—
Iter 3number=7; total=6+7; count=2+11337—
Iter 4number=1; total=13+1; count=3+11441—
After loopaverage = 14 / 414413.5
OutputPrint average———3.5
Output: 3.5. This is correct — the average of 4, 2, 7, and 1 is (4+2+7+1)/4 = 14/4 = 3.5.
Example 5.7.2
Tracing a conditional — only the taken path is followed
Algorithm to Trace — Input: score = 85INPUT score IF score >= 90 THEN SET grade TO "A" ELSE IF score >= 80 THEN SET grade TO "B" ELSE IF score >= 70 THEN SET grade TO "C" ELSE SET grade TO "F" END IF OUTPUT grade
StepCondition CheckedResultgrade
INPUT—score = 85—
IF85 ≥ 90?False — skip A branch—
ELSE IF85 ≥ 80?True — enter B branch"B"
OUTPUT—Print "B""B"
The "score ≥ 70" and "else" branches are never evaluated. Once the True branch is found and taken, all remaining conditions are skipped. This is how conditional execution works.
Tracing Rule — Follow Only the Path Taken

When tracing a conditional, follow only the branch whose condition is true for the specific input you are testing. Do not evaluate what would have happened in other branches. Each trace is for one specific input at a time. To test multiple branches, trace the algorithm multiple times with different inputs.

Practice 5.7Algorithm Tracing

For each algorithm, construct a complete trace table using the given input.

  1. Trace with n = 5:
    SET result TO 1 SET i TO 1 WHILE i <= n DO SET result TO result * i SET i TO i + 1 END WHILE OUTPUT result
    What does this algorithm compute?
  2. Trace with values = [10, 3, 8, 6, 2]:
    SET smallest TO values[0] SET index TO 1 WHILE index < length(values) DO IF values[index] < smallest THEN SET smallest TO values[index] END IF SET index TO index + 1 END WHILE OUTPUT smallest
  3. Trace the ComputeLetterGrade algorithm from Section 5.5 with (a) score = 72, (b) score = 90, (c) score = 55. Show the trace table for each.
  4. Trace with word = "level":
    SET reversed TO "" SET index TO length(word) - 1 WHILE index >= 0 DO SET reversed TO reversed + word[index] SET index TO index - 1 END WHILE IF reversed = word THEN OUTPUT "Palindrome" ELSE OUTPUT "Not a palindrome" END IF
Section 5.8

Correctness

An algorithm is correct if, for every valid input, it produces the correct output according to its specification and always eventually terminates. Correctness is not the same as "it worked once when I tested it." A single successful test does not guarantee correctness. A correct algorithm works for all valid inputs — including unusual ones, boundary values, and edge cases.

Computer scientists distinguish three related concepts. Partial correctness means that if the algorithm terminates, its output is right. This checks the logic of the steps but ignores whether the algorithm always stops. Termination means the algorithm always eventually stops for every valid input. Total correctness is the combination: the algorithm always terminates and always produces the right answer.

In practice, most algorithms in an introductory course are trivially terminating — they process a fixed list or count through a known range, so they always stop. The more difficult requirement to verify is usually partial correctness: does the logic actually produce the right result for every input, or only for the inputs that happened to be tested?

Testing Multiple Input Types

Good algorithm designers test against multiple categories of input. A typical input is a normal case in the middle of the valid range. A boundary value is an input at the smallest or largest allowed value. An edge case is an unusual or extreme value that might reveal special-case errors. Testing all three categories is necessary to build real confidence in correctness.

Example 5.8.1
Testing a division algorithm for correctness failures
Algorithm: DivideAlgorithm: Divide Input: Two numbers — numerator and denominator Output: Their quotient SET result TO numerator / denominator OUTPUT result
Test TypenumeratordenominatorExpectedProblem?
Typical1025.0Works correctly
Boundary050.0Works correctly
Edge case50?Division by zero — error!
Large values1,000,0003≈333,333.33Works correctly
The algorithm is NOT totally correct. It fails when denominator is zero. A correct version must check for this case before dividing — either by specifying it as a precondition or by handling it explicitly.
Preconditions

A precondition is a condition that must be true before an algorithm begins. If the precondition is not met, the algorithm makes no guarantees about its output. For the division algorithm, a precondition might be: "denominator is not equal to zero." Specifying preconditions is useful for design and documentation, but real software must usually handle invalid inputs explicitly rather than simply requiring users to be perfect.

Common Mistake — Testing Only Typical Cases

Most algorithms are easy to make work for typical inputs. The failures almost always occur at boundary values and edge cases: the empty list, the single-element list, a value of zero, a negative number, the last element of an array. Always test these before declaring an algorithm correct.

Practice 5.8Correctness Testing
  1. For each algorithm below, identify one input that might reveal a correctness failure. Explain what goes wrong.

    a. An algorithm that divides its input by (the input minus 10).
    b. An algorithm that finds the second-largest element in a list, assuming the list always has at least two elements.
    c. An algorithm that searches a list for a value by checking positions 0 through 9, assuming every list has exactly 10 elements.
  2. Write three test cases (typical, boundary, edge case) for an algorithm that computes the square root of a number. For the edge case, what special input should be tested?
  3. An algorithm counts how many times the word "the" appears in a sentence. What inputs would you use to test boundary and edge cases? List at least three specific test sentences.
  4. What is the difference between partial correctness and total correctness? Give a brief example of an algorithm that has partial correctness but not total correctness.
Section 5.9

Algorithms in Everyday Life

Algorithms appear wherever precise, repeatable procedures are needed. Recognizing them in everyday life deepens your understanding of what algorithm design actually requires — and reveals that the discipline you are building in this chapter applies far beyond software.

A recipe is an algorithm for preparing food. It specifies inputs (ingredients and quantities), a sequence of steps, decisions (cook until golden, add salt to taste), and an output (the finished dish). A well-written recipe is precise enough for anyone who knows how to cook to follow consistently.

Navigation directions are algorithms. Turn-by-turn directions accept an input (your starting location) and produce an output (your destination) through a precise sequence of conditional instructions ("at the light, if you see a gas station, turn left; otherwise continue straight"). Modern GPS systems implement these algorithms in software, but the logical structure is the same as written directions.

The rules of a board game or card game define an algorithm for play. They specify the sequence of turns, what moves are allowed, what conditions must be checked, and what constitutes winning. A well-designed game has rules precise enough that disputes about legal moves can always be resolved by checking the rulebook.

Medical protocols are algorithms. A surgical checklist or a triage procedure specifies precise steps that must be followed in order, conditions that must be assessed, and outcomes that determine the next action. The stakes of correctness in medical algorithms are unusually high, which is why healthcare has invested so heavily in making them explicit and verifiable.

In logistics and manufacturing, algorithms determine how packages are sorted, how assembly lines sequence operations, how inventory is restocked, and how delivery routes are planned. These algorithms process enormous volumes of data and require the same properties of precision, finiteness, and correctness that any algorithm requires — just at a scale where errors cost millions of dollars or affect millions of people.

Why This Matters

Recognizing algorithms in everyday life helps you understand that algorithm design is not an abstract computer science skill. It is the skill of describing any precise procedure clearly enough to follow reliably. When you learn to design algorithms for computers, you are sharpening a form of reasoning that applies everywhere precise procedures matter.

Practice 5.9Algorithms in Context
  1. Write a brief algorithm — four to seven steps — for each of the following tasks. Then trade with a classmate and follow each other's algorithm exactly. Where does the algorithm break down?

    a. Making a bowl of cereal with milk.
    b. Alphabetizing a stack of five file folders by the first letter.
    c. Calculating a 15% tip on a restaurant bill and rounding to the nearest dollar.
    d. Finding a specific song in a playlist sorted alphabetically by song title.
  2. Identify an algorithm used in a profession you find interesting (medicine, engineering, cooking, finance, sports coaching, transportation). Describe its inputs, its output, and two or three of its key steps. Where would an error in this algorithm have the most serious consequences?
  3. A streaming service recommends shows to users. Describe this process as an algorithm: what are the inputs, what is the output, and what makes this algorithm unusually difficult to specify correctly?
Section 5.10

From Algorithm to Program

Algorithms are the ideas; programs are those ideas expressed in a language a computer can execute. Every program implements some algorithm. When you write a program, you are translating an algorithm from pseudocode — or from your own mind — into a specific programming language with precise syntax rules. The algorithm is the what; the program is the how it is expressed in a particular language.

This relationship has an important implication: a single algorithm can be implemented in many different programming languages. The FindMaximum algorithm from Section 5.5 could be written in Python, JavaScript, Java, C, Swift, or any other general-purpose language. The algorithm's logic does not change. Only the language used to express it changes. This is why algorithm design is language-independent, and why the pseudocode skills you build here transfer to any programming language you learn.

The professional habit is to design a clear algorithm — in pseudocode or flowchart form — before writing any code. Once the algorithm is correct, translating it into code is relatively mechanical. Debugging incorrect code when the underlying algorithm is unclear is very difficult. The hard thinking happens during algorithm design; the code is the expression of that thinking.

A Preview: FindMaximum in Python

Chapter 6 covers programming languages in detail. Here is a preview showing how the FindMaximum pseudocode from Section 5.5 translates into Python. Notice how directly each pseudocode element maps to code.

Python — FindMaximum# FindMaximum in Python # Input: a list of numbers # Output: the largest number in the list values = [3, 7, 1, 9, 4] # Example input maximum = values[0] # SET maximum TO values[0] index = 1 # SET index TO 1 while index < len(values): # WHILE index < length(values) DO if values[index] > maximum: # IF values[index] > maximum THEN maximum = values[index] # SET maximum TO values[index] index = index + 1 # SET index TO index + 1 print(maximum) # OUTPUT maximum → prints 9

The pseudocode keyword WHILE becomes Python's while. The condition values[index] > maximum is written identically in Python. The pseudocode command OUTPUT maximum becomes print(maximum). Every element of the pseudocode has a direct translation. This is the value of pseudocode: when you write it clearly, translating to code is almost mechanical. The hard thinking — the algorithm design — has already been done.

Algorithm First, Code Second

A very common beginner mistake is to start typing code without a clear algorithm in mind. This leads to programs that are hard to understand, hard to debug, and often incorrect. Think of the algorithm as the architect's blueprint and the program as the construction. You would not begin construction without a blueprint — and you should not begin coding without an algorithm.

Practice 5.10Algorithms and Programs
  1. Explain in your own words why the same algorithm can be implemented in many different programming languages. What stays the same across all implementations?
  2. Take the ComputeLetterGrade pseudocode from Section 5.5 and describe, step by step, how each pseudocode line would correspond to a line of real code. You do not need to write Python — just describe the translation in words.
  3. A classmate says: "I do not need pseudocode. I can just figure out the algorithm while I write the code." Explain why this approach often creates problems, especially for beginners.
  4. Write pseudocode for an algorithm that inputs 5 numbers from a user one at a time and outputs their average. Then, without looking at any reference, describe in one paragraph how you would translate each pseudocode construct into a real programming language you have heard of (even if you have never used it).
Chapter 5 — Back Matter

Chapter Summary

Key Terms

algorithm
A precise, finite, step-by-step procedure that accepts inputs and produces outputs. Must work correctly for any valid input.
input
The information an algorithm receives before it begins execution. Should be specified with type, range, and constraints.
output
The information an algorithm produces when it finishes. Should be specified exactly in the algorithm's header.
sequential execution
Running algorithm steps in order, one after another, without skipping or reordering. The simplest control structure.
variable
A named storage location used to hold a value while the algorithm runs. The name labels the value; the value can change.
pseudocode
A structured, English-like notation for writing algorithms. Language-independent, readable, and focused on logic rather than syntax.
flowchart
A visual diagram representing an algorithm using standard symbols connected by arrows showing the direction of execution.
terminal
The rounded-rectangle symbol in a flowchart that marks the Start or End of the algorithm.
process box
The rectangle symbol in a flowchart representing an action or calculation step, such as setting a variable.
decision diamond
The diamond symbol in a flowchart representing a yes/no question. Always has exactly two labeled exit arrows.
tracing
Following an algorithm step by step with a specific input, recording each variable's value after each step.
trace table
A table used during tracing with columns for variables and rows for each execution step.
correctness
The property that an algorithm produces the right output for every valid input and always terminates.
partial correctness
Correctness of output if the algorithm terminates — without regard to whether it always terminates.
total correctness
Partial correctness plus guaranteed termination for all valid inputs. What a truly correct algorithm requires.
termination
The property that an algorithm always eventually stops for every valid input.
edge case
An input at the extreme boundary of valid inputs, often revealing errors that typical inputs do not expose.
boundary value
An input at the smallest or largest limit of the algorithm's valid input range.
precondition
A condition that must be true before an algorithm begins. If violated, the algorithm makes no guarantees about its output.

Concept Check

Answer each question in one or two sentences before moving to the longer exercises.

  1. What is the difference between a vague instruction and an algorithmic instruction? Give a brief example of each.
  2. What are the four defining characteristics of an algorithm?
  3. Why must an algorithm eventually terminate?
  4. What is pseudocode, and what is it used for?
  5. What does a decision diamond in a flowchart always have that no other symbol has?
  6. What does a trace table record?
  7. Why is testing one typical input not enough to establish algorithm correctness?
  8. What is the difference between partial correctness and total correctness?
  9. Why is it better to write a clear algorithm before writing code rather than thinking through the algorithm while coding?
  10. What stays the same when you implement the same algorithm in two different programming languages?
Exercise 5APseudocode Practice

Write pseudocode for each task. Begin each algorithm with a header specifying inputs and outputs. Use the conventions from Section 5.5.

  1. An algorithm that takes two numbers as input and outputs the larger of the two.
  2. An algorithm that takes a whole number as input and outputs whether it is even or odd.
  3. An algorithm that converts a temperature from Celsius to Fahrenheit. (F = C × 9/5 + 32)
  4. An algorithm that counts from 1 to 10, outputting each number.
  5. An algorithm that takes a list of five numbers and outputs their sum and their average.
  6. An algorithm that takes a list of numbers and outputs how many of them are greater than 50.
  7. An algorithm that takes a student's three test scores (weighted 30%, 30%, 40%) and outputs the weighted average and the corresponding letter grade (A ≥ 90, B ≥ 80, C ≥ 70, D ≥ 60, F otherwise).
  8. An algorithm that asks the user to input numbers one at a time until they enter 0, then outputs how many positive numbers were entered (not counting the 0).
Exercise 5BAlgorithm Tracing

Trace each algorithm using the given input. Construct a complete trace table. Then answer the follow-up question.

Trace Problem 1
Input: n = 4
SET total TO 0 SET i TO 0 WHILE i <= n DO SET total TO total + i SET i TO i + 1 END WHILE OUTPUT total

What does this algorithm compute? What would the output be for n = 10?

Trace Problem 2
Input: values = [5, 12, 3, 8]
SET count TO 0 FOR EACH num IN values DO IF num > 7 THEN SET count TO count + 1 END IF END FOR OUTPUT count

What does this algorithm count? What is the output?

Trace Problem 3
Input: a = 5, b = 3
SET temp TO a SET a TO b SET b TO temp OUTPUT a OUTPUT b

What does this algorithm accomplish? Why is the temp variable necessary?

Error Analysis

Each algorithm below contains at least one error. Identify the error, explain why it is wrong, and write a corrected version.

Error 5.1 — Step-order error
// Compute sum of numbers from 1 to 10 SET total TO 0 SET i TO 1 WHILE i < 10 DO SET total TO total + i SET i TO i + 1 END WHILE OUTPUT total

Trace carefully. What is the last value of i that gets added to total? What should the loop condition be?

Error 5.2 — Logic error in average calculation
SET total TO 0 SET count TO length(values) FOR EACH number IN values DO SET total TO total + number END FOR SET average TO count / total OUTPUT average

There are two errors here. Find both. What is the correct final expression for average?

Error 5.3 — Swap without temporary variable
// Swap the values of A and B SET A TO B SET B TO A OUTPUT A OUTPUT B

Trace this with A = 5 and B = 3. What is the actual output? Why does it fail? How do you fix it?

Error 5.4 — Incomplete conditional structure
// Classify a number as positive, negative, or zero INPUT number IF number > 0 THEN OUTPUT "Positive" IF number < 0 THEN OUTPUT "Negative" IF number = 0 THEN OUTPUT "Zero"

This runs without crashing, but it has a structural problem. What is it? How should these conditions be structured? (Hint: what if number = 5?)

Error 5.5 — Off-by-one in a loop
// Output every element of a list with 5 elements SET index TO 1 WHILE index < length(values) DO OUTPUT values[index] SET index TO index + 1 END WHILE

Assuming the list uses zero-based indexing (first element is values[0]), what element is never output? Fix the algorithm.

Exercise 5CDesign and Application

For each problem, write pseudocode, include a header, and specify at least two test cases (including one edge case).

  1. Grade calculator. A teacher wants to compute a student's weighted grade from three components: homework average (30%), midterm score (30%), and final exam score (40%). Design the algorithm.
  2. Password length checker. A website requires passwords to be at least 8 characters long. Design an algorithm that accepts a proposed password and outputs either "Accepted" or "Too short." What is the edge case?
  3. Shipping cost calculator. An online store charges: $3.99 for orders up to 1 pound; $6.99 for 1–5 pounds; $12.99 for over 5 pounds. Orders over $50 ship free regardless of weight. Design the algorithm for inputs: order weight (in pounds) and order total (in dollars). Specify your preconditions.
  4. Longest word finder. Design an algorithm that takes a list of words as input and outputs the longest word. If there is a tie, output the first one found. What edge case should you test?
  5. Number guessing game. The algorithm has a secret number (42). The user inputs guesses one at a time. After each guess, the algorithm outputs "Too high," "Too low," or "Correct!" The algorithm counts guesses and outputs the count when the user wins. Design the full algorithm.

Review Questions

Write one to three sentences for each.

  1. Explain in your own words why precision matters in algorithm design. Give a real-world example of an instruction that is too vague to be algorithmic, and explain why it fails.
  2. Why do algorithms need to be general rather than correct for only a single specific case?
  3. When would you choose a flowchart over pseudocode? When would you prefer pseudocode?
  4. A classmate says: "I tested my algorithm five times and it worked every time, so it must be correct." Explain why this reasoning is incomplete.
  5. Describe the relationship between an algorithm and a program. Can two different programs implement the same algorithm?
  6. What is a precondition? Give an example of an algorithm whose precondition should be stated explicitly.
  7. What is an off-by-one error? Why are off-by-one errors particularly easy to miss and particularly important to catch?
  8. Why is the algorithm-first habit — designing in pseudocode before writing code — especially valuable for beginners?

True or False

If false, explain what is wrong.

  1. An algorithm that never terminates can still be partially correct.
  2. Pseudocode must follow Python syntax.
  3. A decision diamond in a flowchart can have three exit paths.
  4. Tracing an algorithm means running it on a computer and reading the output.
  5. The order of steps in a sequential algorithm does not matter as long as all steps are present.
  6. If an algorithm's preconditions are violated, it is not required to produce correct output.
  7. Every program implements some algorithm.
  8. A correct algorithm is one that works for every input without any preconditions.

Mixed Review

These questions connect Chapter 5 to earlier chapters.

  1. Chapter 3 connection. Section 3.2 covered decomposition. Choose a complex task — planning a school event, building a small website, organizing a collection. Decompose it into subproblems, then specify the input and output of each subproblem's algorithm.
  2. Chapter 4 connection. Chapter 4 showed that text is represented using numeric codes. Describe an algorithm that takes a single character as input and outputs whether it is an uppercase letter, a lowercase letter, a digit, or something else. What information about character encoding does the algorithm need?
  3. Chapter 2 connection. Chapter 2 introduced the input–process–output model of computation. How does that model relate to what you have learned about algorithms in this chapter?
  4. General. Two algorithms both produce the correct output for every valid input and always terminate. In what other ways might one algorithm still be better than the other? (You will study this in depth in Chapter 12.)
  5. General. A student writes an algorithm for finding a word in a dictionary by starting at the first entry and checking each word in order. A classmate's algorithm opens the dictionary to the middle and decides whether to look in the left or right half. Without doing any calculations, explain in general terms why the second approach is likely faster for large dictionaries.

Chapter 5 Checkpoint

Chapter 5 Checkpoint
Complete without assistance — covers all key skills and concepts from Chapter 5
Section 1 — Vocabulary and Concepts
  1. Define algorithm in your own words and state its four defining characteristics.
  2. What is a trace table, and what is it used for?
  3. Explain the difference between partial correctness and total correctness.
  4. What is a precondition? Give one example.
Section 2 — Pseudocode Writing
  1. Write pseudocode for an algorithm that inputs a positive number n and outputs the sum of all integers from 1 to n inclusive.
  2. Write pseudocode for an algorithm that inputs a list of numbers and outputs the count of numbers that are negative.
  3. Write pseudocode for an algorithm that inputs a temperature in Fahrenheit and outputs whether it is "Freezing" (below 32°F), "Cold" (32–60°F), "Warm" (61–85°F), or "Hot" (above 85°F).
Section 3 — Tracing
  1. Trace the following algorithm with input values = [6, 2, 9, 1, 7]. Show the complete trace table and state the output. SET max TO values[0] SET index TO 1 WHILE index < length(values) DO IF values[index] > max THEN SET max TO values[index] END IF SET index TO index + 1 END WHILE OUTPUT max
  2. Trace the temperature classifier from problem 7 with inputs (a) 28, (b) 45, (c) 72, (d) 100. Show the trace for each.
Section 4 — Error Analysis
  1. Identify the error in this algorithm and write a correction: SET total TO 0 SET average TO total / length(values) FOR EACH num IN values DO SET total TO total + num END FOR OUTPUT average
  2. A student tests their sorting algorithm on [3, 1, 2] and gets [1, 2, 3]. They declare it correct. Name two additional inputs you would test before accepting this conclusion, and explain why each is important.
Section 5 — Design
  1. A library charges late fees: 25 cents per day for the first 7 days overdue, and 50 cents per day after that. Write a complete pseudocode algorithm (with header) that inputs the number of days overdue and outputs the total late fee.
Looking Ahead
Chapter 6: Programming Languages and Code

Chapter 5 gave you the ability to design algorithms precisely — in pseudocode and flowcharts — and to verify their correctness through tracing. Chapter 6 takes the next step: expressing algorithms in programming languages that computers can actually execute. You will learn what source code is, why programming languages have strict syntax rules, how interpreters and compilers translate human-readable code into machine instructions, what happens when those rules are broken, and how to read the error messages that result. Every pseudocode construct you practiced in this chapter has a direct counterpart in Python. By the end of Chapter 6, you will be reading and writing small, real programs — not just algorithms on paper.

MGU Library Connection
  • Pseudocode and Flowchart Reference — Appendix C of this textbook
  • Python-Style Code Reference — Appendix D of this textbook
  • Debugging and Testing Reference — Appendix E of this textbook
  • Data Structures and Algorithms Reference — Appendix F of this textbook
  • Computer Science Foundations, Chapter 3: Problem Solving and Computational Thinking
  • Computer Science Foundations, Chapter 12: Searching, Sorting, and Efficiency
  • MGU Computer Science Series: Python Programming Foundations — Chapter 1
  • MGU Dictionary entries: algorithm, pseudocode, flowchart, variable, trace table, correctness, precondition