Apuntes
Summary of Chapter 1
Contenido del apunte (1)
Página 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
Información
- Descripción
- (Chapter 1: Algorithms) Decision Apunte sobre Summary of Chapter 1, creado por jakubburger el 11/04/2013.
- Creado por
- jakubburger · abr 2013
- Actualizado
- 19 feb 2016
- Visitas
- 100
- Etiquetas
- Valoración