Interactive lab¶
Here you can watch the algorithms at work. Pick an app: it opens full page, with sliders and buttons. Drag the sliders, or press ▶ to run one step at a time and «Run» for the animation. The notation is that of the lecture notes: arrays \(a[1..n]\) indexed from 1, the same names of algorithms and variables.
Basic algorithms¶
-
Number representation
The same integer in binary, two's complement, sign-magnitude and IEEE 754: change the number and watch the bits.
-
Sorting step by step
Insertion, exchange and selection sort: comparisons and moves one step at a time, with the pseudo-code line being executed.
-
Linear and binary search
The same sorted array searched in two ways: count how many comparisons linear and binary search need.
-
Euclid and the sieve of Eratosthenes
The greatest common divisor through successive remainders, and the primes that emerge by crossing out multiples.
Asymptotic notation and growth¶
-
Orders of growth
Logarithm, polynomials, exponential: how many steps (and how much time) are needed as n grows, comparing the functions.
Analysis of algorithms¶
-
The loop invariant
FindMaximum iteration by iteration: check that the invariant holds at the start, at every step and at the end.
Recursion¶
-
Recursion trees
The tree of calls of a recursive function and the stack: nodes count the steps, depth counts the memory.
-
The Master Theorem
The recurrence T(n) = a T(n/b) + n^d level by level: the cost of the levels is a geometric progression and decides the order of T(n).
-
Merge sort
Divide down to one element, then merge the sorted halves with Merge: watch calls and merges one at a time.