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

How to use an algorithm

Make a table with a column for each step


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


Flow charts start/end shape



Flow charts instruction shape



Flow charts decision shape



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


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

It decreases by 1


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



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


Which sorting method is quicker

Quick Sort


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


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


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


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


Bin-packing algorithm

Bin | Items in Bin | Space in Bin


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


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


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


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


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)