Algorithms And Flow Charts Flashcards Preview

A Level Further Maths Decision 1 > Algorithms And Flow Charts > Flashcards

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

Why does bubble sort have quadratic order?

Pass 1 has (n-1) comparisons and pass 2 (n-2) and so on
(n-1) + (n-2) + … + 2 + 1
Arithmetic series n/2(n+1)