D1, C1 - Algorithms Flashcards
What is an algorithm
A process or a set of instructions that need to be followed PRECISELY
How can you use a table to implement algorithms (what goes in the top row (headers))
Step number
Variables (such as A, B, et…)
Print (if things are printed)
What numbers does an algorithm generate if it generates (1, 1, 2, 3, 5, 8, …)
Fibonacci sequence
What is a flow chart
A way of listing instructions or a process
What shape is a start / end in a flow chart
Oval
What shape is an instruction in a flow chart
Rectangle
What shape is a decision (question) in a flow chart
Diamond
What is a trace table
A table that record actions / results
What goes in the header of a trace table
Actions
Variables
Print
Decisions
Perform a bubble sort on 4, 1, 3, 2 to get them into ascending order
1) 4, 1, 3, 2
2) 1, 3, 2, 4
3) 1, 2, 3, 4
4) 1, 2, 3, 4
What are the steps for a bubble sort
1) Start at the beginning and move from left to right comparing adjacent items, if in order leave, if out of order swap
2) When you get to the end of the working list, last item will be in its final position, this item is no longer in the working list
3) If you have made some swaps in the last pass repeat step 1
4) When a pass is completed with no swaps, every item is in final position and the list is in order
What is ascending
Smallest to biggest
What is descending
Biggest to smallest
Bubble sort into ascending order:
24, 18, 37, 11, 15, 30
1) 24, 18, 37, 11, 15, 30
2) 18, 24, 11, 15, 30, 37
3) 18, 11, 15, 24, 30, 37
4) 11, 15, 18, 24, 30, 37
5) 11, 15, 18, 24, 30, 37
What working should you show with bubble sorts
Circle letters / numbers being swapped
Write swap / leave
Perform a FINAL pass to show nothing changes
How do you find the pivot of a quick sort for even and odd n (where n is the number of letters / numbers)
(n + 1) / 2 if n is odd
if n is even round up
What are the steps of a quick sort (ascending) (6)
1) Choose the item at the midpoint of the list to be the first pivot ((n+1)/2)
2) Write down all the items that are less than the pivot, keeping their order, in a sub list
3) Write down the pivot
4) Write down the remaining items ( greater than the pivot) in a sub list
5) Apply steps 1 to 4 for each sub list
6) When all items have been chosen as pivots, stop
Perform a quick sort on 8, 3, 6, 4, 2 into ascending order
1) 8, 3, (6), 4, 2
2) 3, (4), 2, (6), (8)
3) 3, (2) (4), (6), (8)
4) (2), (3), (4), (6), (8)
What are bin packing algorithms
Algorithms that allow us to put different sized items into bins, so that there is the least amount of wasted space and the least number of bins is used
What are examples of bin packing uses
Production lines
Files on a hard disk
Packing items into a lorry
What is the lower bound in bin packing
The least number of bins required for packing
Is the lower bound in bin packing always achievable
NO
What does it mean if a solution for bin packing is the lower bound
Solution = optimal solution
What is the formula for lower bound in bin packing
Total size of all items / bin size
(round up)
