Decision 1: Algorithms

Question 1

What do the shapes of flow chart boxes mean? (3)

Answer 1

Squares with rounded edges - start/end
Squares - instructions
Diamond - decision

Question 2

What is a trace table?

Answer 2

A table that records values from a flow chart, answering all decisions

Question 3

What does the Euclidean algorithm do?

Answer 3

It finds the highest common factor of two numbers

Question 4

What is bubble sort? (2)

Answer 4

A method of sorting numbers by comparing and switching adjacent numbers until the end of one pass is identical to the previous pass
One pass - every adjacent pair of numbers has been compared

Question 5

What is quick sort? (3)

Answer 5

A method of sorting that uses the pivot (middle number) to move numbers into the correct order
The pivot - circled middle number (otherwise consistently choose left/right)
Fixed number - a boxed number that has been used as a pivot in a previous pass remains fixed

Question 6

What is bin packing?

Answer 6

The process of fixing ‘boxes’ into ‘bins’ with a fixed size

Question 7

How is the minimum number of bins needed for bin packing calculated?

Answer 7

Sum of box sizes / height of one bin

Question 8

Bin Packing - First Fit

Answer 8

Fit the boxes in the order given, putting them in the first bin with enough space or adding a bin if there is no room in any

Question 9

Bin Packing - First Fit Decreasing

Answer 9

Order the boxes in decreasing order, then use first fit

Question 10

Bin Packing - Full Bin

Answer 10

Fill as many bins as possible, in any order, and then use first fit on the remaining boxes

Question 11

What is an algorithm?

Answer 11

A finite sequence of step-by-step instructions carried out to solve a problem