Algorithms, flow charts and bin packing
Studying this course? Keep your progress in one place.
Key facts
- An algorithm is a finite list of precise steps that always stops.
- In a flow chart an oval is Start or Stop, a parallelogram is input or print, a rectangle is a process and a diamond is a decision.
- A trace table records each variable every time it changes: show every pass of a loop.
- The middle item of items is in position if is odd and if is even.
- The lower bound for bin packing is total size ÷ capacity, rounded up; first-fit decreasing usually uses the fewest bins.
What an algorithm is
An algorithm is a finite sequence of precise steps that solves a problem and always stops. You apply it by following the steps exactly.
An algorithm can be written as numbered instructions or drawn as a flow chart.
- Inputs are the values you start with.
- A loop repeats steps by going back to an earlier step.
- A decision chooses between two routes, Yes or No.
You are not expected to work out the order (efficiency class) of an algorithm.
- 1
Input
the starting values
- 2
Process
carry out the instructions
- 3
Decision
is the loop test met? Yes: go back to the process
- 4
Stop
output the result when the test fails
What is the job of a decision in an algorithm?
Flow chart symbols
Each flow chart shape has one job: oval for Start or Stop, parallelogram for input or print, rectangle for a process and diamond for a decision.
A flow chart draws an algorithm with standard shapes joined by arrows.
- Arrows show the order of the steps.
- A diamond always has two exits, labelled Yes and No.
- A loop is an arrow that returns to an earlier step.
A process rectangle holds an instruction such as .
- 1
Oval: Start
Every flow chart begins here
- 2
Parallelogram: Input N
Input or print
- 3
Rectangle: S = 0
A process, such as setting or adding to a total
- 4
Diamond: Is N > 0?
Decision with a Yes exit and a No exit; Yes loops back
- 5
Oval: Stop
Every flow chart ends here
Oval
- Start or Stop
Parallelogram
- Input or print
Rectangle
- A process, such as adding to a total
Diamond
- A decision with Yes and No exits
Which shape holds the test of a loop?
Trace tables
To apply an algorithm, write a trace table with a column for each variable and a new row each time a value changes.
A trace table shows exactly what the algorithm does.
- Give each variable a column.
- Add a row every time a value changes.
- Apply the loop test after the values change, and stop when it fails.
State the output with its context once the trace is finished.
- N
- S
| N | S | |
|---|---|---|
| Start | 14 | 0 |
| After pass 1 | 11 | 14 |
| After pass 2 | 8 | 25 |
| After pass 3 | 5 | 33 |
| After pass 4 | 2 | 38 |
| After pass 5 | −1 | 40 |
N
- Start:
- 14
- After pass 1:
- 11
- After pass 2:
- 8
- After pass 3:
- 5
- After pass 4:
- 2
- After pass 5:
- −1
S
- Start:
- 0
- After pass 1:
- 14
- After pass 2:
- 25
- After pass 3:
- 33
- After pass 4:
- 38
- After pass 5:
- 40
Worked example
Step 1 input . Step 2 set . Step 3 add to . Step 4 replace by . Step 5 repeat from Step 3 while . Step 6 print . Trace the algorithm for .
- 1
Start with , . Step 3 gives , then Step 4 gives . The test is true, so repeat.
- 2
Next , then . Repeat.
- 3
Next , then . Repeat.
- 4
Next , then . Repeat.
- 5
Next , then . The test is now false, so stop.
In the worked example, what is printed?
Finding the middle item
The middle item of items is in position if is odd, and if is even.
Whenever an algorithm needs the middle item of a list, use these positions.
- gives the 5th item.
- gives the 4th item.
For an even the middle item is the one just after the true centre.
If a search deletes the middle item and the items beyond it, renumber the remaining list from 1 before applying the rule again.
- N oddposition
- N evenposition
Worked example
Find the position of the middle item in a list of 10 items.
- 1
is even, so use .
- 2
.
Which position is the middle of a list of 7 items?
Bin packing and the lower bound
Bin packing places items in as few bins of fixed capacity as possible. The lower bound is the total size divided by the capacity, rounded up.
Bin packing asks for every item to be placed in a bin without any bin exceeding its capacity, using as few bins as possible.
The algorithms give a good solution, not always the best, so they are heuristic.
The lower bound is the least number of bins that could possibly be needed. If an algorithm uses exactly that many, the packing is optimal.
For files totalling 73 MB on 20 MB sticks, , so at least 4 sticks are needed.
- Load (first-fit decreasing)
- Capacity
- Lower bound
Items total 62 and each bin holds 15. What is the lower bound on bins?
First-fit methods
First-fit places each item in the first bin with room. First-fit decreasing sorts the items largest first and then applies first-fit, which usually uses fewer bins.
First-fit: take the items in the order given and place each in the first bin that has room, starting a new bin only when no earlier bin can take it.
First-fit decreasing: sort the items into decreasing order, then apply first-fit.
Full-bin: find combinations of items that fill a bin exactly, pack these first, then pack the rest by first-fit.
- Load (first-fit)
- Capacity
First-fit
- Use the order given
- Earliest bin with room
First-fit decreasing
- Sort largest to smallest first
- Then apply first-fit
Full-bin
- Find exact fills first
- Pack the rest by first-fit
Worked example
Bin capacity 20. Items: 9, 7, 11, 6, 5, 13, 12, 10. Pack them using first-fit and first-fit decreasing.
- 1
First-fit in the order given: 9 and 7 go in bin 1. 11 does not fit with them, so it starts bin 2. 6 and 5 do not fit in bin 1 (22 and 21), so 6 joins 11 in bin 2 and 5 starts bin 3.
- 2
13 joins 5 in bin 3. 12 starts bin 4 and 10 starts bin 5. That is , , , , : 5 bins.
- 3
Sort into decreasing order: 13, 12, 11, 10, 9, 7, 6, 5.
- 4
Apply first-fit: , , , : 4 bins.
Why might first-fit decreasing use fewer bins than first-fit?
Try an exam question
Bin capacity is 12. The items to be packed are 5, 7, 4, 3, 6, 2, 8, 5. (a) Calculate a lower bound for the number of bins needed. (b) Use first-fit to pack the items, listing the contents of each bin.
[4 marks]
- [1]Total size of the items is 40, and 40 ÷ 12 = 3.33.
- [1]So at least 4 bins are needed.
- [1]Bins 1 and 2 correct: {5, 7} and {4, 3, 2}.
- [1]Bins 3 and 4 correct: {6, 5} and {8}, so first-fit uses 4 bins.
That's the notes covered.
Carry on to the next subtopic.
Try a question
Find the value printed when the input is .
1 mark, marked against the mark scheme
Find the value printed when the input is .
1 mark, marked against the mark scheme