Define an algorithm .

An algorithm is a set of precise instructions which, if followed strictly, will produce the solution to a problem. Algorithms can be carried out by a computer, by a robot or by a person, and the instructions for building a model are an everyday example.

In what three ways may an algorithm be presented?

An algorithm may be presented as a list of instructions in words , as pseudocode , or as a flow chart . Each sets out the same steps in a different way, and the flow chart is the one that shows the order visually.

What do ovals, rectangles and diamonds represent in a flow chart?

An oval marks the start or the end, a rectangle gives an instruction, and a diamond asks a question. The start and end boxes are sometimes called terminations, and question boxes are sometimes called decision boxes.

Which two features of an algorithm make a flow chart a good way to present it?

A flow chart suits an algorithm with conditional instructions, where the answer to a question sends you down one route or another. It also suits one with repetitive stages, because the loop can be seen in the diagram.

Pseudocode is a way of writing an algorithm using a mixture of ordinary words and basic programming commands . It follows no formal programming language, so no knowledge of computer programming is needed in order to read it.

Define the order of an algorithm.

The order of an algorithm is a measure of its efficiency , expressed as a function of the size of the problem . It is found from the maximum number of steps the algorithm can take, which is the worst case.

How does one pass of the bubble sort algorithm work?

Compare the first item with the second, the second with the third, and so on to the end of the working list, swapping any pair that is in the wrong order. A pair of equal items does not count as a swap.

Define the working list in a bubble sort.

The working list is the part of the list that the next pass of the algorithm is applied to. It starts as the whole list and loses one item after each pass, because the item at its end is then known to be in its correct place.

When does a pass of a bubble sort make the maximum possible number of swaps?

When every comparison results in a swap, which happens if the first item on the working list is the largest, for an ascending sort. The whole algorithm makes the most swaps of all when the list starts in reverse order.

True or False? An item that reaches its correct position during a bubble sort is removed from the working list straight away.

False. Only the item at the end of the working list comes off it after each pass. Another item may already be sitting in its correct place, but the algorithm has no way of knowing that yet, so it stays on the working list.

Which item is chosen as the pivot in the quick sort algorithm?

The pivot is the middle item of the sub-list, taken without reordering that sub-list first. On the first pass the sub-list is the whole list, so there is a single pivot, and after that each new sub-list produced has its own.

In a quick sort into ascending order, where do the other items go once a pivot is chosen?

Items less than the pivot are listed before it, and items greater than or equal to the pivot are listed after it. Within each of the two new sub-lists the items keep the order they already had .

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

The algorithm is complete when every item on the original list has been used as a pivot. A pass can produce no reordering at all and still be a genuine pass, because its pivots have now been fixed in place.

True or False? An item equal to the pivot may be placed in either of the two sub-lists.

True. Either side is acceptable, but it is much safer to fix one convention and keep to it, placing equal items with those greater than the pivot every time. Staying consistent is what stops the halves being built one way at one pass and another way at the next.

What is a bin packing algorithm designed to do?

A bin packing algorithm arranges a set of objects into as few bins of equal size as possible. Size may mean length, width, volume or weight, and 'packing' may equally stand for cutting or separating.

True or False? If the lower bound calculation gives 4.85, then the lower bound for the number of bins is 4.

False. The lower bound is 5 , because the number of bins has to be a whole number and 4 bins would not be enough to hold everything. The result is always rounded up , unless it comes out as a whole number already.

How does the first-fit bin packing algorithm place each object?

Take the objects in the order they are listed , and put each one into the first bin that still has room for it. If no bin opened so far has enough room left, start a new bin.

Define a heuristic algorithm.

A heuristic algorithm is one that produces a good solution but not necessarily an optimal one, and not necessarily the only one. The first-fit and first-fit decreasing bin packing algorithms are both heuristic.

Why might first-fit be chosen over first-fit decreasing, and when would the reverse be true?

First-fit is quicker , since the objects need no sorting first, and it is often good enough for practical purposes. First-fit decreasing usually gets closer to the optimal solution, so it is preferred whenever using the fewest bins matters more than speed.

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

The objects are first sorted into decreasing order , and only then placed into bins. The placing rule itself is unchanged, so the only difference is the order in which the objects are dealt with.

How does the full-bin packing algorithm work?

