2.1 Algorithms

Completed flashcard set

What are the three principles of computational thinking?

• Abstraction

• Decomposition

• Algorithmic thinking

What is abstraction and how is it used to solve problems?

Abstraction is a principle of computational thinking that involves removing unnecessary details from a problem to focus on the key information needed to solve it.

It simplifies a problem and makes it less complex; this makes it easier to understand the problem and create a solution.

What is decomposition and how is it used to solve problems?

Decomposition is a principle of computational thinking that involves the breaking down of problems into smaller, simpler steps or stages.

Each individual step can be separately tested and solved, making it easier to solve the problem as each smaller part acts as an easier, manageable sub-problem.

It also enables different people to work on different parts of the same problem simultaneously, allowing problems to be solved more quickly.

What is algorithmic thinking and how is it used to solve problems?

Algorithmic thinking is a principle of computational thinking that involves working out the steps needed to be taken to solve the problem and producing an algorithm (set of instructions) that needs to be followed to solve the problem.

It is used as it helps programmers to understand and breakdown the problem so that they know what they need to do and how to do it, making it easier to solve the problem.

It involves both abstraction and decomposition.

What is an algorithm and why are they created?

A set of instructions presented in a logical sequence

Programmers create algorithms as a method of planning a program before writing any code; this helps them to consider potential problems in the program and easier to begin to create source code.

What are flowcharts?

A tool that can be used to visually represent an algorithm (set of instructions presented in a logical order to plan a program)

What flowchart symbol is used at the beginning and end of a flowchart?

A terminal

What flowchart symbol is used for an if statement?

A decision

What flowchart symbol would be used for

• sum = sum + number

• password = 1234

A process

What flowchart symbol would be used for:

• print(name)

• temperature = input

Input and output

Give the flowchart symbols for:

• a line

• input and output

• process

• decision

• subprogram

• terminal

What are trace tables used for?

To track the value of variables as a program is run

They can be used to manually track the value of variables to investigate why the program isn’t working as intended

Each row in the trace table presents another line, each column stores the value of variables as they change.

Name the standard searching algorithms

• Linear search

• Binary search

Name the standard sorting algorithms

• Bubble sort

• Merge sort

• Insertion sort

State the main steps of a linear search algorithm, any pre-requisites and give the key features of the code/algorithms

• Each value is searched in order from the first value to the last

Pre-requisites:

• No pre-requisites; can be used on any dataset, even unsorted ones

For large lists this is not very efficient and takes a long time

Key features:

• A loop is used to check the first value in a list and increment by 1, checking each value for a match to the target

• Reaching the last element without finding a match means the value is not included

State the main steps of a binary search algorithm, any pre-requisites and give the key features of the code/algorithms

• The midpoint of the data set is selected and compared to the target value

• If the midpoint is greater than the value, the right half of the dataset is discarded and the midpoint of the remaining dataset is selected etc. If the midpoint is less than the value, the left half of the dataset is discarded and the midpoint of the remaining dataset is selected etc

Pre-requisites:

• Data must already be sorted!

Much quicker and more efficient, especially for large datasets.

Key features:

• A midpoint, low point and high point are all calculated

• A while loop is used to repeatedly compare the midpoint to a target value

• The upper half or lower half of the data is completely ignored if the midpoint does not equal the target

State the main steps of a merge sort algorithm

Merge sorts separates and then merges data together again in the correct order.

• A merge sort list divides a dataset into half again and again until each data item is separate

• The items are then compared and combined until there is one dataset in the correct order

Efficient and quick for large lists

State the main steps of a bubble sort algorithm

The algorithm repeatedly bubbles through the data set comparing each item each time.

• The algorithm iterates through a data set continuously and compares adjacent data elements and swaps them if they are not in the correct order

• The algorithm will only stop when a complete iteration has been made through the dataset and no swaps have been made

Not suitable for large sets of data

State the main steps of an insertion sort algorithm

• The list is logically split into sorted values (on the left) and unsorted values (on the right)

• Starting from the left, values from the unsorted part are checked and inserted into the correct position on the sorted part

• This continues through all of the elements in the list until the last item is reached and sorted

Efficient for small datasets but slow for large datasets.