Algorithms, flow charts and bin packing

Algorithms, flow charts and bin packing

Spec 1.1–2 · Edexcel International A Level Maths: Revision notes

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 NN items is in position N+12\frac{N+1}{2} if NN is odd and N+22\frac{N+2}{2} if NN 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. 1

    Input

    the starting values

  2. 2

    Process

    carry out the instructions

  3. 3

    Decision

    is the loop test met? Yes: go back to the process

  4. 4

    Stop

    output the result when the test fails

The shape of an algorithm with a loop

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 S=S+NS=S+N.

  1. 1

    Oval: Start

    Every flow chart begins here

  2. 2

    Parallelogram: Input N

    Input or print

  3. 3

    Rectangle: S = 0

    A process, such as setting or adding to a total

  4. 4

    Diamond: Is N > 0?

    Decision with a Yes exit and a No exit; Yes loops back

  5. 5

    Oval: Stop

    Every flow chart ends here

A small flow chart, with the shape used at each step.

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
The four flow chart shapes

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.

010203040Start12345PassValue
  • N
  • S
Trace of the worked example for N = 14: S grows each pass while N falls by 3, and the loop stops once N is below 0.

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
Trace of the worked example

Worked example

Step 1 input NN. Step 2 set S=0S=0. Step 3 add NN to SS. Step 4 replace NN by N−3N-3. Step 5 repeat from Step 3 while N>0N>0. Step 6 print SS. Trace the algorithm for N=14N=14.

In the worked example, what is printed?

Finding the middle item

The middle item of NN items is in position N+12\frac{N+1}{2} if NN is odd, and N+22\frac{N+2}{2} if NN is even.

Whenever an algorithm needs the middle item of a list, use these positions.

  • N=9N=9 gives the 5th item.
  • N=6N=6 gives the 4th item.

For an even NN 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.

012345678910111middle: 6th10
Positions in a list of 10 items: N is even, so the middle item is in position (10 + 2)/2 = 6.
  • N oddposition N+12\dfrac{N+1}{2}
  • N evenposition N+22\dfrac{N+2}{2}

Worked example

Find the position of the middle item in a list of 10 items.

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, 7320=3.65\frac{73}{20}=3.65, so at least 4 sticks are needed.

05101520Bin 1Bin 2Bin 3Bin 4BinLoad
  • Load (first-fit decreasing)
  • Capacity
Items 9, 7, 11, 6, 5, 13, 12, 10 total 73. With capacity 20 the lower bound is 4 bins, and first-fit decreasing achieves it.
  • Lower bound⌈total size of itemsbin capacity⌉\left\lceil\dfrac{\text{total size of items}}{\text{bin capacity}}\right\rceil

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.

05101520Bin 1Bin 2Bin 3Bin 4Bin 5BinLoad
  • Load (first-fit)
  • Capacity
First-fit in the order given uses 5 bins for the worked example (loads total 73, capacity 20).

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
Three bin packing methods

Worked example

Bin capacity 20. Items: 9, 7, 11, 6, 5, 13, 12, 10. Pack them using first-fit and first-fit decreasing.

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]

That's the notes covered.

Carry on to the next subtopic.

Try a question

Find the value printed when the input is N=14N=14.

1 mark, marked against the mark scheme

Revision notes