<aside> 📊

L11 — Analyse! covers the transition from data structures to algorithms. It introduces pseudocode conventions (assignment notation, comments, indentation), sequential search (O(n)), binary search using divide-and-conquer (O(log₂ n)), and three simple sorting algorithms — insertion sort, selection sort, and bubble sort — along with key properties: stability, in-place, and time complexity (worst, average, best cases).

</aside>

📋 At a Glance

• [ ] Understand why we use pseudocode instead of real code for describing algorithms
• [ ] Know the common pseudocode conventions: assignment (= or ←), equality (==), comments (. or //), indentation
• [ ] Trace sequential search and know its complexity: worst Θ(n), best Θ(1), average Θ(n)
• [ ] Explain the divide-and-conquer idea behind binary search
• [ ] Trace binary search with low/high/mid pointers and know its complexity: O(log₂ n)
• [ ] Know why sorting is a prerequisite for binary search
• [ ] Define stability: a sort is stable if it preserves the relative order of elements with equal keys
• [ ] Define in-place: a sort is in-place if it uses O(1) additional memory
• [ ] Trace insertion sort on a small array and know its pseudocode
• [ ] Know insertion sort properties: stable, in-place, worst Θ(n²), average Θ(n²), best Θ(n)
• [ ] Trace selection sort on a small array and know its pseudocode
• [ ] Know selection sort properties: in-place, not stable, always Θ(n²) comparisons, at most n−1 swaps
• [ ] Trace bubble sort on a small array and know its pseudocode
• [ ] Know bubble sort properties: stable, in-place, worst Θ(n²) — combines disadvantages of both insertion and selection sort
• [ ] Understand why simple sorts are O(n²) and why this is problematic for large data
• [ ] Know that insertion sort is fast for small or nearly-sorted arrays
• [ ] Know that selection sort minimises the number of swaps (useful when swapping is expensive, e.g. hardware/FPGA)