Algorithms And Flow Charts

Question 1

How to use an algorithm

Answer 1

Make a table with a column for each step

Question 2

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

Answer 2

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

Question 3

Flow charts start/end shape

Answer 3

Oval

Question 4

Flow charts instruction shape

Answer 4

Rectangle

Question 5

Flow charts decision shape

Answer 5

Diamond

Question 6

Bubble Sort Process

Answer 6

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

Question 7

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

Answer 7

It decreases by 1

Question 8

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

Answer 8

45

Question 9

Quick Sort Process

Answer 9

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

Question 10

Which sorting method is quicker

Answer 10

Quick Sort

Question 11

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

Answer 11

Sum of all the sizes
________________
Bin size

Round up to next whole number

Question 12

First-fit bin packing algorithm

Answer 12

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

Question 13

First-fit decreasing algorithm

Answer 13

Sort the items into descending order
Apply the first-fit algorithm

+ easy to implement, fairly good solution
- may not get an optimal solution

Question 14

Full-fit bin packing algorithm

Answer 14

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

Question 15

Bin-packing algorithm

Answer 15

Bin | Items in Bin | Space in Bin

Question 16

Order of an algorithm

Answer 16

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

Question 17

If the size is increased by k then

Answer 17

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

Question 18

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

Answer 18

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

Question 19

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

Answer 19

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

n(n-1) which is a quadratic

Question 20

Why does bubble sort have quadratic order?

Answer 20

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)