Algorithms

Question 1

What are the 3 steps to ‘Bubble sort’?

Answer 1

1. Start at the beginning of the list. Pass though the list & compare values. If not in order swap them
2. When you get to the end of the list, repeat step 1
3. When a pass is completed without any swaps, the list is ordered

Question 2

What are the 6 steps to ‘Quick sort’?

Answer 2

1. Choose the item in the middle of the list as 1st pivot
2. Write down all the items that are less than the pivot, keeping them in order, into a sub-list
3. Write down the pivot
4. Write down the items that are greater than the pivot, keeping them in order, into a sub-list
5. Apply step 1-4 to each sub-list
6. When all have been chosen as pivots, STOP

Question 3

What do you have to do before a binary search?

Answer 3

Order the list

Question 4

What are the 3 steps to do a ‘binary search’?

Answer 4

1. Select the middle item
   n+1 / 2
2. If T is before M it can’t be in second half of list so it is discarded. If T is after M it can’t be in the first half of list so it is discarded
3. Repeat 1-2 to remaining list until T is found

Question 5

What are the 3 bin packing algorithms?

Answer 5

1. First-fit
2. First-fit decreasing
3. Full-bin

Question 6

What are the 2 steps to do a ‘first-fit’ bin sort?

Answer 6

1. Take the items in order given

2. Place each item into 1at available bin. Start from bin 1 each time

Question 7

What is 1 strength and 1 weakness of the first-fit algorithm

Answer 7

Strength:
- Quick

Weakness:
- Not likely to lead to a good solution

Question 8

What are the 2 steps to do a ‘first-fit decreasing’ bin sort?

Answer 8

1. Reorder the items so that they are in decreasing order

2. Apply he first-fit algorithm

Question 9

What is 1 strength and 1 weakness of a ‘first-fit decreasing’ algorithm?

Answer 9

Strength:

• Easy to do
• Usually get good solution

Weakness:
- May not get optimal solution

Question 10

What are the 2 steps to do a ‘full-bin’ bin sort?

Answer 10

1. Use observation to find combination of items that will fill a bin
2. Any remaining items are packed using ‘first-fit’ algorithm

Question 11

What is 1 strength and 1 weakness of ‘full-bin’ algorithm?

Answer 11

Strength:
- Usually get good solution

Weakness:
- Difficult to do