Flashcards in Algorithms And Flow Charts Deck (20)

Loading flashcards...

1

## How to use an algorithm

### Make a table with a column for each step

2

## When to move on to the next row of a table?

### When you have to move left in the table or fill a square which already has a number

3

## Flow charts start/end shape

### Oval

4

## Flow charts instruction shape

### Rectangle

5

## Flow charts decision shape

### Diamond

6

## Bubble Sort Process

###
Check whether it is ascending or descending

Start at the left value and compare with the one to the right of it

Draw a curvy line between and point the end if you swap them

Use whichever value ended up on the right side of those and compare with the one to the right

When you finish this once the rightmost value is in the right place

Write the amount of comparisons and swaps each time

Repeat not checking the rightmost value

Stop when you make 1 check or no swaps

7

## Bubble sort, how does the amount of comparisons change each time

### It decreases by 1

8

## Bubble sort, what is the most amount of comparisons needed for a list of 10

### 45

9

## Quick Sort Process

###
Check if ascending or descending

Choose the middle or middle-right value to be the pivot and circle it

Make a sub-list of bigger and smaller values on each side of the pivot (not ordered) which side depends on ascending or descending

Draw a downwards line each side of the pivot

Simultaneously repeat for each sub-list and keep going until all values have been pivots or are surrounded by lines

10

## Which sorting method is quicker

### Quick Sort

11

## How to find the lower bound of the amount of bins required

###
Sum of all the sizes

________________

Bin size

Round up to next whole number

12

## First-fit bin packing algorithm

###
Take the items in the order given

Place each in the first available bin

+ quick to implement

- not likely to lead to a good solution

13

## First-fit decreasing algorithm

###
Sort the items into descending order

Apply the first-fit algorithm

+ easy to implement, fairly good solution

- may not get an optimal solution

14

## Full-fit bin packing algorithm

###
Use observation to find combinations of items which will fill a bin and pack these first.

Use first-fit for any remaining items

+ Usually get a good solution

- Difficult to do, especially for lots of/awkward numbers

15

## Bin-packing algorithm

### Bin | Items in Bin | Space in Bin

16

## Order of an algorithm

###
Can also be known as the complexity of an algorithm

How changes in size of the problem affect the approximate run time of the algorithm

17

## If the size is increased by k then

###
Linear: the time increases by a factor of k

Quadratic: the time increases by a factor of k^2

Cubic: the time increases by a factor of k^3

18

## How to go from the change in time to the change in size

###
If k is the change in k

Linear: the size increases by k

Quadratic: the size increases by root k

Cubic: the size increases by the cube root of k

19

## Why does the first-fit bin packing algorithm have quadratic order?

###
Because for n items, at most n-1 bins need to be checked

n(n-1) which is a quadratic

20