UPI Study › Courses › C++ Programming › Free lessons › Lesson 1.5 Free with a free account
Sequential Problem-Solving
C++ Programming · Chapter 1: Foundations of ProgrammingSection 1.5 · lesson 5 of 84video coming soon
← Sketching the Logic FirstNext lesson: The Build-Run-Fix Workflow →
In this lesson
Constructing reliable algorithms.
- Test a sequence against the four properties of an algorithm
- Build a straight-line sequence from a data plan
- Desk-check it with a trace table
- Compare two correct sequences on stated grounds
Transcript
Everything said in the video, section by section (1,400 words). Read along, or search it.
Opening Contrast
Two Sets of Directions
Here are two sets of directions to the same building. The first: head toward the market, and when you see the tall place, turn. The second: walk 300 meters north along Mill Road, turn right at the traffic signal, and the entrance is 40 meters on your left. Both were written by someone who knows the way. Only the second can be followed by someone who doesn't.
Definition
What an Algorithm Is
An algorithm is a finite sequence of unambiguous, carry-out-able steps, that takes some input, and always finishes, producing the intended output. Every word in that sentence rules out a specific way of getting it wrong. And it matters, because a machine supplies no judgment. Given a vague instruction, it refuses it. Or, much worse, it picks one reading, and carries it out perfectly, at speed, on all your data.
Four Properties
Four Gates a Candidate Must Pass
Four properties separate an algorithm from a set of notes about how something might be done. Think of them as four gates a candidate must pass. Definite: every step has exactly one possible meaning. Add a reasonable delivery charge fails, because two people would produce two different numbers. Effective: every step can actually be carried out, with a limited amount of work. Write one third exactly as a decimal is clear, and impossible, because the digits never end. Finite: the written sequence has a limited number of steps. A price table with one step for every possible weight fails. One step that multiplies weight by rate passes. And terminating: carrying the steps out reaches an end, for every input it's meant to accept. Failing any one gate is enough.
Key Distinction
Finite Writing Versus Terminating Doing
Finite and terminating sound alike, but they're not the same thing. Finiteness is a property of the writing: how many steps are on the page. Termination is a property of the doing: whether following them ever stops. The instruction on a shampoo bottle, lather, rinse, repeat, is three words long, thoroughly finite, and it never tells you to stop. Every sequence in this lesson performs each step exactly once, so termination comes free. That stops being automatic later, which is why the two are named separately. Two more properties are easy. An algorithm has zero or more inputs, and at least one output. One that produces nothing has done nothing observable.
Core Concept
Straight-Line Sequences and Five Moves
A straight-line sequence performs every step exactly once, in written order, with nothing skipped and nothing revisited. Reading it top to bottom is carrying it out. Two ideas make it work. A value must be named before anything can refer to it. And a step may only mention names that are already filled. To build one, use five moves, in the same order every time. Name what you're given. Name what must be produced. Name the intermediates, the values needed on the way. Order the steps by dependency. And write one action per step. If a step contains and, it's two steps.
Worked Example
Building a Parcel Charge Data Plan
Here's a worked example: a parcel charge. The rule: a base of 40 rupees, plus 12 for every kilogram and 3 for every kilometer, then 5 percent tax on the whole thing. The first three moves produce a data plan: every name, where its value comes from, and who needs it. Weight and distance are given. Weight charge is weight times 12, and distance charge is distance times 3. The subtotal is 40 plus both charges. Tax is the subtotal times 0.05, and the total is subtotal plus tax, which is reported. Every name has exactly one origin, and nothing appears that's never used.
Worked Example
Writing and Gate-Checking Sequence A
Move four is now trivial: read downward, because each row only refers to names above it. Move five gives the sequence. Input weight, input distance, then compute the weight charge, the distance charge, the subtotal, the tax and the total, and output the total. Check it against the four gates. Every step names its numbers, so it's definite. Each is one multiplication or addition, so it's effective. Ten lines, so it's finite. And each line runs once, so it terminates. So it's an algorithm. But that's not the same as saying it's right. That question is settled next.
Technique
Desk Checking With a Trace Table
Desk checking means taking a sequence and chosen inputs, carrying out the steps yourself on paper, and recording every value as it changes. It answers a question no amount of re-reading can: not, does this look right, but, what does this actually produce? The tool is a trace table: one row per step, and one column per name. On each row, change only what that step changes, and copy everything else down.
Hands-On Trace
Tracing a 2 Kilogram Parcel
Trace a 2-kilogram parcel over 50 kilometers. The weight charge is 24, and the distance charge is 150. The subtotal is 40 plus 24 plus 150, which is 214. Tax is 10.70, and the total is 224.70. Work through it yourself, rather than reading the numbers. That's the only way the technique becomes usable.
Edge Cases
Why Awkward Inputs Reveal the Most
One ordinary case only tells you the sequence works on the case you had in mind, which you already believed. The valuable runs are the awkward ones: the smallest permitted values, zero, and cases you can work out independently. Try weight zero and distance zero. The subtotal is 40, the tax is 2, and the total is 42. The steps are faithful to the rule. Yet the trace has surfaced something: a parcel of no weight, traveling no distance, costs 42 rupees. Maybe that's intended, since the base covers handling. Maybe nobody considered it. Either way, the question came up on paper, in a minute, not as a complaint later. So desk checking finds two kinds of problem: steps that don't do what you intended, and intentions that were never fully decided.
Misordered Step
A Moved Line Leaves a Dash
Now move one line. In this version, the subtotal is computed right after the weight charge, before the distance charge exists. Trace it, and at the subtotal row, the distance charge cell is still a dash. There's literally nothing to write. A trace makes, used before it was set, impossible to overlook. Without one, the fault shows up much later, as a total 150 too small, and every one of the ten lines is a suspect.
Fault Signatures
Spotting Order and Operation Errors
Here are the faults a hand trace exposes, with the signature each leaves in the table. Used before set leaves a needed cell as a dash. A wrong order shows a value computed from an earlier version of another. And a wrong operation makes one row disagree with the hand answer.
Common Mistake
Overwrites, Rounding, and Tracing Intent
An overwritten name shows a column changing twice, when the first value was still needed. Rounding too early shows values drifting from the hand calculation in the last decimal. And a missing output leaves the output column empty. One warning: the common failure is tracing what you meant, rather than what you wrote. Read each step as if you'd never seen it, and write down what the words say.
Quick Check
Predicting the Second Sequence's Total
Here's a second sequence for the same rule. It computes the subtotal in one line, and the total as subtotal times 1.05. Quick check: with 2 kilograms over 50 kilometers, what total does it give? Pause, and predict. The same 224.70: 214 times 1.05. Fewer lines, and fewer names.
Comparison
Choosing Between Sequence A and B
Neither is better in the abstract. On length, B wins: 7 lines and 3 names, not 10 and 5. But on checking midway, A wins: the tax is a visible value you can compare against a receipt. On clarity, A wins too. Each line matches one clause of the rule, while 1.05 hides two ideas in one number. And if the tax rate changes, A needs one obvious line, not the realization that 1.05 means 5 percent. So A suits a bill with tax itemized, and B suits an internal figure nobody will ask about. What isn't defensible is choosing without a reason, or assuming shorter means better.
Key Takeaways
Gates, Data Plans, Traces, and Trade-offs
To summarize. An algorithm must be definite, effective, finite and terminating. Finite is about the writing, and terminating is about the doing. Build straight-line sequences from a data plan: givens, output, intermediates, then order by dependency, one action per step. Desk-check with a trace table, using an ordinary case, an awkward case, and an answer you worked out independently. And when two sequences are both correct, choose on grounds you can state: clarity, checkability, and the cost of change.
Think About It
Choosing Test Inputs for Temperature Conversion
Here's something to think about. You're given a sequence that converts Celsius to Fahrenheit. Which two input values would you choose for desk checking, and why those two in particular?
About C++ Programming at UPI Study
C++ Programming (Computer Science 242) is a self-paced online course of 84 video lessons in 11 chapters, from your first program to decisions, loops, arrays, functions, classes, files, pointers and inheritance. It carries a NCCRS credit recommendation for 3 semester credits.
Every lesson transcript is free on pages like this one, and the videos are free with a free UPI Study account. Enrolling adds a practice quiz after each lesson, the graded work and final exam that earn the credit, lifetime access, and an official transcript on completion. UPI Study has helped over 130,000 students with college credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.
Enroll now → Course details Download the syllabus Every course with PRO →
Why take it here
Why students take C++ Programming with UPI Study
Where the credit goes
Universities that work with NCCRS
C++ Programming carries a NCCRS credit recommendation. These universities work with NCCRS; some are UPI Study's signed partners. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.
Thomas Edison State UniversitySigned partner
University of the PeopleSigned partner
Charter Oak State CollegeSigned partner
Strayer UniversitySigned partner
Columbia Southern UniversitySigned partner
Indiana TechSigned partner
Penn StateWorks with NCCRS
Southern New Hampshire UniversityWorks with NCCRS
SUNYWorks with NCCRS
+many more cooperating universitiesFind my college →Find my college → Not listed? Ask Athena in the corner of this page, or book a 15-minute call.
FAQ
Questions students ask us
About Sequential Problem-Solving
What are the four properties of an algorithm?
What is the difference between finite and terminating in an algorithm?
How do you build a straight-line sequence from a data plan?
How do you desk-check a sequence with a trace table?
About the C++ Programming course
How many college credits is C++ Programming?
How much does C++ Programming cost and what is included?
Which universities accept UPI Study credits?
How long does C++ Programming take?
How are the exams done?
How do my credits reach my college?
Ready for the full course? Earn 3 credits in C++ Programming.
84 video lessons, a quiz after each one, and the graded work that earns the credit. Recommended for credit by NCCRS.
3 credits · NCCRSEnroll →