Summary of Chapter 1

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.

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        

11 The three bin packing algorithms have advantages and disadvantages.   

Page 1

Page 2