Algorithms
An algorithm is a precise set of instructions which, when followed, will solve a problem. They can be presented in various forms, e.g. words, pictures, flow diagrams.
Tracing an algorithm means displaying how the value of variables change as a computer runs a program.
If you are asked to state values of the variables for which the algorithm would fail – you will usually need to state inequalities.
If you are asked to change/add additional commands to the algorithm – make sure you give the line an appropriate number.
The algorithms you should know:
First-fit: Put each object in the first available bin in which it will fit.
First-fit decreasing: Put object in order from largest to smallest then do first-fit.
Full-bin combinations: Find combinations of objects to fill bins, then do first-fit for remaining objects.
A few examples of other algorithms (from Wikipedia):
Bubble Sort
For a set of numbers, the first number is compared to the number to the right of it.
13, 2, 4, 3, 82
13>2 so it moves to the right.
2, 13, 4, 3, 82
13>4 so it moves to the right.
2, 4, 13, 3, 82
13>3 so it moves to the right.
2, 4, 3, 13, 82
13<82 so it stays.
At the end of first pass: 2, 4, 3, 13, 82
At the end of second pass: 2, 4, 3, 13, 82
At the end of third pass: 2, 3, 4, 13 82
This set only needed 2 passes, but on a larger data set it can get quite large. The maximum number of passes is equal to the size of the set, provided the set items are unique.
Shuttle Sort
From a set of numbers, one selects the first two numbers and underlines them. These two are the ones that get sorted in the first pass.
In the second pass, the range of numbers to be sorted increases by one, so the first three numbers are compared and sorted into their order.
And so forth until all the numbers are covered in the range and sorted.
1st pass - 23, 2, 4, 8, 9 - 23>2 so 2 is sorted to the left.
2nd pass - 2, 23, 4, 8, 9 - 23>4 so 4 is sorted to the left.
3rd pass - 2, 4, 23, 8, 9 - The numbers are sorted
4th pass - 2, 4, 8, 23, 9 - The numbers are sorted
Final set of numbers = 2, 4, 8, 9, 23 - The numbers are sorted
Shell Sort
Divide the set of numbers in n/2 sublists.
The sublists are shuttle sorted.
The data range is recombined and split into half the number of the previous sublists.
The data range are shuttle sorted again.
Repeat until the number of sublists = 2
Tracing an algorithm means displaying how the value of variables change as a computer runs a program.
- List the variables used (in the order they are introduced) as column headings in a table;
- If the PRINT command is used – write clearly “PRINT:” and then list the words/values the computer would print;
- There will be the use of inequalities;
- When you think you have finished tracing – start again and check the values you have listed – particularly the last ones to make sure you didn’t need to repeat again.
If you are asked to state values of the variables for which the algorithm would fail – you will usually need to state inequalities.
If you are asked to change/add additional commands to the algorithm – make sure you give the line an appropriate number.
The algorithms you should know:
First-fit: Put each object in the first available bin in which it will fit.
First-fit decreasing: Put object in order from largest to smallest then do first-fit.
Full-bin combinations: Find combinations of objects to fill bins, then do first-fit for remaining objects.
A few examples of other algorithms (from Wikipedia):
Bubble Sort
For a set of numbers, the first number is compared to the number to the right of it.
13, 2, 4, 3, 82
13>2 so it moves to the right.
2, 13, 4, 3, 82
13>4 so it moves to the right.
2, 4, 13, 3, 82
13>3 so it moves to the right.
2, 4, 3, 13, 82
13<82 so it stays.
At the end of first pass: 2, 4, 3, 13, 82
At the end of second pass: 2, 4, 3, 13, 82
At the end of third pass: 2, 3, 4, 13 82
This set only needed 2 passes, but on a larger data set it can get quite large. The maximum number of passes is equal to the size of the set, provided the set items are unique.
Shuttle Sort
From a set of numbers, one selects the first two numbers and underlines them. These two are the ones that get sorted in the first pass.
In the second pass, the range of numbers to be sorted increases by one, so the first three numbers are compared and sorted into their order.
And so forth until all the numbers are covered in the range and sorted.
1st pass - 23, 2, 4, 8, 9 - 23>2 so 2 is sorted to the left.
2nd pass - 2, 23, 4, 8, 9 - 23>4 so 4 is sorted to the left.
3rd pass - 2, 4, 23, 8, 9 - The numbers are sorted
4th pass - 2, 4, 8, 23, 9 - The numbers are sorted
Final set of numbers = 2, 4, 8, 9, 23 - The numbers are sorted
Shell Sort
Divide the set of numbers in n/2 sublists.
The sublists are shuttle sorted.
The data range is recombined and split into half the number of the previous sublists.
The data range are shuttle sorted again.
Repeat until the number of sublists = 2
