Algorithms, flow charts and bin packing

Algorithms, flow charts and bin packing Flashcards

Spec 1.1–2 · Edexcel International A Level Maths: Flashcards

Studying this course? Keep your progress in one place.

Flip each card. Be honest: the ones you mark Not yet come back first.

13 cards

Tap a card to flip it. Swipe right if you knew it, left if not.

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 NN items, NN odd?
N+12\frac{N+1}{2}
Middle item position in a list of NN items, NN even?
N+22\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.

Flashcards