Define an algorithm .

An algorithm is a set of precise instructions which, if followed exactly, produces the solution to a problem. Because the instructions leave nothing to judgement, a computer or a person can carry them out without needing to understand the problem itself.

In what two ways can an algorithm be presented?

As a text-based algorithm , which is a list of instructions written out in sentences and usually numbered, or as a flow chart , which sets the same instructions out diagrammatically. A flow chart makes the order of the instructions visible, along with any part that has to be repeated.

What do the flow chart commands 'Input', 'Let' and 'Output' each tell you to do?

Input supplies the algorithm with its starting data, Let assigns or updates the value of a variable, and Output (or Print) tells you to write the answer down. The output has to be read off the instruction that names it, and is not simply whatever number happens to be last in your working.

You are asked to describe what an algorithm shown as a flow chart achieves. Where should you look first?

Look at the final instructions , and particularly at whatever the chart outputs, since that is what the whole algorithm was built to produce. Working backwards from the output usually makes the purpose of the loop above it clear.

What does a sorting algorithm do?

A sorting algorithm arranges a list of items into ascending or descending order. The items are usually numbers, such as weights, lengths, scores or times, but they can equally be letters or words.

What happens during one pass of the bubble sort algorithm?

Each pair of neighbouring items on the working list is compared in turn, working from left to right , and the two are swapped whenever they are out of order. A pair of equal items is already in order, so it is not swapped and does not add to the swap count.

How do you know when the bubble sort algorithm is complete?

It is complete as soon as a pass produces no swaps , because that means every neighbouring pair is already in the right order. It is also complete once only one item would be left on the working list, since a single item cannot be out of order.

Define the working list in a bubble sort.

The working list is the part of the list that the next pass is actually applied to, meaning the items not yet known to be in their final place. It starts as the whole list and loses one item after every pass, because each pass carries the largest remaining item to the end, or the smallest if the sort is descending.

True or False? A bubble sort can need the maximum possible number of passes even when only one item is out of place.

True. An item sitting at the very end of the list that belongs at the very start moves only one place closer with each pass. The rest of the list already being in order does nothing to speed that item up, so the sort runs to the full number of passes.

What happens during one pass of the quick sort algorithm?

Every sub-list is split into two halves around a pivot , with the items smaller than the pivot on one side and the larger ones on the other. For an ascending sort the smaller items go before the pivot, and within each half the items keep the order they were already in.

True or False? In a quick sort, the pivot is found by putting the sub-list into order and then taking the middle value.

False. The pivot is whichever item sits in the middle position of the sub-list as it currently stands, with no reordering at all. Sorting the sub-list first would defeat the purpose, since sorting it is exactly what the algorithm is trying to achieve.

In a quick sort, where should an item equal to the pivot be placed?

Either side is valid, but for consistency always put it in the half holding the items greater than or equal to the pivot. Keeping to one convention means your sub-lists match the expected working at every later pass.

How do you know when the quick sort algorithm is complete?

It is complete once every item on the original list has been a pivot , because an item that has served as a pivot is already in its final position. At that point no sub-list has more than one item left in it.

A pivot turns out to be the lowest item in its sub-list. What happens on that side of the pivot?

No new sub-list is created there, because there are no items smaller than the pivot to form one. The next pass simply has one fewer sub-list to work on, which is why the number of pivots does not always double from one pass to the next.

Define the binary search algorithm .

The binary search algorithm inspects an ordered list to decide whether a specified item is in it, and if it is, to find where it is. The list must already be sorted for the algorithm to be used at all.

Why must a list be in order before a binary search can be run on it?

Because the method works by comparing the target with a middle item and then discarding one whole half of the list. That step is only valid if everything on one side of the middle item comes before it and everything on the other side comes after it, which is exactly what being ordered guarantees.

The item being searched for comes before the pivot. What does a binary search do next?

It rejects the pivot and everything after it, and carries on searching only the sub-list before the pivot. Had the item come after the pivot instead, the sub-list before it would have been the part rejected.

True or False? A binary search can only report that an item is missing after it has compared the item with every entry in the list.

False. Each comparison lets the search throw away roughly half of the items still in play, so only a handful of comparisons are needed even for a long list. For example, a list of eight names is settled in three comparisons.

