Learning Objectives
By the end of this lesson, you will be able to:
- Show understanding that an algorithm is a solution to a problem expressed as a sequence of steps
- Use suitable identifier names for representation of data used by a problem and represent these using an identifier table
- Write pseudocode that contains input, process and output
- Write pseudocode using three basic constructs of sequence, selection and iteration
- Document simple algorithms using pseudocode
- Write pseudocode from structured English descriptions and flowcharts
- Describe and use the process of stepwise refinement to express an algorithm to a level of detail from which a task may be programmed
- Use logic statements to define parts of an algorithm solution
Key Terms
Algorithm
A sequence of steps that can be carried out to perform a task
Pseudocode
Resembles a programming language without following the syntax of a particular programming language
Structured English
A subset of English language consisting of command statements
Flowchart
Graphical representation of an algorithm using specific shapes linked together
Identifier
A unique name given to a variable, constant, array, procedure or function
Variable
A memory location which temporarily stores data that can change while the program is running
Constant
A memory location which temporarily stores data that remains the same throughout execution of a program
Array
A data structure that can store a fixed-size collection of elements of the same type
Stepwise Refinement
Breaking a complex problem down into smaller steps until they are small enough to solve easily
Sequence
When programming statements are executed one after the other in the order they appear
Selection
A control structure where a test decides if certain instructions are executed
Iteration
A control structure where a group of statements is executed repeatedly (also called repetition or looping)
Local Variable
A variable that is accessible only within the module in which it is declared
Global Variable
A variable that is accessible from all modules
Transferable Skill
Knowledge or experience of one programming language that can be applied to another unfamiliar language
Understanding Algorithms
An algorithm is a sequence of steps that can be carried out to perform a task. Many problems have more than one solution, and sometimes one solution will be better than another.
For Slow Learners: Think of Algorithms Like Recipes
Just like a recipe tells you step-by-step how to bake a cake, an algorithm tells a computer step-by-step how to solve a problem. Good recipes (and good algorithms) are:
- Correct: They give the right result (a tasty cake!)
- Efficient: They don't waste ingredients or time
- Easy to follow: Clear steps that anyone can understand
- Concise: No unnecessary steps
Expressing Algorithms
Four Ways to Express Algorithms
1. Structured English
Subset of English language consisting of command statements
2. Pseudocode
Resembles a programming language without following specific syntax
3. Flowchart
Graphical representation using specific shapes linked together
4. Programming Statement
Resembles pseudocode but follows particular programming language syntax
Algorithm Basic Constructs
Assignment
Instruction that places a value into a specified variable or constant
Sequence
Statements executed one after another in order of appearance
Selection
Control structure with a test to decide if instructions are executed
Repetition (Iteration)
Group of statements executed repeatedly (looping)
Algorithm Flow Visualizer
Visualize how different algorithm constructs work together to solve a problem:
How it works: This shows the basic Input → Process → Output model. Real algorithms often include selection (IF statements) and repetition (loops) within the process stage.
Real-Life Example: Online Food Delivery App
When you order food online, the app follows an algorithm:
This algorithm has multiple solutions (different apps solve it differently), but good solutions are correct, efficient, and user-friendly.
Activity 1: Identify Algorithm Steps
For each scenario below, identify the algorithm steps in order:
- Making a cup of tea
- Withdrawing money from an ATM
- Posting a photo on social media
- Finding the average of three test scores
- Deciding what to wear based on the weather
Solution:
- Making tea: 1. Boil water, 2. Put tea bag in cup, 3. Pour hot water, 4. Wait 3 minutes, 5. Remove tea bag, 6. Add milk/sugar, 7. Stir, 8. Drink
- ATM withdrawal: 1. Insert card, 2. Enter PIN, 3. Select "Withdrawal", 4. Enter amount, 5. Take cash, 6. Take receipt, 7. Take card
- Posting photo: 1. Open app, 2. Click "New Post", 3. Select photo, 4. Add filter/edit, 5. Write caption, 6. Add hashtags, 7. Choose audience, 8. Click "Post"
- Average score: 1. Get score1, score2, score3, 2. Add scores together, 3. Divide sum by 3, 4. Display result
- Weather clothing: 1. Check weather, 2. IF raining THEN take umbrella, 3. IF cold THEN wear jacket, 4. IF sunny THEN wear sunglasses, 5. Get dressed
Check Your Understanding: Algorithms
1. What is an algorithm? [2 marks]
Answer
- [1 mark] A sequence of steps that can be carried out to perform a task
- [1 mark] A solution to a problem expressed as a sequence of steps
- [Additional] Many problems have more than one algorithm (solution)
2. Name three ways to express an algorithm. [3 marks]
Answer
- [1 mark] Structured English
- [1 mark] Pseudocode
- [1 mark] Flowchart
- [Additional] Programming Statement (fourth way)
3. What makes a "good" algorithm solution? [3 marks]
Answer
- [1 mark] Gives correct results
- [1 mark] Takes up little computer memory
- [1 mark] Executes as fast as possible
- [Additional] Should be concise, elegant and easy to understand
4. What are the three basic algorithm constructs? [3 marks]
Answer
- [1 mark] Sequence
- [1 mark] Selection
- [1 mark] Iteration (Repetition)
- [Additional] Assignment is also a basic construct (fourth one)
5. Explain what "transferable skill" means in programming. [2 marks]
Answer
- [1 mark] Knowledge or experience of one programming language can be applied to another
- [1 mark] Helps recognize control structures of unknown languages and learn new computer languages
- [Additional] Example: Understanding pseudocode helps learn Python, Java, or C++
Data Storage and Pseudocode
Algorithms involve inputting data, processing data, and outputting results. To store and manipulate data, we use variables, constants, and arrays, which need appropriate identifiers.
Data Storage Elements
Variables and Constants
Variable
Memory location that temporarily stores data that can change
DECLARE Average : REAL
Constant
Memory location that temporarily stores data that remains the same
CONSTANT BookTitle ← "CS MADE EASY"
Variables can change value during program execution, constants cannot change.
Identifiers and Arrays
What is an Identifier?
Variables, constants, arrays, procedures and functions names
Identifier Rules
- No spaces in a name
- Not a keyword of programming language
- Name should be relevant
- Start with an alphabet (not a number)
Array
Data structure that can store a fixed-size collection of elements of same type
Valid: First_Name, PostCode, AverageHeight, Sum
Invalid: 15um (starts with digit), First Name (space), Total% (% not allowed)
Identifier Table Builder
Build an identifier table for this problem: "Convert a distance in miles into km and output the equivalent distance in km."
| Identifier | Explanation | Data Type | Valid? |
|---|---|---|---|
| ✓ | |||
| ✓ | |||
| - |
Identifier Table Purpose: Helps while designing an algorithm. Contains list of identifiers, explanations, and data types. Ensures consistent naming and understanding of data elements.
Assignment Operator and Value Swapping
Assignment Operator (←)
Values are assigned to constants, arrays and variables using the ← operator. Variable on left of ← is assigned value of expression on right.
// Assigns value 10 to variable Cost
// Updates Cost by adding 2 (Cost becomes 12)
// Copies value from Cost to Price
Swapping Two Values
To swap contents of two variables, we need to store one value in a temporary variable. Otherwise the second value will be overwritten.
Pseudocode Examples
Example 1: Miles to Kilometers
This follows the Input → Process → Output model: INPUT miles, PROCESS (convert to km), OUTPUT result.
Example 2: Sum of Two Numbers
Uses multiple variables and shows sequence construct (steps executed in order).
Activity 2: Pseudocode Writing
Write pseudocode for the following problems:
- Take marks of physics, chemistry and math as input, calculate the average and display output
- Take two numbers from user and swap their values
- Take two numbers as input, calculate both product and sum, and display both results
- Create an identifier table for problem 1 above
Solution:
1. Average Marks Pseudocode:
2. Swap Values Pseudocode:
4. Identifier Table for Average Marks:
| Identifier | Explanation | Data Type |
|---|---|---|
| Phy_marks | Marks obtained in physics | Integer |
| Chem_marks | Marks obtained in chemistry | Integer |
| Math_marks | Marks obtained in mathematics | Integer |
| average | Average of three subjects | Real |
Check Your Understanding: Data and Pseudocode
1. What is the difference between a variable and a constant? [2 marks]
Answer
- [1 mark] Variable: Memory location that temporarily stores data that can change while program runs
- [1 mark] Constant: Memory location that temporarily stores data that remains same throughout execution
- [Additional] Use of constant helps prevent accidental changes when writing program
2. List three rules for naming identifiers. [3 marks]
Answer
- [1 mark] No spaces in a name
- [1 mark] Name should not be a keyword of programming or pseudocode
- [1 mark] Name should start with an alphabet (not a number)
- [Additional] Name should be relevant; Only letters, digits and underscore allowed
3. Why do we need a temporary variable when swapping two values? [2 marks]
Answer
- [1 mark] To store one of the values temporarily
- [1 mark] Otherwise the second value to be moved will be overwritten by the first value
- [Additional] Example: Temp ← Value1, Value1 ← Value2, Value2 ← Temp
4. What is the purpose of an identifier table? [2 marks]
Answer
- [1 mark] Designed while designing an algorithm to list all identifiers
- [1 mark] Contains list of identifiers, explanations/descriptions, and data types
- [Additional] Helps ensure consistent naming and understanding of data elements
5. Write the pseudocode statement to declare a constant named PI with value 3.14159. [1 mark]
Answer
Logic Statements and Stepwise Refinement
Selection constructs use conditions to decide which steps to execute. Complex problems are solved by breaking them down into smaller steps through stepwise refinement.
Logic Statements and Selection
Relational (Comparison) Operators
Selection constructs use conditions with relational operators:
| Operator | Comparison |
|---|---|
| = | Is equal to |
| < | Is less than |
| > | Is greater than |
| <= | Is less than or equal to |
| >= | Is greater than or equal to |
| <> | Is not equal to |
Selection Methods
IF Then Else EndIf
Used if there are two possible outcomes to a test
OUTPUT "Child"
ELSE
OUTPUT "Not a child"
ENDIF
SELECT-CASE EndCase
Used if there are more than two possible outcomes to a test
Logic Statement Evaluator
Person is classed as child if under 13, adult if over 19, teenager if between 13 and 19 inclusive. Evaluate these logic statements:
How it works: The selection construct tests conditions in order. Only one condition will be true for any given age. Conditions use relational operators (<, >, >=, <=) and logical operators (AND).
Stepwise Refinement
Important: Solving Complex Problems
Many problems we want to solve are complex. To make it easier to solve a complex problem, we break it down into smaller steps. These might need breaking down further until the steps are small enough to solve easily.
What is Stepwise Refinement?
Stepwise refinement is the process of breaking down a complex problem into smaller, more manageable steps. Each step can be refined further until it's simple enough to code directly.
Stepwise Refinement Visualizer
Problem: "Calculate final grade for a student based on test scores and attendance"
Key Insight: Stepwise refinement turns a complex problem into a series of simple steps that can be easily programmed. Each level adds more detail until the steps are specific enough to code.
Variable Scope: Local vs Global
Local Variable
A variable that is accessible only within the module in which it is declared.
Advantage: Makes modules independent and re-usable. Other modules cannot accidentally change these variables.
Global Variable
A variable that is accessible from all modules.
Use with caution: Global variables can be changed by any part of the program, which can lead to bugs.
Good Programming Practices
Features that make pseudocode or program easier to read and understand:
Meaningful identifier names
Use names that describe the purpose (e.g., studentCount instead of sc)
Camel case fonts
firstName, totalScore, averageHeight (first word lowercase, subsequent words capitalized)
Capitalization of keywords
IF, THEN, ELSE, ENDIF, DECLARE, CONSTANT
Use of functions
Library/built-in functions for common tasks
Use of constants
Prevents accidental changes to fixed values
Use of indentation
Shows structure and nesting of code blocks
Blank lines and white space
Separate logical sections for readability
Add comments
Explain purpose of code sections (preceded by // in pseudocode)
Activity 3: Stepwise Refinement Practice
Apply stepwise refinement to these problems:
- Problem: "Make a sandwich"
- Break into 3-4 main steps
- Refine one of those steps into 3-4 more detailed steps
- Problem: "Calculate electricity bill"
- Break into main steps (Input, Process, Output)
- Refine the Process step into detailed calculations
- Write pseudocode for a program that classifies a person as child, teenager, or adult based on age
- Identify whether these should be local or global variables:
- A counter in a loop that calculates sum of numbers
- A constant for VAT rate used throughout a shopping program
- A temporary variable to swap two values
- A student's name in a grade calculation program
Solution:
1. Make a Sandwich (Stepwise Refinement):
3. Age Classification Pseudocode:
4. Variable Scope Identification:
- Loop counter: Local (only needed within the loop calculation)
- VAT rate constant: Global (used throughout shopping program)
- Swap temporary variable: Local (only needed within swap operation)
- Student's name: Depends on design. If used in multiple procedures, could be global; if only in one procedure, should be local.
Check Your Understanding: Logic and Refinement
1. What is stepwise refinement? [2 marks]
Answer
- [1 mark] Breaking a complex problem down into smaller steps
- [1 mark] These might need breaking down further until steps are small enough to solve easily
- [Additional] Process continues until steps are at a level of detail from which task may be programmed
2. When would you use SELECT-CASE instead of IF-THEN-ELSE? [2 marks]
Answer
- [1 mark] When there are more than two possible outcomes to a test
- [1 mark] When checking a single variable against multiple specific values
- [Additional] Example: Menu selection (1 for option A, 2 for option B, 3 for option C)
3. What is the difference between local and global variables? [3 marks]
Answer
- [1 mark] Local variable: Accessible only within the module in which it is declared
- [1 mark] Global variable: Accessible from all modules
- [1 mark] Good design uses local variables as it makes modules independent and re-usable
4. What is the purpose of adding comments in pseudocode? [2 marks]
Answer
- [1 mark] To improve readability of the pseudocode or program
- [1 mark] Help programmer in understanding the code (comments are not executed)
- [Additional] Comments are preceded by // in pseudocode and are not compiled/translated
5. List four good programming practices. [4 marks]
Answer
- [1 mark] Meaningful or sensible identifier names
- [1 mark] Use of Camel case fonts for identifier names
- [1 mark] Capitalization of keywords
- [1 mark] Use of indentation
- [Additional] Also: Use of functions, constants, blank lines, comments
Key Takeaways
- An algorithm is a sequence of steps to perform a task, expressed in structured English, pseudocode, flowcharts, or programming statements
- Good algorithms are correct, efficient, concise, elegant, and easy to understand
- The three basic algorithm constructs are sequence, selection, and iteration (plus assignment)
- Algorithms follow the Input → Process → Output model
- Variables store data that can change; constants store data that remains the same
- Identifiers are unique names for variables, constants, arrays, procedures and functions
- Identifier rules: no spaces, not a keyword, relevant, start with alphabet
- An identifier table lists identifiers with explanations and data types
- The assignment operator (←) places values into variables/constants
- To swap two values, use a temporary variable to avoid overwriting
- Pseudocode resembles programming language without specific syntax
- Selection uses conditions with relational operators (=, <, >, <=, >=, <>)
- IF-THEN-ELSE for two outcomes; SELECT-CASE for multiple outcomes
- Stepwise refinement breaks complex problems into smaller steps until easily solvable
- Local variables are accessible only within their module; global variables are accessible everywhere
- Good programming practices include meaningful names, camel case, indentation, comments, and use of constants
- Transferable skills from one programming language help learn new languages
Question Bank
1. Explain the three basic algorithm constructs with examples. [6 marks]
Marking Scheme & Answer
- [2 marks] Sequence: Statements executed one after another in order. Example: INPUT num1, num2; sum ← num1 + num2; OUTPUT sum
- [2 marks] Selection: Control structure with test to decide if instructions execute. Example: IF age < 13 THEN OUTPUT "Child" ELSE OUTPUT "Not child" ENDIF
- [2 marks] Iteration (Repetition): Group of statements executed repeatedly. Example: FOR count ← 1 TO 5 OUTPUT count ENDFOR
- [Additional] Assignment is also a basic construct: placing values into variables using ← operator
2. Create an identifier table and write pseudocode to convert temperature from Celsius to Fahrenheit. [5 marks]
Marking Scheme & Answer
Identifier Table:
| Identifier | Explanation | Data Type |
|---|---|---|
| Celsius | Temperature in degrees Celsius | Real |
| Fahrenheit | Converted temperature in degrees Fahrenheit | Real |
Pseudocode:
3. Explain stepwise refinement using the problem "Bake a cake". Show three levels of refinement. [6 marks]
Marking Scheme & Answer
Stepwise refinement is breaking a complex problem into smaller steps until they are small enough to solve easily.
Each level adds more detail. Level 3 steps are specific enough to follow directly.
4. Write pseudocode to swap the values of two variables without using a third variable. [4 marks]
Marking Scheme & Answer
Alternative using XOR: a ← a XOR b; b ← a XOR b; a ← a XOR b
Note: The standard method uses a temporary variable (Temp ← a; a ← b; b ← Temp), which is clearer and works for all data types.
5. For a library system, identify which variables should be local and which should be global. Justify your choices. [5 marks]
Marking Scheme & Answer
- [1 mark] Global: totalBooks (needed by multiple procedures - issue, return, search)
- [1 mark] Global: libraryName (constant used throughout system)
- [1 mark] Local: daysOverdue in calculateFine procedure (only needed for fine calculation)
- [1 mark] Local: searchTerm in searchBooks procedure (only needed during search operation)
- [1 mark] Local: tempCounter in a loop that displays books (only needed within display function)
Justification: Good design uses local variables where possible to make modules independent and re-usable. Global variables should only be used for data that truly needs to be shared across multiple modules.
6. Write pseudocode that classifies a student's grade based on marks: A for 90+, B for 80-89, C for 70-79, D for 60-69, F below 60. [5 marks]
Marking Scheme & Answer
Alternative using SELECT-CASE: Could use SELECT-CASE with ranges if pseudocode supports it. IF-ELSEIF is more standard for CIE pseudocode.
7. Explain why "transferable skill" is important for computer scientists. [3 marks]
Marking Scheme & Answer
- [1 mark] Knowledge or experience of one programming language can be applied to another unfamiliar language
- [1 mark] Helps recognize control structures of unknown languages (IF statements, loops, etc. work similarly in most languages)
- [1 mark] Makes learning new computer languages faster and easier
- [Additional] Example: Understanding pseudocode helps learn Python, Java, C++, etc. because algorithmic thinking is the same
8. Identify which of these are valid identifiers and explain why invalid ones are wrong: [4 marks]
15um, First_Name, Total%, Average Height, Num1, IF
Marking Scheme & Answer
- [1 mark] 15um: Invalid - starts with a digit (must start with alphabet)
- [1 mark] First_Name: Valid - uses underscore, starts with letter, meaningful
- [1 mark] Total%: Invalid - % symbol not allowed (only letters, digits, underscore)
- [1 mark] Average Height: Invalid - contains space (no spaces allowed)
- [Additional] Num1: Valid - starts with letter, contains digit
IF: Invalid (usually) - IF is a keyword in most programming languages
9. Write pseudocode for a simple calculator that adds, subtracts, multiplies, or divides two numbers based on user choice. [6 marks]
Marking Scheme & Answer
Uses SELECT-CASE for multiple outcomes, includes error handling for division by zero, and follows good practices with clear variable names.
10. Describe the characteristics of a "good" algorithm solution. [4 marks]
Marking Scheme & Answer
- [1 mark] Gives correct results - solves the problem accurately
- [1 mark] Takes up little computer memory - efficient use of storage
- [1 mark] Executes as fast as possible - minimal processing time
- [1 mark] Concise, elegant and easy to understand - well-structured and readable
- [Additional] Many problems have more than one solution; sometimes one solution will be better than another based on these criteria