Algorithm fundamentals

A procedure counts as an algorithm when it has: input (zero or more values), output (at least one result), finiteness (it stops), definiteness (every step is precise) and effectiveness (every step can be done by a machine in finite time).

“Make the best coffee” is not an algorithm: the steps are not definite. “Boil 200 ml of water, add 10 g of grounds, wait 4 minutes, pour” is.

An algorithm must terminate on every valid input. Loops need a measure that moves toward the exit condition on every iteration, such as an index that grows toward n or a value that shrinks toward 0.

A common bug is updating the wrong variable, or updating it only on some paths, so the loop never ends.

1// terminates: i grows toward n on every iteration
2for (int i = 0; i < n; i++) { work(); }
3
4// terminates: n halves each time and is an int, so it reaches 0
5while (n > 0) { n /= 2; }
6
7// does NOT terminate when x is 0 or negative: x never reaches 10 from below
8int x = 1;
9while (x != 10) { x -= 1; }     // bug: should have been x += 1

A deterministic algorithm performs the same steps and returns the same result every time it is given the same input. Most algorithms in this course are deterministic, which makes them easy to test.

Randomness, threads and reading the clock introduce non-determinism. Keep such sources behind a parameter (a seed, a clock object) so that tests can control them.

1Random rnd = new Random(42);          // fixed seed: same sequence every run
2int a = rnd.nextInt(100);
3int b = new Random(42).nextInt(100);  // a == b
4// new Random() without a seed differs on every run, so tests become flaky

Each step must have one precise meaning. “Process the items quickly” is not definite; “for each item in index order, add its price to total” is. Definiteness also means the order of steps is fixed, and every branch has a stated condition.

Typical sources of ambiguity: unclear tie-breaking (“pick the largest” when two are equal), unspecified order of iteration, and undefined behaviour for edge inputs such as an empty array.

A precondition is what must be true when a method is called; a postcondition is what is guaranteed when it returns. If the caller breaks a precondition, the method owes nothing. If the method breaks a postcondition, the method has a bug.

In Java, check cheap preconditions with exceptions at public boundaries, and use assert for internal conditions you believe are always true.

1/** Precondition: lo <= hi, arr sorted. Postcondition: returns first index with arr[i] >= target, or arr.length. */
2static int lowerBound(int[] arr, int target) {
3    Objects.requireNonNull(arr);                        // public boundary: throw on misuse
4    int lo = 0, hi = arr.length;
5    while (lo < hi) {
6        int mid = lo + (hi - lo) / 2;
7        if (arr[mid] < target) lo = mid + 1; else hi = mid;
8    }
9    assert lo == arr.length || arr[lo] >= target;       // postcondition (run with java -ea)
10    return lo;
11}

Pseudocode is a language-neutral outline of an algorithm: precise enough to implement, loose about syntax. Use it to think before coding and to compare the idea with the Java.

Conventions used on this site: indentation shows nesting, ← is assignment, arrays are 0-based, and return ends the procedure.

1LINEAR-SEARCH(A, target)
2    for i ← 0 to length(A) - 1
3        if A[i] = target
4            return i
5    return -1
6
7// Java
8static int linearSearch(int[] a, int target) {
9    for (int i = 0; i < a.length; i++) if (a[i] == target) return i;
10    return -1;
11}

A flowchart draws an algorithm as boxes and arrows: rounded boxes for start and end, rectangles for actions, diamonds for decisions. They are useful for explaining branching logic to non-programmers, and clumsy for loops over data, which is why this course uses animations and tracing tables instead.

Text form of the flowchart for “is n even?”: START → read n → decision [n % 2 == 0] → yes: print “even”, no: print “odd” → END.

A dry run executes code by hand with concrete values, without a computer. It finds logic errors early and builds the habit of thinking in program states. Pick a small input, write down each variable, and update them one statement at a time.

Step through the animation below with a different array each time. Each frame shows the variables a dry run would track, the condition just evaluated, and the highlighted line.

1public static int sumEvens(int[] arr) {
2    int sum = 0;
3    for (int i = 0; i < arr.length; i++) {
4        if (arr[i] % 2 == 0) {
5            sum += arr[i];
6        }
7    }
8    return sum;
9}

A tracing table has one column per variable (and one for the condition) and one row per step. It is the written form of what the animation's trace table shows. Open “Execution trace” under the player to see every step as a row.

Dry run of sumEvens on [3, 8, -2, 7]: