What do the main flow chart shapes mean?

Oval: start or stop; parallelogram: input or print; rectangle: process; diamond: decision.

What is a trace table used for?

Recording the value of every variable as an algorithm is applied.

What is the aim of bin packing?

To pack the items into as few bins of a given capacity as possible.

How do you find the lower bound for the number of bins?

Total size of items divided by bin capacity, rounded up.

Describe the first-fit algorithm.

Take the items in the given order and put each in the first bin with room; start a new bin only if none fits.

Describe first-fit decreasing.

Sort the items into decreasing order, then apply first-fit.

Describe the full-bin method.

Find combinations of items that fill a bin exactly, pack them first, then pack the rest by first-fit.

What does Euclid's algorithm in text form find?

The highest common factor of two integers.

Algorithms, flow charts and bin packingEdexcel International A Level Maths: Flashcards

Card 1 of 130 of 13 known

Question

What is an algorithm?

Tap or press Space to reveal

Tap card or press Space to flip

See all 13 cards

What is an algorithm?: A finite sequence of precise steps that solves a problem and always stops.
What do the main flow chart shapes mean?: Oval: start or stop; parallelogram: input or print; rectangle: process; diamond: decision.
What is a trace table used for?: Recording the value of every variable as an algorithm is applied.
Middle item position in a list of $N$ items, $N$ odd?: $\frac{N+1}{2}$
Middle item position in a list of $N$ items, $N$ even?: $\frac{N+2}{2}$
Which item is the middle one in a list of 9? Of 6?: The 5th item; the 4th item.
What is the aim of bin packing?: To pack the items into as few bins of a given capacity as possible.
How do you find the lower bound for the number of bins?: Total size of items divided by bin capacity, rounded up.
Describe the first-fit algorithm.: Take the items in the given order and put each in the first bin with room; start a new bin only if none fits.
Describe first-fit decreasing.: Sort the items into decreasing order, then apply first-fit.
Describe the full-bin method.: Find combinations of items that fill a bin exactly, pack them first, then pack the rest by first-fit.
If an algorithm uses the lower-bound number of bins, what can you say?: The packing is optimal.
What does Euclid's algorithm in text form find?: The highest common factor of two integers.

Exam questions on Algorithms, flow charts and bin packing

An algorithm is described as follows. Step 1: Input a number $N$ . Step 2: Set $S$ equal to 0. Step 3: Add $N$ to $S$ . Step 4: Replace $N$ by $N-3$ . Step 5: If $N>0$ , go to Step 3. Step 6: Print $S$ .
Find the value printed when the input is $N=20$ .2 marks
Eight files of sizes 9, 7, 11, 6, 5, 13, 12 and 10 megabytes (MB) are to be stored on memory sticks. Each memory stick can hold at most 20 MB.
Use the first-fit decreasing algorithm to pack the files, and write down the contents of each memory stick.2 marks
An algorithm is described as follows. Step 1: Input two positive integers $A$ and $B$ , with $A>B$ . Step 2: Let $R$ be the remainder when $A$ is divided by $B$ . Step 3: If $R=0$ , print $B$ and stop. Step 4: Replace $A$ by $B$ and $B$ by $R$ , then go to Step 2.
Apply the algorithm to the inputs $A=252$ and $B=105$ , showing the values of $A$ , $B$ and $R$ each time Step 2 is performed.3 marks

See the full worksheet

Written by the Exaim team, led by Shaun Daswani (Head of Upper Secondary, Improve ME Institute; MSc Financial Mathematics, Imperial College London; BSc, UCL) and Jason Daswani (operational lead, Improve ME Institute; LSE).