Inspect the list to find combinations of objects that exactly fill a bin , and place each such combination into a bin of its own. Any objects left over afterwards are then packed using the first-fit algorithm.

What is the drawback of the full-bin packing algorithm?

The full-bin combinations have to be found by inspection , which is slow and error-prone when there are many objects. It often produces the optimal solution, so it is a good choice wherever speed does not matter.

How can you show that a bin packing solution is optimal?

Show that the number of bins it uses is equal to the lower bound . No packing can possibly use fewer bins than the lower bound, so matching it proves that no better solution exists.

A LevelFurther MathsEdexcelDecision 1FlashcardsAlgorithms & Graph TheoryAlgorithms

Algorithms (Edexcel A Level Further Maths: Decision 1): Flashcards

Exam code: 9FM0

1/32

0Still learning

Know0

FrontGeneral Algorithms
Define an algorithm.

Was this flashcard helpful?

Cards in this collection (32)

Define an algorithm.
An algorithm is a set of precise instructions which, if followed strictly, will produce the solution to a problem.
Algorithms can be carried out by a computer, by a robot or by a person, and the instructions for building a model are an everyday example.
In what three ways may an algorithm be presented?
An algorithm may be presented as a list of instructions in words, as pseudocode, or as a flow chart.
Each sets out the same steps in a different way, and the flow chart is the one that shows the order visually.
What do ovals, rectangles and diamonds represent in a flow chart?
An oval marks the start or the end, a rectangle gives an instruction, and a diamond asks a question.
The start and end boxes are sometimes called terminations, and question boxes are sometimes called decision boxes.
Which two features of an algorithm make a flow chart a good way to present it?
A flow chart suits an algorithm with conditional instructions, where the answer to a question sends you down one route or another.
It also suits one with repetitive stages, because the loop can be seen in the diagram.
What is pseudocode?
Pseudocode is a way of writing an algorithm using a mixture of ordinary words and basic programming commands.
It follows no formal programming language, so no knowledge of computer programming is needed in order to read it.
Fill in the two missing pseudocode commands.
The command $______$ assigns or updates a value to a variable, and the command $______$ gives the integer part of a value.
The completed sentence is:
The command Let assigns or updates a value to a variable, and the command Int gives the integer part of a value.
Other commands used in pseudocode include Input, If, While and Output.
Define the order of an algorithm.
The order of an algorithm is a measure of its efficiency, expressed as a function of the size of the problem.
It is found from the maximum number of steps the algorithm can take, which is the worst case.
What does it mean to say an algorithm has quadratic order, and what does that predict?
Quadratic order means the number of steps is a function of the square of the size of the input data.
So doubling the input size multiplies the approximate running time by $2^{2} = 4$ , and the same proportional reasoning gives 2 for linear order and $2^{3} = 8$ for cubic.
An algorithm of order $\sqrt{n}$ takes 5 seconds on an input of size 20. Estimate the time for an input of size 80.
The input size is multiplied by 4, so the time is multiplied by $\sqrt{4} = 2$ , giving about 10 seconds.
The answer is only an estimate, because it uses the order alone and the order describes the worst case.
True or False?
Two algorithms that both have quadratic order will take the same time to complete.
False.
The exact functions may differ, so one algorithm might take $\frac{1}{2} n (n + 1)$ steps while another takes $\frac{1}{2} n (n - 1)$ .
Both of those are quadratic, but for the same value of $n$ they give different numbers of steps.
How does one pass of the bubble sort algorithm work?
Compare the first item with the second, the second with the third, and so on to the end of the working list, swapping any pair that is in the wrong order.
A pair of equal items does not count as a swap.
Define the working list in a bubble sort.
The working list is the part of the list that the next pass of the algorithm is applied to.
It starts as the whole list and loses one item after each pass, because the item at its end is then known to be in its correct place.
How do you know that a bubble sort is complete?
Either a whole pass has been carried out with no swaps, or the $(n - 1)$ th pass has been completed.
After that many passes only one item would be left on the working list, so no further comparison is possible.
Complete the maximum total number of comparisons made by a bubble sort of $n$ items:
$\sum_{r = 1}^{n - 1} r = \frac{1}{2} n (______)$
The completed result is:
$\sum_{r = 1}^{n - 1} r = \frac{1}{2} n (n - 1)$
Because this is a quadratic function of $n$ , bubble sort is said to be of quadratic order.
How many comparisons are made in the $k$ th pass of a bubble sort of $n$ items?
There are $n - k$ comparisons.
The number of comparisons in a pass is always one less than the number of items on the working list, and on the $k$ th pass that list holds $n - k + 1$ items.
When does a pass of a bubble sort make the maximum possible number of swaps?
When every comparison results in a swap, which happens if the first item on the working list is the largest, for an ascending sort.
The whole algorithm makes the most swaps of all when the list starts in reverse order.
True or False?
An item that reaches its correct position during a bubble sort is removed from the working list straight away.
False.
Only the item at the end of the working list comes off it after each pass.
Another item may already be sitting in its correct place, but the algorithm has no way of knowing that yet, so it stays on the working list.
Which item is chosen as the pivot in the quick sort algorithm?
The pivot is the middle item of the sub-list, taken without reordering that sub-list first.
On the first pass the sub-list is the whole list, so there is a single pivot, and after that each new sub-list produced has its own.
In a sub-list of $N$ items the middle item is at position $\frac{N + 1}{2}$ when $N$ is odd. Complete the position when $N$ is even:
$\frac{N +______}{2}$
The completed position is:
$\frac{N + 2}{2}$
So a sub-list of 6 items takes the 4th item as its pivot, and a sub-list of 9 items takes the 5th.
In a quick sort into ascending order, where do the other items go once a pivot is chosen?
Items less than the pivot are listed before it, and items greater than or equal to the pivot are listed after it.
Within each of the two new sub-lists the items keep the order they already had.
How do you know that the quick sort algorithm is complete?
The algorithm is complete when every item on the original list has been used as a pivot.
A pass can produce no reordering at all and still be a genuine pass, because its pivots have now been fixed in place.
True or False?
An item equal to the pivot may be placed in either of the two sub-lists.
True.
Either side is acceptable, but it is much safer to fix one convention and keep to it, placing equal items with those greater than the pivot every time.
Staying consistent is what stops the halves being built one way at one pass and another way at the next.
What is a bin packing algorithm designed to do?
A bin packing algorithm arranges a set of objects into as few bins of equal size as possible.
Size may mean length, width, volume or weight, and 'packing' may equally stand for cutting or separating.
Complete the calculation that gives the lower bound for the number of bins:
$lower bound \geq \frac{total size of all objects}{______}$
The completed calculation is:
$lower bound \geq \frac{total size of all objects}{size of one bin}$
The same calculation gives the lower bound whichever bin packing algorithm is going to be used.
True or False?
If the lower bound calculation gives 4.85, then the lower bound for the number of bins is 4.
False.
The lower bound is 5, because the number of bins has to be a whole number and 4 bins would not be enough to hold everything.
The result is always rounded up, unless it comes out as a whole number already.
How does the first-fit bin packing algorithm place each object?
Take the objects in the order they are listed, and put each one into the first bin that still has room for it.
If no bin opened so far has enough room left, start a new bin.
Define a heuristic algorithm.
A heuristic algorithm is one that produces a good solution but not necessarily an optimal one, and not necessarily the only one.
The first-fit and first-fit decreasing bin packing algorithms are both heuristic.
Why might first-fit be chosen over first-fit decreasing, and when would the reverse be true?
First-fit is quicker, since the objects need no sorting first, and it is often good enough for practical purposes.
First-fit decreasing usually gets closer to the optimal solution, so it is preferred whenever using the fewest bins matters more than speed.
How does the first-fit decreasing algorithm differ from the ordinary first-fit algorithm?
The objects are first sorted into decreasing order, and only then placed into bins.
The placing rule itself is unchanged, so the only difference is the order in which the objects are dealt with.
How does the full-bin packing algorithm work?
Inspect the list to find combinations of objects that exactly fill a bin, and place each such combination into a bin of its own.
Any objects left over afterwards are then packed using the first-fit algorithm.
What is the drawback of the full-bin packing algorithm?
The full-bin combinations have to be found by inspection, which is slow and error-prone when there are many objects.
It often produces the optimal solution, so it is a good choice wherever speed does not matter.
How can you show that a bin packing solution is optimal?
Show that the number of bins it uses is equal to the lower bound.
No packing can possibly use fewer bins than the lower bound, so matching it proves that no better solution exists.

Sign up to unlock flashcards

By signing up you agree to our Terms and Privacy Policy

Next:Graphs