CPX1Decomposition, Abstraction and Algorithms

Decomposition means breaking a problem or solution down into smaller parts.

• Keep splitting until each part is small enough to understand and solve on its own.
• Name each part by the job it does: “Record results”, not “Results”.
• Benefits of decomposition:
• Each small part is easier to understand and solve than the whole problem.
• Different programmers can work on different parts at the same time, so the program is finished sooner.
• Each part can be tested on its own, so errors are easier to find.
• Parts often become subprograms, which can be reused in other programs.

Decomposing a sports day results program. Each part can be broken down again until it is small enough to solve.

Decomposition

Breaking a problem or solution down into smaller parts.

Abstraction means removing or hiding unnecessary detail, so you can focus on what matters for the problem.

• Removing detail: a weather app shows a sun or cloud icon and a temperature. It leaves out air pressure readings, satellite data and the maths of the forecast.
• A general model from common features: look at a group of objects, keep the features they share that the problem needs, and drop the rest. A journey planner treats a bus, a tram and a ferry all as a “vehicle” with a route, capacity and next stop.
• Abstraction in code: a subprogram hides how a task is done. The main program calls calcPostage (weight) without needing to know the steps inside it.
• What counts as unnecessary depends on the problem. A tram’s colour doesn’t matter to a journey planner, but it might matter to a paint shop’s program.
• Benefits: the problem is simpler to understand and solve; programmers can use a subprogram without knowing how it works; one general model can be reused for many objects.

Abstracting the common features of three vehicles into one general model

Abstraction

Removing or hiding unnecessary detail from a problem.

General model

A model made by keeping the features a group of objects have in common and dropping the rest.

A subprogram is a named block of code that does one specific task. Other code runs it by calling its name.

• Function: returns one or more values to the code that called it.
• Procedure: carries out a task but does not return a value.
• In Python both are written with def. Both can take parameters.
• Pre-existing subprograms are already written for you: built-in ones such as len () and print (), and library ones such as random.randint ().
• Subprograms are a form of abstraction: the caller uses the name and doesn’t need to know the code inside.

# -------------------------------------------------------
# Subprograms
# -------------------------------------------------------
def showBanner (pTitle):
    print ("=" * 20)
    print (pTitle)
    print ("=" * 20)

def floorArea (pLength, pWidth):
    area = pLength * pWidth
    return (area)

# -------------------------------------------------------
# Main program
# -------------------------------------------------------
showBanner ("Flooring quote")
room = floorArea (4.5, 3)
print ("Area:", room, "square metres")

Subprogram

A named, self-contained block of code that performs a specific task and is called from other code.

Function

A subprogram that returns one or more values to the calling code.

Procedure

A subprogram that carries out a task but does not return a value.

An algorithm is a precise set of step-by-step instructions to solve a problem or complete a task.

• Algorithms are used to plan a program before it is written, and to describe how a program works.
• Most algorithms take input (data in), do processing (calculations, comparisons, decisions) and give output (results out).
• Input: input (), reading a file, a sensor reading.
• Processing: arithmetic, comparing values, updating a total, choosing what to do next.
• Output: print (), writing to a file, switching on a motor or light.

1  minutes = int (input ("Minutes of screen time: "))
2  hours = minutes // 60
3  left = minutes % 60
4  print (hours, "h", left, "min")

Algorithm

A precise set of step-by-step instructions to solve a problem or complete a task.

Input

Data that goes into an algorithm, e.g. typed by the user or read from a file.

Processing

What the algorithm does with the data: calculations, comparisons and decisions.

Output

The results an algorithm gives out, e.g. displayed on screen or written to a file.

Pearson shows algorithms in three ways, and you can answer in any of them unless a question says otherwise.

• Flowchart: a diagram of the steps using standard symbols and arrows.
• Written description (pseudocode): in this course, “pseudocode” just means an informal written description in English. There is no special syntax to learn.
• Program code: Python, in the style printed in the exam (a space before brackets, conditions in brackets).
• Why use a flowchart? The flow and the decisions are easy to see at a glance; it doesn’t depend on any programming language; non-programmers can check the logic.

charge = int (input ("Charge: "))
if (charge < 20):
    dimScreen ()
    print ("Saver on")
else:
    print ("Normal mode")

Flowchart

A diagram that represents an algorithm using standard symbols joined by arrows.

Pseudocode (Edexcel)

