Algorithms 2. Packing and Sorting

Question 1

What is a bin-packing problem?

Answer 1

A problem that packs ‘boxes’ of given sizes into a number of (equal sized) ‘bins’ of a fixed size. The boxes are in a given order and so are the bins.

Question 2

What is the first-fit algorithm?

Answer 2

You pack each box, in turn, into the first available bin into which it will fit.

Question 3

What is the first-fit decreasing algorithm?

Answer 3

You Reorder the boxes from the largest to the smallest

 Apply the first-fit algorithm to the reordered list of boxes

Question 4

What is the full bin method?

Answer 4

You look for combinations of boxes which fill a bin and pack these boxes

 Put the rest of the boxes in combinations which come as close as possible to filling bins

Question 5

Why is the full bin method not an algorithm?

Answer 5

it is ambiguous; there may be different ways of packing full bins.

Question 6

What are the two algorithms not guaranteed to produce?

Answer 6

The two algorithms are not guaranteed to produce an optimal solution (which in this case means using the least number of bins).

Question 7

What is a heuristic algorithm?

Answer 7

An algorithm which is usually efficient but may not produce an optimal solution is called a heuristic, or heuristic algorithm.

Question 8

What complexity do first fit and first fit decreasing algorithm have?

Answer 8

First-fit and first-fit decreasing have quadratic complexity, O(n2), where n is the number of boxes.

Question 9

How do you carry out the quick sort algorithm?

Answer 9

First pass
 The first value in the list is the pivot
 Rearrange the list as follows
o Go along the list, writing down each value which is less than or equal to the pivot
o Write down the pivot
o Go along the list writing down the values which are greater than the pivot.
o Underline the pivot to show it is in the correct place in the final sorted list.

Subsequent passes
 The previous pivot divides the new list into two sub-lists.

 Repeat the instructions for the first pass on these sub-lists.

Continue in this way until every value in the list is underlined to show it is in
the correct place.

Question 10

What is worst case complexity for quick sort?

Answer 10

The worst-case complexity for quick sort is O(n2) where n is the number of numbers in the list to be sorted and you are counting the number of comparisons to be made. ‘Worst-case’ complexity means that you imagine that the maximum possible number of comparisons has to be made e.g. if the list is actually in reverse order.