Define a bin packing algorithm .

A bin packing algorithm organises a collection of objects into as few bins as possible , where every bin is the same size. 'Size' can mean length, weight, volume or any other capacity, so the objects might be pallets loaded into lorries or lengths of cable cut from reels.

How does the first-fit bin packing algorithm decide where each object goes?

Objects are taken in the order they are presented , and each one is put into the first bin that still has room for it. A new bin is opened only when no existing bin has enough capacity left.

What is the main advantage of the first-fit bin packing algorithm?

Speed , because the objects do not have to be sorted into any order before the packing begins. For many business or practical purposes a quick workable answer is worth more than the very best one.

True or False? Each of the three bin packing algorithms has its own lower bound for the number of bins.

False. There is only one lower bound, and it depends on the objects and the bin size rather than on which method is used. No algorithm can beat it, because the objects simply will not fit into fewer bins than that however cleverly they are arranged.

How does the first-fit decreasing algorithm differ from the ordinary first-fit algorithm?

The objects are first arranged into decreasing order , largest first, and only then packed by the first-fit rule. Placing the awkward large objects while every bin is still empty usually gets much closer to the optimal number of bins.

How does the full-bin packing algorithm work?

Combinations of objects that exactly fill a bin are identified by inspection and placed together. Whatever objects are left over are then packed using the first-fit algorithm.

Full-bin packing often reaches the optimal answer. Why is it still not always the algorithm to choose?

Because the full-bin combinations have to be spotted by inspection , which becomes slow and easy to get wrong once there are many objects. Where speed matters more than using the fewest bins, first-fit is the better choice.

International A Level (IAL)MathsEdexcelDecision 1FlashcardsAlgorithms & Graph TheoryAlgorithms

Algorithms (Edexcel International A Level (IAL) Maths: Decision 1): Flashcards

Exam code: YMA01

1/40

0Still learning

Know0

FrontGeneral Algorithms
Define an algorithm.

Was this flashcard helpful?

Cards in this collection (40)

