Algorithms Revision Notes

What is Fitness for Purpose?

Fitness for purpose means the algorithm does exactly what it is required to do, solving the given problem as intended. This includes producing accurate results, handling typical and edge-case inputs, and being robust to unexpected or incorrect values so it doesn't crash or become unreliable.

Efficiency: Comparing Time and Memory Usage

Evaluating efficiency involves measuring how many key operations the algorithm performs, such as comparisons or passes through a loop, and how much memory it uses. An efficient algorithm completes tasks with fewer operations and/or less memory, especially as input sizes get larger, which is important for performance.

Why Algorithms and Data Structures are Essential

Algorithms provide the logical sequence for problem-solving in computing. Without them, programs would not know how to process information or perform tasks. Coupled with appropriate data structures, they allow for efficient storage, retrieval, and manipulation of data, which is key for developing effective software. This skill is critical for debugging, optimisation, and creating scalable solutions.

Variables, Constants, and Data Structures

Variables are named storage locations that can hold data that changes during program execution, like user input. Constants are similar but hold data that remains fixed throughout the program, such as mathematical constants (e.g., PI) or fixed limits. Data structures organise related pieces of data. One-dimensional arrays store items in a linear sequence, accessed by a single index. Two-dimensional arrays (like tables) store data requiring two indices. Strings are sequences of characters. Records group different data types into one logical unit, providing a structured way to represent real-world entities (e.g., a student record with name, ID, and grade).

What is Algorithm Output?

The output of an algorithm is the final result or information produced after the algorithm has completed its execution with a given set of inputs. Understanding the output requires a step-by-step analysis of how input data is processed and transformed by the algorithm's instructions.

Using Trace Tables for Algorithms

A trace table is a methodical way to manually execute an algorithm and record the state of its variables and outputs at each stage. To use a trace table effectively: create columns for each variable and output. Move row by row, updating variable values and noting output as each line of the algorithm is processed. This helps determine the precise value a variable will hold at any specific point.

Steps to Determine Algorithm Output

1. Understand the algorithm: Read through the pseudocode or flowchart to grasp its logic. 2. Identify inputs and variables: Note down all variables that will store values and any initial inputs. 3. Create a trace table: Set up columns for each variable and an output column. 4. Step-by-step execution: Process each line of the algorithm, updating variable values in the trace table as you go. 5. Record output: Whenever the algorithm produces output, record it in the trace table. 6. Final value: The last recorded value for a variable in its column is its final value. The final output is the last value in the output column.

Core Algorithmic Constructs

Algorithms are built using four main logical constructs: Sequence, Selection, Repetition (Iteration), and Input/Processing/Output. Understanding these is fundamental. Sequence means instructions run one after another in order. Selection introduces decision-making based on conditions (e.g., IF/THEN/ELSE). Repetition allows blocks of code to run multiple times, which can be count-controlled (e.g., FOR loops) or condition-controlled (e.g., WHILE loops). Iteration over data structures is a specific type of repetition, processing each element.

Representing Algorithms

Algorithms can be represented in various ways. Flowcharts use standard graphical symbols to depict the flow of control, making them visual and easy to follow. Pseudocode uses a structured, English-like notation that is similar to programming languages but less rigid, providing a clear description of the algorithm's logic. Program code is the actual implementation of the algorithm in a specific programming language. Each representation serves to clearly define the steps involved in solving a problem.

Types of Repetition

Repetition, often called iteration or looping, is key for efficiency. Count-controlled loops execute a set number of times, commonly seen with 'FOR' loops where the loop variable increments or decrements through a range. Condition-controlled loops continue to execute as long as a specified condition remains true or until it becomes false, typically implemented with 'WHILE' loops. Iteration 'over every item in a data structure' is a common condition-controlled or implicit count-controlled loop that processes each element, array item, or list member sequentially until all have been handled.

Input, Processing, Output (IPO)

The IPO model describes the essential flow of data in an algorithm. Input involves obtaining data from a user, file, or sensor. Processing is the manipulation of this input data according to the algorithm's logic, transforming it to achieve the desired outcome. Output is the presentation of the results of the processing, often displayed to the user, saved to a file, or sent to another system. This fundamental model applies to almost all computational tasks.