Unit 1: Computational Thinking Edexcel GCSE Computer Science

Algorithm

Set of step-by-step instructions to complete a task, or solve a problem

Decomposition

breaking down larger problems into smaller problems, making them easier to solve

Abstraction

the process of hiding unnecessary details so that only the important points remain

Pattern recognition

Seeing similarities and differences in a range of problems

Computational thinking

Using methods to solve complex problems

Flowchart

Diagram that represents an algorithm showing the steps as boxes, and their order by connecting them with arrows.

3 basic programming constructs

Selection - Sequence - Iteration

3 elements of a successful algorithm

Accurate - Efficient - Consistent

Logical operators - AND

Two conditions must both be true for the whole statement to be true

Logical operators - OR

Either one of two conditions must be true for the whole statement to be true

Logical operators - NOT

Reverses the logic of the AND and OR statement

Logic error

Error that results in an unexpected output

Trace table

Used to identify logic errors in an algorithm

Sorting - Bubble sort

Uses 'brute force' to sort a list

Sorting - Merge sort

Uses 'divide and conquer' to sort a list

Searching - Linear search

Starts at beginning of list and searches until the item is found

Searching - Binary search

Selects the median item in a list, then checks if the desired item is higher or lower

Median

The middle number in a list of ascending or descending numbers

What is an Iteration?

Construct that allows the repetition of a process (also called a loop)

Selection

Construct that allows a choice to be made between different options

Why are subprograms used

reduce duplicate code

allows for easy reuse of code

makes code easier to debug

What is this flowchart symbol?

Terminal (start and stop)

What is this flowchart symbol?

input/output (e.g. input: enter a value/ print: your new value)

What is this flowchart symbol?

process (e.g. value*3)

What is this flowchart symbol?

decision (e.g. if value>5)

Aspects of Bubble sort

Slow

Suitable for small data sets

easy to program

Aspects of merge sort

Quick

suitable for large data sets

more difficult to program

Aspects of linear search

items do not need to be stored in order

new items are added at the end - quick

suitable for a small number of items

Aspects of binary search

items must be in order for the algorithm to work

new items must be added in the correct place to keep correct order - slow

suitable for a large number of items

Record

a record is a list where each value may be a different data type.

Why are constants used (instead of rewriting the value each time)?

If a value of a constant has to be changed, only one change is required

What is this type of operator? <, !=

relational

What is this type of operator? +, *

arithmetic

What is this type of operator? AND, NOT

Boolean/logical

Difference between syntax and logic errors

A syntax error is caused by using words of the programming language incorrectly, whereas a logic error is caused by an error in the design of the algorithm

Explain the effect on efficiency of using a bubble sort algorithm instead of a merge sort algorithm

A bubble sort will use less memory because it is an in-place sort

In-place algorithms

transforms the input without using extra memory (e.g. bubble sort)

Out-of-place algorithms

requires extra memory, the amount required depends on the input size (e.g. merge sort)

Define the term ‘iteration’.

looping over every item in a data structure

Benefit of subprograms

The subprogram may be used more than once in a program so will save time when writing

Explain why integer division is used rather than division, when finding the middle item in an array

If the length of the array is an odd number, division would return a real (decimal) number which is not valid because index values are integers

Define the term ‘subprogram’.

A self contained block of code that performs a specific task, that can be called by the main program when needed