2.1 Algorithms

Question 1

Computational thinking

Answer 1

Structuring problems in a way that computers can easily follow

Question 2

Decomposition

Answer 2

Breaking a problem down into smaller subproblems

Question 3

Abstraction

Answer 3

Removing or hiding unnecessary details from a problem so that important details can be focused on or more easily understood

Question 4

Algorithmic thinking

Answer 4

Deciding on the order that instructions are carried out and identifying decisions that need to be made by the computer

Question 5

Structure diagram

Answer 5

Graphical method of decomposing a problem
-each layer breaks down layer above it into smaller and smaller sub-problems
-root and node

Question 6

Flowchart

Answer 6

Graphical representation of an algorithm
-line
-process
-subprogram
-input/ output
-decision
-terminal

Question 7

Flowchart symbols - line, process, subprogram, input/output, decision, terminal

Answer 7

Line - arrow
Process - rectangle
Subprogram - rectangle with two lines
Input/ output - parallelogram
Decision - diamond
Terminal (start/end) - rounded rectangle

Question 8

Trace table

Answer 8

Tool used to follow each line of an algorithm through step by step
-show contents of each variable after each line has been carried out and any output

Question 9

Standard searching algorithms

Answer 9

-linear search
-binary search

Question 10

Linear search

Answer 10

Inspecting each item of the list in turn to check if it is the desired value
-when value is matching, item is found. If not, next item is checked
-inefficient
-works on unsorted data

Question 11

Binary search

Answer 11

1. calculate a mid-point in the data set
2. check if that is the item to be found
3. if the item to be found is lower than the mid-point, repeat on the bottom half of the data set
4. if the item to be found is greater than the mid-point, repeat on the top half of the data set
5. repeat until the item is found or only one item left

-discard middle value
-more efficient
-only works on sorted list

Question 12

Standard sorting algorithms

Answer 12

-bubble sort
-merge sort
-insertion sort

Question 13

Bubble sort

Answer 13

1. Comparing pairs of value
2. If two values are in wrong order, swapped
3. Repeated for each further pair of values
4. When last pair of values has been compared, first pass is complete
5. Algorithm repeats until pass has been completed with no swaps occurring - guaranteed to be in order

Question 14

Insertion sort

Answer 14

Splits the list to be sorted in two parts: sorted side and unsorted side
1. Initially, sorted side contains first item in a list, everything else on the unsorted side
2. first item from unsorted list is inserted to sorted list
3. Repeat until unsorted list has no values

-more efficient
-tricky to code

Question 15

Merge sort

Answer 15

1. Splits data up into individual lists
2. Pairs of lists are merged back together in order
3. Repeats until there is one merged list

-more efficient - sorts large list of random values in a quicker time
-not best for nearly sorted or small lists
-divide and conquer