An algorithm is a step-by-step procedure for solving a problem or accomplishing a task. Understanding how to write and follow algorithms is fundamental to programming.
Definition
An algorithm is a finite sequence of well-defined, computer-implementable instructions to solve a class of problems or perform a computation.
Key Point
Algorithm Characteristics:
• Finite - Must terminate after a finite number of steps
• Definite - Each step must be precisely defined
• Input - Zero or more inputs
• Output - One or more outputs
• Effective - Operations must be basic enough to be carried out exactly
• Finite - Must terminate after a finite number of steps
• Definite - Each step must be precisely defined
• Input - Zero or more inputs
• Output - One or more outputs
• Effective - Operations must be basic enough to be carried out exactly
Representing Algorithms
Algorithms can be expressed in several ways before being coded:
Key Point
Pseudocode - Structured English-like language for describing algorithms
• Easy to write and understand
• Language-independent
• Focuses on logic, not syntax
Flowcharts - Visual representation using standard symbols
• Diamond = decision
• Rectangle = process
• Oval = start/end
• Arrow = flow direction
Structured English - Simple English statements using indentation
• Easy to write and understand
• Language-independent
• Focuses on logic, not syntax
Flowcharts - Visual representation using standard symbols
• Diamond = decision
• Rectangle = process
• Oval = start/end
• Arrow = flow direction
Structured English - Simple English statements using indentation
Exam Tip
Algorithm Tracing Tips:
• Create a table with columns for each variable
• Work through step-by-step, updating values
• Be careful with loop conditions - check before entering
• Watch for off-by-one errors in array indexing
• If stuck, use small, simple test data
• Verify your trace makes logical sense
• Create a table with columns for each variable
• Work through step-by-step, updating values
• Be careful with loop conditions - check before entering
• Watch for off-by-one errors in array indexing
• If stuck, use small, simple test data
• Verify your trace makes logical sense
Tracing an Algorithm
Following an algorithm means working through it by hand, one line at a time, as the computer would. This is called a dry run. A trace table records the value of every variable each time it changes, together with any output.
Worked Example
Worked Example: Trace Table
After the fifth pass x is 1, so the condition x > 1 is false and the loop ends.
Output: 5
pseudocode
x = 13
count = 0
while x > 1
if x MOD 2 == 0 then
x = x / 2
else
x = x - 1
endif
count = count + 1
endwhile
print(count)
| Pass of the loop | Is x even? | x | count |
|---|---|---|---|
| Before the loop | 13 | 0 | |
| 1 | No | 12 | 1 |
| 2 | Yes | 6 | 2 |
| 3 | Yes | 3 | 3 |
| 4 | No | 2 | 4 |
| 5 | Yes | 1 | 5 |
Output: 5
Key Point
Writing an algorithm:
• Decide what the inputs and outputs are before writing any steps
• Build the steps from sequence, selection and iteration
• Use meaningful identifiers and indent the lines inside loops and selection statements
• Dry run the finished algorithm with test data, including values at the boundaries of each condition
• Decide what the inputs and outputs are before writing any steps
• Build the steps from sequence, selection and iteration
• Use meaningful identifiers and indent the lines inside loops and selection statements
• Dry run the finished algorithm with test data, including values at the boundaries of each condition