Everything from the 5 lessons of this topic on a few pages: the key idea of each lesson, the diagram to remember, the points to learn and the traps examiners set. Read it, cover it, test yourself.
A binary search only works on data that is sorted and held in a structure with direct access by index, such as an array. It compares the search item with the middle element, Mid ← (Low + High) DIV 2. If they match, the item is found; if the middle item is smaller, the search continues in the upper half (Low ← Mid + 1); otherwise in the lower half (High ← Mid - 1). It stops when the item is found or Low > High. Each comparison halves the items left, so the worst case for n items is about log2 n comparisons: 1000 items need at most 10.
| Low | High | Mid | List[Mid] | Action |
|---|---|---|---|---|
| 1 | 15 | 8 | 34 | High ← 7 |
| 1 | 7 | 4 | 17 | Low ← 5 |
| 5 | 7 | 6 | 26 | High ← 5 |
| 5 | 5 | 5 | 21 | High ← 4 |
20 is not found after 4 comparisons (a linear search would need 15).
(Low + High) DIV 2; compare List[Mid] with the search item.Low ← Mid + 1; smaller means High ← Mid - 1.INT(log2 n) + 1 comparisons."A binary search splits the list in half" is not enough for the marks. Say what is compared (the middle item with the search item) and what is discarded (the half that cannot contain it, because the data is sorted).
Do not use the loop condition Low < High. When the item is in the last element left (Low = High) the loop would stop without checking it.
Do not say a binary search is "always faster". It needs sorted data, and on a tiny list, or when the item is the first element, a linear search can need fewer comparisons.
An insertion sort treats the first element as a sorted part of length one. Each pass takes the next element as the key, compares it with the sorted part from right to left, shifts every larger element one place to the right, and drops the key into the gap. After pass i the first i elements are in order. On data that is already sorted each pass makes one comparison, so it needs only n − 1 comparisons; on data in reverse order it needs n(n − 1)/2. The bubble sort has the same best and worst cases, but usually makes more comparisons and moves data with three-step swaps.
FOR i ← 2 TO n, Key ← List[i], j ← i - 1.j >= 1 and List[j] > Key, shift right and decrease j.List[j + 1] ← Key after the inner loop.Do not describe an insertion sort as "comparing adjacent pairs and swapping them": that is a bubble sort. Say that each item is inserted into its correct position in the sorted part.
Writing List[j] ← Key after the loop puts the key one place too far left. When the loop stops, j points at the element that is not larger, so the gap is at j + 1.
"Insertion sort is faster than bubble sort" earns little on its own. Link the answer to the data: for nearly sorted data both are quick, and in the worst case both need n(n − 1)/2 comparisons.
An abstract data type (ADT) is defined by its data and its operations, not by how it is stored. A stack (push, pop) needs an array and a top pointer; a circular queue (enqueue, dequeue) needs front and rear pointers that wrap round with MOD; a linked list needs an array of records with a start pointer, a free list pointer and a null pointer (−1) at the end; a binary search tree adds a left and a right pointer to each node, smaller values to the left. A dictionary stores key-value pairs, and a graph is a set of vertices joined by edges. ADTs can be built from other ADTs, for example a queue from two stacks.
(Pointer + 1) MOD Size and keep a count.In a circular queue, write (RearPointer + 1) MOD 6, not RearPointer + 1. Without MOD the pointer runs past index 5 even though spaces at the front are free.
Deleting the first node is a special case: there is no previous node, so the start pointer must change. Code that only updates List[Previous].Pointer fails for it.
When inserting into a tree or a linked list, take the node from the free list and update the free pointer before setting the new node's own pointers, or the rest of the free list is lost.
Algorithms that perform the same task are compared by the time taken (the number of basic steps, such as comparisons) and the memory used, as the number of data items n grows. Big O notation gives the order of growth in the worst case: keep only the dominant term and drop constants, so 3n2 + 5n + 2 steps is O(n2). Time complexity ranks O(1) < O(log n) < O(n) < O(n log n) < O(n2) < O(2n). Space complexity uses the same notation for extra memory: an in-place sort is O(1), a copy of the data is O(n).
Count ← Count + 1 executed by the code above when n = 10? What if the inner loop is changed to FOR j ← i TO n?"Algorithm A is faster because it took 0.3 seconds" earns nothing. Compare the number of operations as n increases, or the Big O order.
O(log n) does not mean "fewer than n" for every n, and O(n2) does not give an exact count. Big O describes how the work grows; for very small n a "worse" algorithm can still be quicker.
Do not confuse the two criteria. "It uses less memory" is a space argument; "it makes fewer comparisons" is a time argument. Say which one you mean and link it to n.
A recursive subroutine is one that is defined in terms of itself: it calls itself. It must have a base case, a condition where it returns a result without calling itself, and a general (recursive) case that calls itself with a value that moves closer to the base case. Each call is placed on the call stack as a stack frame holding its return address, parameters and local variables. When the base case is reached the calls return one by one in reverse order: the stack unwinds. With no reachable base case the stack fills up: stack overflow.
Factorial(4).| Call | n | Waits for | Returns |
|---|---|---|---|
| 1 | 4 | 4 * Factorial(3) | 24 |
| 2 | 3 | 3 * Factorial(2) | 6 |
| 3 | 2 | 2 * Factorial(1) | 2 |
| 4 | 1 | 1 * Factorial(0) | 1 |
| 5 | 0 | (base case) | 1 |
Five calls in total; the value 24 is returned to the original caller.
A base case that is never reached is as bad as none. Factorial(−1) calls Factorial(−2), then −3, ... and never meets n = 0, so the stack overflows. State that each call must move towards the base case.
In a trace, do not output a value when a call is made if the OUTPUT is after the recursive call. Write each call on a new row, and fill in its output only when control returns to it.
"Recursion is faster" is usually wrong. A recursive solution is often shorter and clearer, but it normally uses more memory and more time than an equivalent loop because of the stack frames.