Algorithms, bin packing and sorting

Algorithms, bin packing and sorting Flashcards

Spec 1.1–2 · Edexcel A-Level Further 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.

12 cards

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

See all 12 cards
What is an algorithm?
A finite, unambiguous sequence of instructions that solves a problem.
What does the order of an algorithm describe?
How the running time grows with the size of the problem for large nn.
Order of bubble sort?
n2n^2, from n(n−1)2\frac{n(n-1)}{2} comparisons.
Number of comparisons for bubble sort on nn items?
(n−1)+(n−2)+⋯+1=n(n−1)2(n-1)+(n-2)+\cdots+1=\frac{n(n-1)}{2}.
If time is of order n2n^2 and nn is multiplied by 10, the time is?
Multiplied by about 100.
What does first-fit do?
Places each item, in the given order, into the first bin with room.
What does first-fit decreasing do?
Sorts the items into descending order, then uses first-fit.
How do you find the lower bound for bin packing?
Total size ÷\div capacity, rounded up.
What is the full-bin method?
Find combinations of items that exactly fill a bin and pack these first.
What does one pass of bubble sort achieve?
The largest unsorted item ends up in its final position.
Pivot position in quick sort for N=6N=6?
6+22=4\frac{6+2}{2}=4th item.
Pivot position in quick sort for N=7N=7?
7+12=4\frac{7+1}{2}=4th item.

Flashcards