Decision 1 - Algorithms Flashcards
What is an algorithm?
An algorithm is a finite sequence of step-by-step instructions carried out to solve a problem.
Describe the different shapes of boxes in flow charts.
Rounded end boxes are start and end points.
Straight edged rectangular boxes are instructions.
Diamonds are decisions/questions.
Describe the methods or ordering a list.
Unordered lists can be sorted using a bubble sort or a quick sort.
Lists can be ordered into ascending or descending order.
Describe the bubble sort algorithm.
In a bubble sort, you can compare adjacent items in a list.
The algorithm is;
1) Start at the beginning of the working list and move from left to right comparing adjacent items.
•If they are in order leave them.
•If they aren’t in order, leave them.
2) When you get to the end of the working list, the last item will be in its final position. This item is then no longer in the working list.
If you have made some swaps in the last pass, repeat step 1.
When a pass is completed without any swaps, every item is in its final position and the list is in order.
What is a pass?
Going from the start to the end of the working list. The length of the working list reduces by 1 with each pass.
Describe the quick sort algorithm.
In a quick sort algorithm, you select a pivot, then split the items into two sub-lists.
The algorithm is;
1) Choose the item at the midpoint of the list to be the first pivot.
2) Write down all the items that are less than the pivot, keeping their order, in a sub-list.
3) Write down the pivot.
4) Write down the remaining items, those greater than the pivot) in a sub-list.
5) Apply steps 1 to 4 to each sub-list.
6) When all items have been chosen as pivots, stop.
Where would you place an item in a quick sort if it has the same value as the pivot?
It can go in either sub-list.
What are the bin-packing algorithms?
The three bin-packing algorithms are: first-fit, first-fit decreasing and full-bins.
It is useful first to find a lower band for the number of bins needed. There is no guarantee that you will be able to pack the items into this number of bins, but it will tell you if you have found an optimal solution.
What is an optimal solution?
An optimal solution is one that cannot be improved upon.
What is an optimal solution in the context of bin-packing?
An optimal solution will use the smallest number of bins.
Describe the first-fit algorithm.
The first-fit algorithm works by considering items in the order they are given.
The algorithm is;
1) Take the items in the order given.
2) Place each item in the first available bin that can take it. Start from bin 1 each time.
Describe the first-fit decreasing algorithm.
The first-fit decreasing algorithm requires the items to be in descending order before applying the algorithm.
The algorithm is;
1) Sort the items so that they are in descending order.
2) Apply the first-fit algorithm to the reordered list.
Describe the full-bin packing algorithm.
Full-bin packing uses inspection to select items that will combine to fill bins. Remaining items are packed using the first-fit algorithm.
The algorithm is;
1) Use observation to find combinations of items that will fill a bin. Pack these items first.
2) Any remaining items are packed using the first-fit algorithm.
What is the order of algorithm?
The order of an algorithm, sometimes called the complexity of the algorithm, describes how changes in the size of a problem affect the approximate time taken for its completion, this is sometimes called the run time of the algorithm.
It can be described as a function of its size. If an algorithm has order f(𝑛), then increasing the size of the problem from 𝑛 to 𝑚 will increase the runtime of the algorithm by a factor of approximately f(𝑚)/f(𝑛).
What is the order of a bubble sort?
½𝑛(𝑛-1) or ½𝑛²-½𝑛. The bubble sort algorithm is said to have a quadratic order.
