1 Algorithms can be given in words or flowcharts.

2 Unordered lists can be sorted using a bubble sort or a quick sort.

3 In a bubble sort, you 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.

4 In a quick sort, you select a pivot and then split the items into two sub-lists: those less than the pivot and those greater than the pivot.

Keep doing this to each resulting sub-list.

5 In a quick sort, the item at the mid-point of the list is chosen as the pivot.

Items less than the pivot are written down, keeping their order.

The pivot is written next.

Items greater than the pivot are written down, keeping their order.

6 A binary search will search an ordered list to find out whether an item is in the list. If it is in the list, it will locate its position in the list.

7 In a binary search, the pivot is the middle item in the list. If the target item is not the pivot, the pivot and half the list are discarded. The list length halves at each pass.

8 The middle of n items is found by [(1+ n)/2], rounding up if necessary.

9 The three bin packing algorithms are: first-fit, first-fit decreasing, and full-bin.

10

First-fit algorithm takes items in the order given.

First-fit decreasing algorithm requires the items to be in descending order before applying the algorithm.

Full-bin packing uses inspection to select the items that will combine to fill bins. Remaining items are packed using the first-fit algorithm.

11 The three bin packing algorithms have advantages and disadvantages.

Advantage

Disadvantage

First-fit

Quick to do

Not likely to lead to a good solution

First-fit decreasing

Usually a good solution

Easy to do

May not get an optimal solution

Full-bin

Usually a good solution

Difficult to do, especially when lots of numbers or awkward numbers

	Created by jakubburger about 11 years ago

Decision (Chapter 1: Algorithms) Note on Summary of Chapter 1, created by jakubburger on 04/11/2013.

Summary of Chapter 1