Decision 1 Chapter 1 - Algorithms

Question 1

Flow chart syntax - Start / End

Answer 1

Box with rounded edges

Question 2

Flow chart syntax - Instruction

Answer 2

Rectangle

Question 3

Flow chart syntax - Decision

Answer 3

Diamond

Two arrows coming from it with “yes” and “no”

Question 4

Bubble sort algorithm

Answer 4

1 - Starting at he beginning of the list pass through and compare adjacent values. For each pair:
- If in order leave
- If not in order swap
2 - When at the end of the list repeat step 1
3 - When a pass is completed without any swaps the list is in order

Question 5

Quick sort algorithm

Answer 5

1 - Choose the item at the middle of the list to be the pivot (if the list has an even length the item to the right of the middle)
2 - Write down all the numbers less than the pivot, keeping their order, in a sub list
3- Write down the pivot
4- Write down the remaining items in a sub list
5 - Apply steps 1-4 to each sub list recursively
6 - When all items are pivots, stop

Question 6

Binary search algorithm

Answer 6

1 - Select the middle item in the list
2 - If it is the target the search is complete
3 - If the item is larger than the target delete the second half of the list including the selected item
4 - If the item is smaller than the target delete the first half of the list including the selected item
5 - Repeat steps 1-4 until either the target is found or not

Question 7

What bubble sort and quicksort do

Answer 7

Order a list

Question 8

What binary search does

Answer 8

Checks whether a value is in an ORDERED list

Question 9

First fit algorithm

Answer 9

1 - Take the items in the order given

2 - Place each item in the first available bin that will take it

Question 10

Advantage of first fit algorithm

Answer 10

It is quick and easy to do

Question 11

Disadvantage of first fit algorithm

Answer 11

It is not likely to give a good solution

Question 12

First fit decreasing algorithm

Answer 12

1 - Reorder the list so that it is in descending order

2 - Place each item at the first available bin that will take it

Question 13

Advantage of first fit decreasing algorithm

Answer 13

You usually get a fairly good solution and it is easy to do

Question 14

Disadvantage of first fit decreasing algorithm

Answer 14

You may not get an optimal solution

Question 15

Full bin packing algorithm

Answer 15

1 - Use observation to find combinations of items that will fill a bin and pack these first
2- Pack any remaining items with first fit

Question 16

Advantage of full bin packing algorithm

Answer 16

You usually get a good solution

Question 17

Disadvantage of full bin packing algorithm

Answer 17

It is difficult to do especially with plentiful or awkward numbers