What does the order of an algorithm describe?

How the running time grows with the size of the problem for large n.

Order of bubble sort?

n^2, from \frac{n(n-1)}{2} comparisons.

Number of comparisons for bubble sort on n items?

(n-1)+(n-2)+\cdots+1=\frac{n(n-1)}{2}.

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.

Algorithms, bin packing and sortingEdexcel A-Level Further Maths: Flashcards

Card 1 of 120 of 12 known

Question

What is an algorithm?

Tap or press Space to reveal

Tap card or press Space to flip

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 $n$ .
Order of bubble sort?: $n^2$ , from $\frac{n(n-1)}{2}$ comparisons.
Number of comparisons for bubble sort on $n$ items?: $(n-1)+(n-2)+\cdots+1=\frac{n(n-1)}{2}$ .
If time is of order $n^2$ and $n$ 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=6$ ?: $\frac{6+2}{2}=4$ th item.
Pivot position in quick sort for $N=7$ ?: $\frac{7+1}{2}=4$ th item.

Exam questions on Algorithms, bin packing and sorting

The following algorithm is applied to two positive integers $a$ and $b$ , where $a>b$ . Step 1: input $a$ and $b$ . Step 2: let $r$ be the remainder when $a$ is divided by $b$ . Step 3: if $r=0$ , output $b$ and stop. Step 4: replace $a$ by $b$ and replace $b$ by $r$ . Step 5: go back to Step 2.
State what the algorithm finds, and explain why it must eventually stop.2 marks
Nine files of sizes 7, 13, 8, 3, 5, 9, 4, 14 and 12 MB are to be saved on memory cards, each of capacity 20 MB. A file cannot be split between cards.
Use the first-fit decreasing algorithm to pack the files. State the number of cards used and the contents of each.2 marks
The list 23, 8, 31, 15, 4, 19, 27 is to be sorted into ascending order using quick sort. The pivot is always the middle item of the list or sublist: in position $\frac{N+1}{2}$ if $N$ is odd and $\frac{N+2}{2}$ if $N$ is even. Items smaller than the pivot go to its left and larger items to its right, each keeping their original order.
Show the result of the first pass of quick sort, stating the pivot used.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).