An informal written description of an algorithm, in English, with no strict syntax.

Pearson uses six flowchart symbols. Learn their names and what goes in each.

• Terminator (rounded): Start and Stop. Every path must reach a Stop.
• Process (rectangle): a calculation or assignment, e.g. total = total + steps.
• Input/output (parallelogram): e.g. “Input age”, “Output total”.
• Decision (diamond): a question with exactly two exits, labelled Yes/No or True/False.
• Pre-defined subprogram (rectangle with double sides): calls a subprogram that is defined elsewhere.
• Arrows show the order. A loop is an arrow that goes back to an earlier step: there is no loop symbol.
• In a decision you may write == or =; “Output”, “Print” and “Display” are all accepted.

The six symbols

The battery saver algorithm as a flowchart. The double-sided box calls a subprogram that is written somewhere else.

Terminator

The rounded flowchart symbol for Start and Stop.

Decision symbol

A diamond holding a question, with exactly two labelled exits.

Pre-defined subprogram symbol

A rectangle with double vertical sides, used to call a subprogram defined elsewhere.

Every algorithm is built from a few constructs. You must be able to spot each one in numbered code.

• Sequence: instructions run one after another, in order.
• Selection: a condition decides which block runs (if, elif, else). When asked for the lines of a selection, give the whole block, not just the if line.
• Repetition: a block runs again and again. Count-controlled repetition runs a set number of times (for … in range (…)). Condition-controlled repetition runs until a condition changes (while).
• Iteration (Pearson’s meaning): running the same block for every item in a data structure, such as each item of a list or each character of a string (for item in list:).

 1  # -------------------------------------------------------
 2  # Global variables
 3  # -------------------------------------------------------
 4  scores = [12, 18, 7, 15]
 5  total = 0
 6  answer = ""
 7  
 8  # -------------------------------------------------------
 9  # Main program
10  # -------------------------------------------------------
11  for score in scores:
12      total = total + score
13  for count in range (0, 3):
14      print ("Checking...")
15  while (answer != "yes"):
16      answer = input ("Ready to see your result? ")
17  if (total > 50):
18      print ("Merit")
19  else:
20      print ("Pass")

Sequence

Instructions carried out one after another in order.

Selection

Choosing which block of code to run depending on a condition.

Count-controlled repetition

A loop that repeats a set number of times.

Condition-controlled repetition

A loop that repeats until a condition is met (or while it is true).

Iteration

Repeating the same block of code for every item in a data structure.

Both are named stores of data in memory. The difference is whether the value can change while the program runs.

• Variable: its value can change during execution, e.g. a running total or a user’s answer.
• Constant: its value stays the same throughout execution, e.g. VAT_RATE = 0.2 or MAX_PLAYERS = 4.
• Python has no true constants. By convention a constant’s name is written in CAPITALS, so programmers know not to change it.
• Why use a named constant instead of typing the value each time?
• If the value changes (say the VAT rate), you edit it in one place and every use updates, with no risk of missing one.
• The name explains what the number means, so the code is easier to read.
• It can’t be changed by accident partway through the program.

Variable

A named location in memory that stores a value that can change during program execution.

Constant

A named value that does not change during program execution; written in CAPITALS in Python.

A data structure holds many values under one name. Each item is found by its index, which starts at 0.

• String: a sequence of characters. word[0] is the first character.
• Array: a sequence of items that all have the same data type (homogeneous), e.g. a list of temperatures.
• Record: a sequence of items that may have different data types (heterogeneous). Each item is a field, e.g. name, age, height.
• Two-dimensional structures are tables: a list of rows. A list of records is a common 2D table.
• In Python, arrays and records are both written as lists. A 2D table is a list of lists: table[row][column].
• Traversing a 2D table needs two loops: an outer loop over the records and an inner loop over the fields of each record.

A two-dimensional table of records: give the row index first, then the column

1  days = ["Mon", "Tue", "Wed", "Thu", "Fri"]
2  squad = [["Ama", 15, 1.62, True],
3           ["Ben", 14, 1.55, False],
4           ["Cai", 15, 1.70, True]]
5  word = "python"
6  print (days[2])
7  print (squad[1][0])
8  print (squad[2][2])
9  print (word[0])

Array

A data structure holding a sequence of items of the same data type.

Record

A data structure holding a sequence of items (fields) that may be of different data types.

Field

One item in a record.

Index

The position of an item in a data structure, counting from 0.