Algorithms (Paper 2)

Question 1

what are the three main principles of computational thinking

Answer 1

abstraction
decomposition
algorithmic thinking

Question 2

what is abstraction

Answer 2

the process of removing unnecessary details of a problem to focus on the important features to implement in a solution

Question 3

implementations of abstraction

Answer 3

computer games
users don’t need to know the complex algorithms used to control the NPCs. it is only important to the user they recognise the environment and when they perform an action, they see a response

train maps
travellers don’t need to know the geographical layout of the routes, only that getting on at stop A will eventually transport you to stop B

Question 4

what is decomposition

Answer 4

the process of breaking down a large problem into a set of smaller problems

Question 5

benefits of decomposition

Answer 5

smaller problems are easier to solve
each smaller problem can be solved independently of others
smaller problems can be tested independently
smaller problems can be combined to produce a solution to the full problem

Question 6

describe computer games as an example of decomposition

Answer 6

modern computer games are decomposed to break down the complexity of the problem into more manageable ‘chunks’. for example:
levels - levels can be designed/created independently of other levels
characters - the mechanics of characters in the game can be designed and created by a separate team
landscape - the art team can work on the visual aspects of the game without needing to understand how the game is programmed

Question 7

what is algorithmic thinking

Answer 7

the process of creating step-by-step instructions in order to produce a solution to a problem
algorithmic thinking requires the use of abstraction and decomposition to identify each individual step
once each step has been identified, a precise set of rules (algorithm) can be created and the problem will be solved

Question 8

what is a searching algorithm

Answer 8

precise step-by-step instructions that a computer can follow to efficiently locate specific data in massive data sets

Question 9

conditions for a binary search to be performed on a set of data

Answer 9

the data must be in order.
it can be performed on datasets containing numbers or words.
searching for a word instead of a number is the same process, except comparisons are made based on position in the alphabet instead of numerical size

Question 10

how to perform a binary search

Answer 10

-identify middle value
-compare to value you are looking for
-if it is the value you are looking for, stop
-else if it is bigger then the one you are looking for, create a new list with the values on the left of the middle value
-if it is smaller than the one you are looking for, create a new list with the values on the right of the middle value
-repeat with the new list

Question 11

what is a linear search

Answer 11

starts with the first value in a data set and checks every value one at time until all values have been checked

Question 12

advantages for binary searches

Answer 12

-fast for large datasets
-efficient for repeated searches

Question 13

disadvantages of binary search

Answer 13

-dataset must be in order
-more complex to implement

Question 14

advantages for linear search

Answer 14

-works on unsorted datasets
-faster on very small datasets
-simple to understand and implement

Question 15

disadvantages for linear search

Answer 15

-slow for large datasets
-inefficient, starts at the beginning each time

Question 16

what are the three common sorting algorithms

Answer 16

• Bubble sort
• Merge sort
• Insertion sort

Question 17

how to perform a bubble sort

Answer 17

-compare the first two values in the dataset
-if they are in the wrong order, swap them
-compare the next two values
-repeat step 2 and 3 until you reach the end of the dataset (pass 1)
-if you have made any swaps, repeat from the start
-else if you have not made only swaps, stop - the list is in the correct order

Question 18

what strategy does a merge sort use

Answer 18

‘divide and conquer’ strategy of dividing a dataset into smaller sub-datasets and merging them back together in the correct order

Question 19

how to perform a merge sort

Answer 19

1. divide the dataset into individual datasets by repeatedly splitting the data set in half
2. merge pairs of sub-datasets together by comparing the first value in each dataset
3. repeat step 2 until all sub-datasets are merged together into one dataset

Question 20

how to perform an insertion sort

Answer 20

1. take the first value in the dataset, this is now the sorted list
2. look at the next value in the dataset and compare it to the first value. if it is smaller, insert it into the correct position to the left
3. else, keep it in the same position
4. repeat steps 2 and 3 until all values in the dataset have been compared, the list should now be in order

Question 21

what shape is a terminator symbol (start/stop)

Answer 21

rectangle with rounded edges

Question 22

what shape are input/output symbols

Answer 22

rhombus

Question 23

what shape are process symbols

Answer 23

rectangle

Question 24

what shape are decision symbols

Answer 24

diamond

Question 25

what is a syntax error

Answer 25

an error that breaks the grammatical rules of a programming language and stops it from running

Question 26

what is a logic error

Answer 26

where incorrect code is used that causes the program to run, but produces an incorrect output or result