Algorithms

Question 1

Define:

Decomposition

Answer 1

Breaking a complex problem down into smaller problems and solving each one individually

Question 2

Define:

Abstraction

Answer 2

Picking out the important bits of information from the problem, ignoring the specific details that don’t matter

Question 3

Define:

Algorithmic Thinking

Answer 3

A logical way of getting from the problem to the solution. If the steps you take to solve the problem follow an algorithm then they can be reused and adapted to solve similar problems in the future

Question 4

Describe:

Flowcharts

Answer 4

A way of visualising algorithms using shaped boxes and arrows

Question 5

Describe:

Binary Search

Answer 5

Looks for items in an ordered list
1) Find the middle item in the list
2) If this is the item then stop the search
3) If not, compare the item you’re looking for to the middle item. If it comes before the middle item, get rid of the second half of the list. If it comes after the middle item then remove the first half of the list.
4) Repeat with the smaller lists until you find the item you’re looking for

Question 6

Describe:

Linear Search

Answer 6

Looks for items in an unordered list
1) Look at the first item in the list. If this is the target then stop the search
2) If not, look at the next item in the list. If this is the target then stop the search
3) If not, move on to the next item. Keep repeating until you find the target

Question 7

Describe:

Bubble Sort

Answer 7

Used to sort an unordered list of items
1) Look at the first two items in the list
2) If they’re in the right order, you don’t have to do anything. If they’re in the wrong order, swap them
3) Move onto the next pair (2nd and 3rd) and repeat step 2
4) Repeat step 3 until the end of the list. This is called one pass. The last item is now in the correct place so don’t include it in the next pass
5) Repeat steps 1-4 until there are no swaps in a pass

Question 8

Describe:

Merge Sort

Answer 8

1) Split the list in half. The second sub-list should start at the middle item
2) Keep repeating step 1 until all lists only contain one item
3) Merge pairs of sub-lists so that each sub-list has twice as many items. Each time you merge sub-lists, sort the items into the correct order
4) Repeat step 3 until you’ve merged all sub-lists together