Algorithms Flashcards
What is the shape of a start/end box?
A rounded rectangle
What is the shape of an instruction box?
A rectangle
What is the shape of a decision box?
A diamond
Explain the bubble sort algorithm
Starting from the leftmost value, go through each pair of adjacent values. If they are in the incorrect order, swap them around. Otherwise leave them. Repeat this entire step until a pass is completed without making any swaps
In a list of N items, what is the middle item?
⌈(N+1)/2⌉
Explain the quick sort algorithm
Select the middle item as the pivot. For all other values, and still retaining order, if it is less than the pivot then place it to the left, else place it to the right. This creates two sub-lists, one on each side of the pivot. Repeat the process with these sub-lists, and the sub-lists formed from this, and so on, until all items have been selected as the pivot
Explain the binary search algorithm
Compare the target with the middle value. If the target is less than the middle value, discard the second half of the list (and the middle value). If it is more than the middle value, discard the first half of the list. Repeat this process until the target is either found, or there is one item left which is not the target
In the bin packing algorithm, how can the lower bound for the number of bins required be calculated?
⌈sum of heights/bin size⌉
Explain the first-fit bin packing algorithm
Each item goes in the leftmost bin that it will fit in
Explain the first-fit decreasing bin packing algorithm
The items are sorted into descending order, and then the regular first-fit algorithm is applied
Explain the full-bin packing algorithm
Observation is used to find combinations of items that will completely fill a bin. Any remaining items are packed using the first-fit algorithm
