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)
What is a first-fit algorithm
Take each item in the order it is given
Place it into the first available bin it will fit
Pros and cons of first fit algorithm
+ Easy to implement
- Not likely to be efficient
What is a first-fit decreasing algorithm
Sort items into descending order
Apply first fit algorithm
Pros and cons of first-fit decreasing algorithm
+ Usually a good solution
- May not be optimal solution
What is a full-bin packing algorithm
Put together items that will completely fill a bin
Place any remaining items using first-fit algorithm
Pros and cons of full-bin backing algorithm
+ Usually get a good solution
- Difficult to implement
What is the equation when time is proportional to number of items (n)
t = kn
What is the equation when time is proportional to number of items squared (n^2)
t = kn^2
What is the equation when time is proportional to number of items cubed (n^3)
t = kn^3
What does the order / complexity / size of problem of an algorithm mean
Whether time is proportional to number of items linear / quadratic / cubed
What is the time taken to complete an algorithm also called
Run time
What is important about values worked out for run time
They are estimates
The bubble sort algorithm has quadratic order. Given that it takes a computer 0.2 seconds to sort a list of 1600 numbers using the bubble sort, estimate the time needed to sort a list of 480,000 numbers
t proportional to n^2
t = kn^2
0.2 = k * 1600^2
k = 7.8125 * 10^-8
t = 7.8125 * 10^-8 * n^2
t = 180,000 seconds
t = 5 hours
A bubble sort algorithm has quadratic order, comment on the suitability of the bubble sort algorithm for sorting large data sets
Since the time taken increases by a factor of the number of items squared, this algorithm is NOT suitable for sorting large data sets of items
