Help shape GoConqr. What should we add next?

Notes

Summary of Chapter 1

jakubburger Decision English 1 page

Content of the notes (1)

Page 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.

11 The three bin packing algorithms have advantages and disadvantages.

Page 1

Page 2

Information

Description
Decision (Chapter 1: Algorithms) Note on Summary of Chapter 1, created by jakubburger on 11/04/2013.
Created by
jakubburger · Apr 2013
Updated
Feb 19, 2016
Views
100
Tags
chapter 1: algorithmsdecision
Rating

Feedback

What is it about?

What should we add next?