Decision 1: Algorithms Flashcards

1
Q

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

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

What is a trace table?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

What does the Euclidean algorithm do?

A

It finds the highest common factor of two numbers

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

What is bubble sort? (2)

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

What is quick sort? (3)

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

What is bin packing?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

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

A

Sum of box sizes / height of one bin

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Bin Packing - First Fit

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Bin Packing - First Fit Decreasing

A

Order the boxes in decreasing order, then use first fit

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Bin Packing - Full Bin

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

What is an algorithm?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly