Algorithmic Thinking, Problem Specification, and Correctness

This is the first of fifteen sets of notes. It does two jobs. First, it sets out how the course runs and what you will be graded on. Second, it introduces the three habits that everything else in the semester rests on: saying precisely what a problem is, designing a procedure that solves it, and being able to argue that the procedure is right — before anyone runs it.

Session planHow we will spend the 110 minutes

Section 1How this course works

AI 230 is a three-credit course with an integrated two-hour laboratory component, delivered online. We meet twice a week, Tuesday and Thursday, 4:00–5:50 PM, live over Google Meet. There is no separate lab period — the lab happens inside these sessions. That has a practical consequence you should absorb now: these are working sessions, not lectures you can watch passively. This is a tutorial-size section, and every student is expected to present current work and take part in critique at every meeting.

There are no examinations. Your entire grade comes from four projects, each worth 25%. Each project is a real build with a written component, submitted as a Git repository plus a report. Specifications and rubrics are released at least two weeks before each due date and posted to the course repository. Late submissions lose 10% per calendar day unless an extension was granted in advance.

There is no textbook and nothing to purchase. All notes, worked examples, code, and project specifications are written for this course and posted to the course GitHub repository before the session that uses them. Brightspace at lms.liu.edu carries announcements, submissions, and grades.

Tools you need working by next session

• Python 3.11 or later — the primary language for all projects. Another language is permitted with prior approval.
• Git and a personal GitHub account — every project is submitted as a repository, so version control is not optional here.
• A code editor of your choice; VS Code is recommended.
• Jupyter Notebook or equivalent — you will use it for benchmarking and analysis write-ups, starting with Project 1.

Section 2Two protagonists: algorithms and data structures

Everything in this course is a conversation between two ideas. One of them is in the course title; the other shares top billing anyway. This section introduces both — and deliberately stops at the introductions. The machinery behind each is a story for later weeks; on day one, the two protagonists only need to be named precisely.

Each adjective in that definition is doing work, and it is worth naming what each one rules out.

• Finite. It has to stop. A procedure that never terminates on some legal input is not an algorithm for that problem — it is a bug with good intentions. You will watch one fail this way in §6.2.
• Unambiguous. Every step must be mechanically executable. "Sort the list intelligently" is not a step. "Compare adjacent elements and swap if out of order" is.
• Specified input and output. An algorithm without a stated problem is a procedure with no way to be wrong. This is why §4 exists.

Notice what the definition does not mention: a programming language, a machine, a runtime. An algorithm is an idea. Code is one realization of it. The same algorithm can be written in Python, in C++, on paper, or carried out by hand — and it is the same algorithm each time, with the same fundamental cost behavior. Confusing the algorithm with its implementation is the most common beginner error in this field, and it is why we write pseudocode alongside code all semester.

Why algorithms matter

• They are systematic solutions rather than clever one-offs. An algorithm solves the whole family of instances, not the instance in front of you.
• They determine efficiency. Hardware improves by constant factors. Algorithms improve by orders of magnitude. A better algorithm on a slow machine routinely beats a worse algorithm on a fast one, and the gap widens as the data grows — next week puts a number on exactly how much.
• They are everywhere. Search ranking, route planning, recommendation, compression, encryption, scheduling, training a model — each is an algorithmic problem wearing a product's clothes.

The second protagonist

That definition is short enough to memorize, so give it just enough depth to be honest. Memory is fundamentally flat — an addressable array of bytes with no notion of "customer" or "route" or "word count." A data structure is the shape you impose on that flatness, together with the set of operations the shape makes cheap. And the second half of that sentence carries a warning worth keeping all semester: a data structure is not just a layout; it is a layout plus a bargain. Every way of organizing data makes some operations fast and, in exchange, makes others slow. There is no structure that wins everywhere — only structures that fit, or fail to fit, what a particular program actually does.

How deep that bargain runs — what arrays, linked lists, stacks, queues, hash tables, trees, heaps, and graphs each pay and what each gets back — is the business of Weeks 6–7, and you will feel it in your hands in Project 2, where you build the important ones without library support. Today, the definition and the bargain are all we need.

Why they are taught together

Data structures and algorithms are usually taught as one subject because separating them produces nonsense. The structure determines what operations are cheap; the algorithm is a sequence of operations. Change the structure and the algorithm's cost changes, sometimes catastrophically, without a single line of the algorithm being edited.

Brooks is making a strong claim: choose the representation well and the procedure often writes itself. Testing that claim is a running theme of the whole semester, and it begins in earnest once we can measure cost. For now, take it as the reason this course keeps both protagonists on stage at once.

Section 3Algorithmic thinking

Everything so far has been vocabulary. This section is the actual subject of the course.

Algorithmic thinking is the discipline of moving from "I know what I want" to "I know exactly how to get it, I can say why it works, and I can say what it costs." Most people who can program have the first half — they can produce something that runs and produces plausible output. What separates an engineer from a coder is the second half: the ability to defend the thing.

Four habits make up that discipline, and we practice all four every week this semester.

1. State the problem before solving it. Most bad solutions are answers to a question nobody asked precisely. §4.
2. Find what stays true. Loops and recursions are hard to reason about all at once. They become easy the moment you identify the one property that holds at every step. §6.
3. Argue, don't just test. Tests can show that a bug exists. They cannot show that none does. §6.
4. Count the cost. Correct is the floor, not the ceiling. Two correct programs can differ by a factor of a million — Week 2 is devoted to measuring exactly that.

Section 4Problem specification

A specification is a contract. It states what the caller must guarantee before invoking your procedure, and what your procedure guarantees in return. Nothing outside the contract is promised.

A weak postcondition, demonstrated

Here is the claim this section rests on, and it is worth stating before you see it work: a specification is only as strong as the stupidest procedure that satisfies it. Writing "sort the list" feels complete. It is not, and the way to find out is to hunt for a procedure that obeys every word you wrote and is obviously not a sort.

Below, four candidate procedures run against the same input. Switch on the clauses of your postcondition one at a time and watch which candidates survive. Your goal is a specification that admits the real sort and rejects everything else — using the fewest clauses that achieve it.

Work through it and the lesson lands on its own. Ordering alone lets [0,0,0,0] through — perfectly non-decreasing, and it threw your data away. Add contents and [1,2,3] still slips past, having quietly deduplicated. Only all three together pin down the real sort. Every clause you left out was a bug you had authorized in advance.

Two things worth naming. First, "my sort silently loses elements" is a genuine class of production bug, not a classroom contrivance — and the specification is where you would have caught it, for free, before writing a line. Second, notice that the identity procedure fails only the ordering clause while satisfying the other two: each clause is doing distinct work, and dropping any one of the three reopens a different hole.

Specification is where correctness gets its meaning

A program cannot be "correct" in the abstract — it can only be correct with respect to a specification. Ask "is this function right?" and the only honest answer is "right about what?" Every correctness argument in this course, and every test you write in your four projects, is ultimately an argument that the postcondition holds whenever the precondition did.

Section 5Pseudocode as a design tool

Pseudocode is a description of a procedure precise enough to be unambiguous, but free of the syntax and bookkeeping of any real language. It is not a lesser form of code. It is a different tool, used at a different stage, for a different purpose: pseudocode is where you think, code is where you commit.

The reason to use it is that programming languages force decisions before you are ready. Do you use a list or a NumPy array? Do you handle the empty case with an exception or a sentinel? Which of these does the algorithm actually care about, and which are incidental? In pseudocode you can defer all of that and see the shape of the idea. When the idea is right, translating it into Python is mechanical — and if it is not mechanical, that is a signal the pseudocode was hiding a decision you had not made.

Conventions we use in this course

• Indentation indicates block structure. No braces, no end keywords.
• ← is assignment; = is comparison. This removes an entire category of ambiguity.
• Arrays are 0-indexed, matching Python and C++. A[i .. j] means indices i through j inclusive; if i > j the range is empty.
• n conventionally denotes the size of the input.
• No type declarations, no memory management, no imports. If a detail does not change the algorithm, leave it out.
• Comments after //, used mainly to record invariants.

Here is MAXIMUM — the procedure §6 will step through — as pseudocode, then in both languages, so you can see exactly what the translation adds and what it leaves untouched.

def maximum(A):
    """Return the largest element of A.

    Precondition:  len(A) >= 1 and elements are mutually comparable.
    Postcondition: result is an element of A, and is >= every element of A.
    Not promised:  which occurrence is returned on ties. A is not modified.
    """
    if len(A) == 0:
        raise ValueError("maximum() requires a non-empty sequence")

    m = A[0]
    for i in range(1, len(A)):
        # invariant: m == max(A[0 .. i-1])
        if A[i] > m:
            m = A[i]
    return m

// Return the largest element of A.
//
// Precondition:  A.size() >= 1 and elements are comparable with >.
// Postcondition: result is an element of A, and is >= every element of A.
// Not promised:  which occurrence is returned on ties. A is not modified.
int maximum(const std::vector<int>& A) {
    if (A.empty()) {
        throw std::invalid_argument("maximum() requires a non-empty vector");
    }

    int m = A[0];
    for (std::size_t i = 1; i < A.size(); ++i) {
        // invariant: m == max(A[0 .. i-1])
        if (A[i] > m) {
            m = A[i];
        }
    }
    return m;
}

Compare the three. The C++ version adds types, a container, and an iteration index of the right unsigned type; the Python version adds an exception and a docstring. Neither changes the algorithm. The comparison count is identical, the memory usage is identical, and the invariant is the same sentence in both. Everything the two implementations argue about is bookkeeping — which is precisely why we design in pseudocode first.

Section 6Correctness

Take that literally for a moment. You write a function and run twenty tests. All pass. What have you established? That the function is correct on twenty inputs. If the input space is all arrays of integers, twenty is not a meaningful fraction of it — and the inputs you chose came from the same brain that wrote the bug, so they are systematically biased toward the cases you already thought about. Tests are indispensable, and you will write many in this course. But testing alone is a sampling strategy applied to an infinite space.

The alternative is not to stop testing. It is to be able to argue, over all inputs at once, that the postcondition follows from the precondition. Two tools do almost all the work, and they are really the same tool wearing different clothes: loop invariants for iteration, and induction for recursion.

6.1 · Loop invariants

Finding the invariant is the creative step; once you have it, the argument is a template with three parts.

1. Initialization. The invariant is true before the first iteration.
2. Maintenance. If it is true at the start of an iteration, it is still true at the start of the next one.
3. Termination. The loop ends, and when it does, the invariant together with the exit condition gives you the postcondition.

Initialization and maintenance are the base case and the inductive step of a proof by induction on the number of iterations. Termination is the payoff — where you cash the invariant in for the thing you wanted to prove. An invariant that is true but does not imply the postcondition at exit is a true statement that is useless; choosing an invariant that is too weak is the common failure.

Step MAXIMUM through below. At every iteration the demonstration shows which slice of the array has been examined, what m currently holds, and whether the invariant claim actually holds — computed against the array, not asserted. Then try the empty array, which is the interesting one.

Now read the same argument in prose, which is what you will write in your project reports.

Notice how much that did. It checked no particular array. It covers every array of every length with every arrangement of values, including the ones you would never think to test. That is what an argument buys you that a test suite cannot.

A second invariant — linear search

Same template, different postcondition, and a negative invariant this time. Specification: given array A of n elements (n ≥ 0) and a target t, return True if t occurs in A and False otherwise.

def linear_search(A, target):
    """Return True if target occurs in A, otherwise False.

    Precondition:  none (A may be empty).
    Postcondition: result is True iff there exists i with A[i] == target.
    Not promised:  the position of the match.
    """
    for i in range(len(A)):
        # invariant: target does not occur in A[0 .. i-1]
        if A[i] == target:
            return True
    return False

// Return true if target occurs in A, otherwise false.
//
// Precondition:  none (A may be empty).
// Postcondition: result is true iff there exists i with A[i] == target.
// Not promised:  the position of the match.
bool linearSearch(const std::vector<int>& A, int target) {
    for (std::size_t i = 0; i < A.size(); ++i) {
        // invariant: target does not occur in A[0 .. i-1]
        if (A[i] == target) {
            return true;
        }
    }
    return false;
}

The invariant is a negative statement — "the target is not in the part already examined" — and that is what makes the argument work. Initialization: before the first iteration the examined range A[0 .. -1] is empty, and the target trivially does not occur in an empty range. Maintenance: we only reach the end of the body when A[i] != target, so extending the examined range by one preserves the claim. Termination: two exits. Returning True happens only having just observed A[i] == target, so a match genuinely exists. Falling out of the loop means i = n, and the invariant says the target does not occur in A[0 .. n-1] — the whole array — so False is right. The empty array needs no special handling: the body never runs and the invariant already covers it. □

6.2 · Recursion and induction

Recursive procedures get the same treatment with the names changed. Instead of initialization and maintenance you have a base case and an inductive step, and the induction runs on the size of the input rather than the number of iterations.

def array_sum(A, i=0):
    """Return the sum of A[i .. len(A)-1].

    Precondition:  0 <= i <= len(A).
    Postcondition: result equals the sum of elements from index i onward
                   (0 when the range is empty).
    """
    if i == len(A):          # base case: empty range
        return 0
    return A[i] + array_sum(A, i + 1)

// Return the sum of A[i .. A.size()-1].
//
// Precondition:  0 <= i <= A.size().
// Postcondition: result equals the sum of elements from index i onward
//                (0 when the range is empty).
int arraySum(const std::vector<int>& A, std::size_t i = 0) {
    if (i == A.size()) {      // base case: empty range
        return 0;
    }
    return A[i] + arraySum(A, i + 1);
}

Watch it run. Each step pushes a frame; the base case returns 0 and the stack unwinds, each frame adding its own element to what came back. Then flip the switch to the broken version, where the recursive call forgets to advance i.

Base case. When i = n the range is empty and the procedure returns 0, the sum of no elements. Correct.

Inductive step. Assume the procedure is correct for ranges of size k. For a range of size k+1 starting at i, it returns A[i] plus the result of the call on the range starting at i+1 — a range of size k, which by hypothesis returns the correct sum. Adding A[i] gives the sum of the full range. Correct.

Termination. Each call increases i by exactly one and i is bounded above by n, so the base case is reached after finitely many calls.

That third paragraph is not optional, and it is the one people leave out — which is what the broken version is for. Its base case is still perfectly correct and its arithmetic is still fine; only progress is missing, and the stack grows until the runtime kills it. Correctness of a recursive procedure has two obligations: produce the right answer if it returns, and return. When we reach recurrence relations and the Master Theorem in Week 3, "how fast does the input shrink" becomes the central question for cost as well as for termination — the same structural fact answering two different questions.

Section 7Before next session

If any part of the setup fails, email me before Tuesday rather than arriving stuck — we lose real working time to environment problems, and they are always faster to fix in advance. Setup instructions are in the repository, and we run a guided session this week for anyone who wants to do it together.