Unit 1, Chapters 1-3, Algorithms and Problem Solving

This guide focuses on Unit 1: Problem Solving, drawing directly from the key concepts detailed in the sources provided.

Study Guide: Unit 1 – Problem Solving (Chapters 1–3)

Chapter 1: Understanding Algorithms

This chapter introduces what algorithms are, how they are defined, judged, and represented as the groundwork for programming.

1. Definition and Core Components

  • An algorithm is a precise method for solving a problem. It is an ordered set (or sequence) of instructions designed to achieve an expected result.

  • All instructions within an algorithm must be unambiguous; they cannot be misunderstood (e.g., "turn left" is unambiguous, while "turn" is ambiguous).

  • Relationship to Programs: An algorithm is the detailed design for a solution, while a program is that design implemented in a high-level programming language.

2. Characteristics of a Successful Algorithm

When designing an algorithm, three factors must be considered to ensure success:

  • Accuracy: It must consistently lead to the expected outcome (e.g., calculating a route).

  • Consistency: It must produce the same result every single time it is run.

  • Efficiency: It must solve the problem as quickly as possible, utilizing the fewest computer resources (shortest possible time).

3. Methods of Displaying Algorithms

Algorithms can be expressed in different formats depending on the need for clarity or translation:

  • Written Descriptions: The simplest expression, consisting of step-by-step instructions.

  • Flowcharts: A visual display using specific symbols (like Start/End, Process, Decision, Input/Output) linked by arrows to show the logical flow of the algorithm.

  • Pseudocode: A structured, code-like language. Its primary function is to allow the developer to focus entirely on the logic and efficiency without worrying about the strict rules of a high-level programming language. Pseudocode is relatively straightforward to translate into any high-level language.

4. Data Storage: Variables and Constants

These are the fundamental "containers" used for storing data:

  • Variable: A container holding a value that can change while the program runs. Variables are useful because the same program can process different sets of data.

  • Constant: A container holding a value that never changes (e.g., storing the value of pi).

  • Both must be assigned a unique identifier (name), which should be descriptive to improve code readability.

5. Arithmetic Operators

These are specific characters used to perform calculations on numbers:

  • Basic Operators: Addition (+), Subtraction (-), Multiplication (*), and Real Division (/) (returns result including decimal places).

  • Specialized Operators:

    • Quotient (DIV): Returns only the whole number (integer) result of a division.

    • Modulus/Modulo (MOD): Returns the remainder of a division (e.g., 13 MOD 4 = 1).

    • Exponentiation (^): Used for "to the power of".

Chapter 2: Creating Algorithms

This chapter moves from understanding what an algorithm is to establishing the essential building blocks used to create executable algorithms for computers.

1. Programming Constructs (The Building Blocks)

Algorithms are constructed from three basic elements:

  • Sequence: A simple, ordered set of step-by-step instructions executed in the correct order.

  • Selection: A construct that allows the algorithm to make a choice between alternatives, based on whether a certain condition is met (e.g., using an IF...THEN...ELSE structure). If there are more than two alternatives, a nested IF statement must be used in Pearson Edexcel pseudocode.

  • Iteration (Loops): A construct that causes a process to be repeated. The action repeats until a defined condition is met or a particular outcome is reached.

    • Definite Iteration: Used when the number of repetitions is known in advance (e.g., using FOR...END FOR or REPEAT...END REPEAT structures).

    • Indefinite Iteration: Used when the number of repetitions is not known in advance, repeating until a specified condition is reached (e.g., using a WHILE loop).

2. Logical Operators

Selection often relies on Boolean logic to determine if a condition is true or false:

  • AND: The overall condition is true only if both connected conditions are true.

  • OR: The overall condition is true if at least one of the connected conditions is true.

  • NOT: Reverses the logic of an expression (true becomes false, and vice versa).

  • Operator Precedence: When evaluating logic, the order is: Brackets, then NOT, then AND, and finally OR.

Chapter 3: Sorting and Searching Algorithms

This chapter covers two of the most common and important tasks in computing: organizing (sorting) and locating (searching) data efficiently.

1. Sorting Algorithms

Sorting arranges items into a specific order, typically ascending order (smallest to largest) or descending order (largest to smallest).

Algorithm

Method and Approach

Efficiency

Bubble Sort

Brute Force method. Starts at one end, compares adjacent pairs of data items, and swaps them if they are in the wrong order. The process repeats (a "pass") until a full pass occurs with no swaps.

The slowest of the required sorts. Good for small lists where time difference is negligible, but slow for large lists.

Merge Sort

Divide and Conquer method. Recursively divides the list into smaller halves until each list contains only a single item. These sorted lists are then repeatedly merged back together in the correct sequence. The repeated application of a method to previous results is called recursion.

One of the most efficient sorting algorithms.

2. Searching Algorithms

Searching aims to find a specific item within a list.

Algorithm

Method and Requirement

Efficiency

Linear Search

Simple, sequential method. It starts at the first item and checks each item one by one until the target is found or the list ends.

Best Case: 1 comparison (item is first). Worst Case: N comparisons (item is last). Preferable if the list is searched only once or if the list is small.

Binary Search

Divide and Conquer method. Requirement: The list must already be sorted (ascending or descending). It repeatedly selects the median (middle item) of the current sub-list. If the target is not the median, the search continues only on the relevant half (left or right).

Highly efficient for large lists searched multiple times. Worst Case for 1,000 items is only 10 comparisons (versus 1,000 for linear search).