Decision Chapter 1: Algorithms

24 flashcards · Mathematics · by TheoTyson

1. What is an algorithm?

   Finite sequence of step by step instructions carried out to solve a problem.

2. What is the symbol for start / end in a flow chart?

3. What is the symbol for an instruction in a flow chart?

4. What is the symbol for a decision in a flow chart?

5. What is the function of the bubble sort algorithm?

   Sorting an unordered list.

6. What is the bubble sort algorithm?

   Start at the beginning of the list and compare adjacent items. If they are in order, leave them. If they are not in order, swap them. When you get to the end, the last item will be in its final position. If you have made swaps, repeat step 1. When a pass is completed without swaps every item is in position.

7. What is a pass?

   When you get to the end of the list.

8. What is the working list?

   The elements of the list that are not in the right position.

9. What is the sorted list?

   The elements of the list that are in the right position.

10. What is the function of the quick sort algorithm?

    Sorting an unordered list.

11. What is the quick sort algorithm?

    Choose the item at the midpoint of the list to be the first pivot. Write down all the items that are less than the pivot, keeping their order, in a sub list. Write down the pivot. Write down the remaining items that are greater than the pivot in a sub list. Apply steps 1 to 4 for each sub list. When all items have been chose as pivots, stop.

12. What is the function of the bin packing algorithm?

    Finding the minimum number of bins to stack all objects.

13. What is the lower bound of bins?

    Sum of the heights divided by the bin size rounded up.

14. What is the optimal solution?

    A solution that cannot be improved upon.

15. What is the first fit algorithm?

    Take the items in the order given. Place each item in the first available bin that can take it. Start from bin 1 each time.

16. What are the advantages and disadvantages of the first fit algorithm?

    Advantage - It is quick to implement. Disadvantage - It is unlikely to lead to a good solution.

17. What is the first fit decreasing algorithm?

    Sort the items so that they are in descending order. Apply the first fit algorithm to the reordered list.

18. What are the advantages and disadvantages of the first fit decreasing algorithm?

    Advantages - You usually get a fairly good solution. It is easy to implement. Disadvantage - You may not get an optimal solution.

19. What is the full bin packing algorithm?

    Use observation to find combinations of items that will fill a bin. Pack these items first. Any remaining items are packed using the first fit algorithm.

20. What are the advantages and disadvantages of the full bin packing algorithm?

    You usually get a good solution. It is difficult to implement, especially when the numbers are plentiful and awkward.

21. What is the order of an algorithm / run time?

    How changes in size of the problem affect time taken for its completion.

22. What is the order of a bubble sort?

    n2−n2\frac{n^2-n}{2}2n2−n​

23. What is the order of a quick sort?

    nlog⁡nn \log{n}nlogn

24. How do you work out the new time taken given an increase in size from m\text{m}m to n\text{n}n ?

    new time\text{new time}new time = (mn)order(\frac{m}{n})^\text{order}(nm​)order x original time\text{original time}original time