Define an algorithm.
An algorithm is a set of precise instructions which, if followed exactly, produces the solution to a problem.
Because the instructions leave nothing to judgement, a computer or a person can carry them out without needing to understand the problem itself.
In what two ways can an algorithm be presented?
As a text-based algorithm, which is a list of instructions written out in sentences and usually numbered, or as a flow chart, which sets the same instructions out diagrammatically.
A flow chart makes the order of the instructions visible, along with any part that has to be repeated.
Complete the meanings of the three box shapes used in a flow chart:
An oval marks the $______$ or end of the algorithm, a rectangle holds an $______$ to carry out, and a diamond holds a $______$ to answer.
The completed sentence is:
An oval marks the start or end of the algorithm, a rectangle holds an instruction to carry out, and a diamond holds a question to answer.
The shape tells you what kind of command you are looking at before you have read a word of it.
What kinds of instruction make a flow chart a better way to present an algorithm than a list of sentences?
Conditional instructions, such as 'is $a > b$ ?', where a yes sends you to one instruction and a no sends you to a different one.
Also repetitive parts, since a flow chart can loop an arrow back to an earlier box instead of writing the same instructions out again.
True or False?
An algorithm always produces the best possible solution to the problem it is applied to.
False.
Many algorithms are built to give a solution that is good enough rather than the very best one, because a real problem can be far too complex to solve exactly.
A route-finding algorithm might return a route $200$ miles longer than the shortest, and on a very long journey finding it quickly can matter more than that inaccuracy.
What do the flow chart commands 'Input', 'Let' and 'Output' each tell you to do?
Input supplies the algorithm with its starting data, Let assigns or updates the value of a variable, and Output (or Print) tells you to write the answer down.
The output has to be read off the instruction that names it, and is not simply whatever number happens to be last in your working.
You are asked to describe what an algorithm shown as a flow chart achieves. Where should you look first?
Look at the final instructions, and particularly at whatever the chart outputs, since that is what the whole algorithm was built to produce.
Working backwards from the output usually makes the purpose of the loop above it clear.
When following a flow chart, why might a column of the table of values be left mostly empty?
Because a value only gets a new entry on a row when the algorithm actually changes it.
An input such as $n$ that is never updated appears once, in the first row, and every later row leaves that column blank.
What does a sorting algorithm do?
A sorting algorithm arranges a list of items into ascending or descending order.
The items are usually numbers, such as weights, lengths, scores or times, but they can equally be letters or words.
What happens during one pass of the bubble sort algorithm?
Each pair of neighbouring items on the working list is compared in turn, working from left to right, and the two are swapped whenever they are out of order.
A pair of equal items is already in order, so it is not swapped and does not add to the swap count.
How do you know when the bubble sort algorithm is complete?
It is complete as soon as a pass produces no swaps, because that means every neighbouring pair is already in the right order.
It is also complete once only one item would be left on the working list, since a single item cannot be out of order.
Define the working list in a bubble sort.
The working list is the part of the list that the next pass is actually applied to, meaning the items not yet known to be in their final place.
It starts as the whole list and loses one item after every pass, because each pass carries the largest remaining item to the end, or the smallest if the sort is descending.
A bubble sort is applied to a list of $n$ items. Complete the two results:
The maximum number of passes needed is $______$ and the greatest number of swaps possible in a single pass equals the number of $______$ made in that pass.
The completed results are:
The maximum number of passes needed is $n - 1$ and the greatest number of swaps possible in a single pass equals the number of comparisons made in that pass.
The whole algorithm needs the greatest number of swaps when the list starts in exactly reverse order.
A bubble sort is applied to a list of $n$ items. What is the greatest number of comparisons the whole algorithm can involve?
The comparisons total $(n - 1) + (n - 2) + \dots + 2 + 1$ , which sums to $\frac{1}{2} n (n - 1)$ .
Each pass compares one fewer pair than the pass before, because the working list has just lost an item.
True or False?
A bubble sort can need the maximum possible number of passes even when only one item is out of place.
True.
An item sitting at the very end of the list that belongs at the very start moves only one place closer with each pass.
The rest of the list already being in order does nothing to speed that item up, so the sort runs to the full number of passes.
What happens during one pass of the quick sort algorithm?
Every sub-list is split into two halves around a pivot, with the items smaller than the pivot on one side and the larger ones on the other.
For an ascending sort the smaller items go before the pivot, and within each half the items keep the order they were already in.
Complete the rule for finding the pivot in a quick sort, for a sub-list of $n$ items:
$position of pivot = \frac{______}{2}, rounded up$
The completed rule is:
$position of pivot = \frac{n + 1}{2}, rounded up$
So a sub-list of $8$ items takes its $5$ th item as the pivot, since $\frac{9}{2} = 4.5$ rounds up to $5$ .
True or False?
In a quick sort, the pivot is found by putting the sub-list into order and then taking the middle value.
False.
The pivot is whichever item sits in the middle position of the sub-list as it currently stands, with no reordering at all.
Sorting the sub-list first would defeat the purpose, since sorting it is exactly what the algorithm is trying to achieve.
In a quick sort, where should an item equal to the pivot be placed?
Either side is valid, but for consistency always put it in the half holding the items greater than or equal to the pivot.
Keeping to one convention means your sub-lists match the expected working at every later pass.
How do you know when the quick sort algorithm is complete?
It is complete once every item on the original list has been a pivot, because an item that has served as a pivot is already in its final position.
At that point no sub-list has more than one item left in it.
A pivot turns out to be the lowest item in its sub-list. What happens on that side of the pivot?
No new sub-list is created there, because there are no items smaller than the pivot to form one.
The next pass simply has one fewer sub-list to work on, which is why the number of pivots does not always double from one pass to the next.
Define the binary search algorithm.
The binary search algorithm inspects an ordered list to decide whether a specified item is in it, and if it is, to find where it is.
The list must already be sorted for the algorithm to be used at all.
Why must a list be in order before a binary search can be run on it?
Because the method works by comparing the target with a middle item and then discarding one whole half of the list.
That step is only valid if everything on one side of the middle item comes before it and everything on the other side comes after it, which is exactly what being ordered guarantees.
In a binary search, how do you find the position of the pivot in a sub-list?
Add the positions of the first and last items of the sub-list, divide by $2$ , and round up if the answer is not a whole number.
For a sub-list running from position $6$ to position $8$ the pivot is therefore the $7$ th item.
A binary search begins on a list of $8$ items. Which item is compared with the target first?
The $5$ th item, since the pivot position works out as $\frac{1 + 8}{2} = 4.5$ , which rounds up to $5$ .
Every binary search starts at the middle of the whole list rather than at either end of it.
The item being searched for comes before the pivot. What does a binary search do next?
It rejects the pivot and everything after it, and carries on searching only the sub-list before the pivot.
Had the item come after the pivot instead, the sub-list before it would have been the part rejected.
Complete the two ways a binary search can finish:
The search ends either when the item has been $______$ in the list, or when it has been shown that the item is $______$ there at all.
The completed sentence is:
The search ends either when the item has been found in the list, or when it has been shown that the item is not there at all.
The second case is reached once the sub-list has been cut down until there is nothing left that could hold the item.
True or False?
A binary search can only report that an item is missing after it has compared the item with every entry in the list.
False.
Each comparison lets the search throw away roughly half of the items still in play, so only a handful of comparisons are needed even for a long list.
For example, a list of eight names is settled in three comparisons.
Define a bin packing algorithm.
A bin packing algorithm organises a collection of objects into as few bins as possible, where every bin is the same size.
'Size' can mean length, weight, volume or any other capacity, so the objects might be pallets loaded into lorries or lengths of cable cut from reels.
Complete the names of the three bin packing algorithms:
The $______$ algorithm, the first-fit $______$ algorithm, and the $______$ packing algorithm.
The completed list is:
The first-fit algorithm, the first-fit decreasing algorithm, and the full-bin packing algorithm.
All three pack objects into bins that are every one of them the same size.
How does the first-fit bin packing algorithm decide where each object goes?
Objects are taken in the order they are presented, and each one is put into the first bin that still has room for it.
A new bin is opened only when no existing bin has enough capacity left.
What is the main advantage of the first-fit bin packing algorithm?
Speed, because the objects do not have to be sorted into any order before the packing begins.
For many business or practical purposes a quick workable answer is worth more than the very best one.
How do you find a lower bound for the number of bins needed?
Divide the total capacity of all the objects by the size of one bin, then round the answer up to the next whole number.
A value of $4.85$ therefore gives a lower bound of $5$ bins, since four bins could not possibly hold everything.
True or False?
Each of the three bin packing algorithms has its own lower bound for the number of bins.
False.
There is only one lower bound, and it depends on the objects and the bin size rather than on which method is used.
No algorithm can beat it, because the objects simply will not fit into fewer bins than that however cleverly they are arranged.
How does the first-fit decreasing algorithm differ from the ordinary first-fit algorithm?
The objects are first arranged into decreasing order, largest first, and only then packed by the first-fit rule.
Placing the awkward large objects while every bin is still empty usually gets much closer to the optimal number of bins.
A bin packing algorithm has used $5$ bins, and the lower bound is also $5$ . What can you conclude?
The solution is optimal, since no arrangement at all can manage fewer than $5$ bins and this one achieves exactly that.
Matching the lower bound is the only way to be certain an answer is the best possible.
First-fit has used $6$ bins but the lower bound is $5$ . Does that mean a mistake has been made?
No mistake need have been made, and the packing can be entirely correct.
First-fit is not guaranteed to reach the fewest possible bins, so a gap between its answer and the lower bound is an ordinary outcome rather than a sign of an error.
How does the full-bin packing algorithm work?
Combinations of objects that exactly fill a bin are identified by inspection and placed together.
Whatever objects are left over are then packed using the first-fit algorithm.
Full-bin packing often reaches the optimal answer. Why is it still not always the algorithm to choose?
Because the full-bin combinations have to be spotted by inspection, which becomes slow and easy to get wrong once there are many objects.
Where speed matters more than using the fewest bins, first-fit is the better choice.
Two students apply the same bin packing algorithm and produce different arrangements, both using $5$ bins. Can both be right?
Both arrangements can be correct.
These algorithms are heuristic, which means they guarantee a workable answer rather than a unique one, and the full-bin method in particular can yield several different valid sets of full bins.

Sign up to unlock flashcards

By signing up you agree to our Terms and Privacy Policy

Next:Graphs