Algorithms

Question 1

What is an algorithm?

Answer 1

A finite sequence of step-by-step instructions carried out to solve a problem.

Question 2

How do you complete a bubble sort?

Answer 2

Compare adjacent items in a list:
- if they are in order, leave them
- if they are not in order, swap them
- the list is in order when a pass is completed without any swaps

Question 3

How do you complete a quick sort?

Answer 3

Select a pivot then split the items into two sub-lists:
- one sub-list contains items less than the pivot
-the other sub-list contains items greater than the pivot
- select further pivots from within each sub list and repeat the process until all items have been chosen as pivots
- write “sort complete”

Question 4

How do you determine the lower bound for the number of bins needed?

Answer 4

Sum the heights of the boxes then divide by the bin size. Round up to the next integer.

Question 5

How do you execute the first-fit bin packing algorithm?

Answer 5

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

Question 6

What are the advantages and disadvantages of the first-fit bin packing algorithm?

Answer 6

Advantage: quick to implement
Disadvantage: not likely to lead to a good solution

Question 7

How do you execute the first-fit decreasing bin packing algorithm?

Answer 7

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

Question 8

What are the advantages and disadvantages of the first-fit decreasing bin packing algorithm?

Answer 8

Advantages: usually get a good solution, easy to implement
Disadvantage: may not get an optimal solution

Question 9

How do you execute the full-bin packing algorithm?

Answer 9

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.

Question 10

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

Answer 10

Advantage: usually get a good solution
Disadvantage: difficult to do, especially when the numbers are plentiful and awkward

Question 11

What does the order of an algorithm tell you?

Answer 11

How changes in the size of a problem affect the approximate time taken for its completion.
If an algorithm has order f(n), then increasing the size of the problem from n to m will increase the run time of the algorithm by a factor of f(m)/f(n).