9618 · 19.1
Algorithms flashcards
Revision flashcards for Cambridge 9618 Algorithms (syllabus 19.1). Flip, recall, then mark a real past-paper question.
Card
What is an algorithm?
A finite, well-defined sequence of steps or rules to solve a specific problem or perform a computation. It must be unambiguous and guaranteed to terminate.
Card
Describe a Linear Search.
An algorithm that sequentially checks each element of a list until a match is found or the whole list has been searched. It does not require the list to be sorted.
Card
What is the worst-case time complexity of a Linear Search?
O(n), where 'n' is the number of elements in the list. This occurs when the item is the last element or not in the list at all.
Card
Describe a Binary Search.
A fast search algorithm that repeatedly divides the search interval in half. It compares the target value to the middle element of the array; if they are not equal, the half in which the target cannot lie is eliminated.
Card
What is the essential pre-condition for a Binary Search?
The list or array must be sorted. If it is not sorted, the algorithm will not work correctly and may return an incorrect result or fail to find an existing item.
Card
What is the worst-case time complexity of a Binary Search?
$O(\log n)$. This logarithmic complexity makes it extremely efficient for large datasets compared to linear search.
Card
Describe a Bubble Sort.
A simple sorting algorithm that repeatedly steps through the list, compares adjacent elements and swaps them if they are in the wrong order. Passes through the list are repeated until the list is sorted.
Card
What is the worst-case time complexity of a Bubble Sort?
$O(n^2)$. This occurs when the list is in reverse order. It is considered an inefficient sort for large datasets.
Card
What is a 'pass' in the context of a Bubble Sort?
A single traversal through the list (or the unsorted part of it), comparing and swapping adjacent elements. In each pass, the next largest element 'bubbles' up to its correct position.
Card
What is a trace table used for?
To test an algorithm by hand, tracking the values of variables at each step or iteration. It is used for debugging and verifying that an algorithm works as intended.
Card
What is an 'in-place' sorting algorithm?
An algorithm that sorts the data within the original array, using only a small, constant amount of extra storage space. Bubble Sort is an example of an in-place algorithm.