The Project | About Us | Contribute | Donations | License

HOME

In this first lesson we lay the groundwork for the entire course: what exactly an algorithm is, which properties it must satisfy to deserve that name, and the different ways we can express one before writing a single line of code. Getting these fundamentals right is essential, because everything else in the course —complexity analysis, design strategies, classic algorithms, and optimization— is built on top of them. We will also introduce RutaBus, the fictional urban mobility app that will accompany us as the running case study throughout the course.

RutaBus: the course's running case study
What is an algorithm (and what isn't)?
Properties of an algorithm
Ways to express an algorithm
From pseudocode to Python code: a first RutaBus example
Motivation: some algorithms are better than others

RutaBus: the course's running case study

Imagine you work on the development team of RutaBus, an app that helps city residents plan their public transport journeys. The app handles information such as:

Stops: physical points around the city ("Main Square", "North Station", "Central Hospital"...), each with its coordinates.
Lines: bus routes (L1, L2, L3...) that connect sequences of stops.
Timetables: the times at which each line passes through each stop.
Transport network: the full set of stops and connections, which we will later model as a graph.

Almost every RutaBus feature hides an algorithm:

RutaBus feature	Underlying algorithmic problem
"Which stop is closest to me?"	Finding the minimum in a collection
"Show me the next buses sorted by time"	Sorting
"Does the stop 'Main Square' exist?"	Searching
"How do I get from A to B in the least time?"	Shortest path in a graph

Over the course we will solve these problems progressively: first with simple solutions and, as we learn to analyze and design them better, with increasingly efficient ones.

What is an algorithm (and what isn't)?

An algorithm is a finite, ordered sequence of unambiguously defined steps that transforms input data into output results in order to solve a specific problem.

The classic analogy is a cooking recipe: ingredients (input), precise steps (process), and a finished dish (output). But the analogy has its limits: "add salt to taste" is acceptable in a recipe and would not be in an algorithm, because it is ambiguous.

It is worth distinguishing an algorithm from nearby concepts it is often confused with:

Concept	What is it?	Is it an algorithm?
Algorithm	An abstract solution method, independent of any language	Yes
Program	A concrete implementation of one or more algorithms in a language	No: it is their materialization
Informal heuristic	"Try things until something works"	No: it guarantees neither well-defined steps nor termination
Specification	Describes what must be done, not how	No: it lacks the process
Infinite process	A server handling requests nonstop	Not as a classical algorithm: it never terminates

Examples of things that are not algorithms:

"Find the best route" → that is a goal, not a method: it doesn't say how.
"Repeat until the result is good" → ambiguous: what does "good" mean?
A while True loop with no exit condition → it fails finiteness.

The same algorithmic idea can be implemented in Python, Java, or C and it remains the same algorithm. This language independence is what will allow us, in Module 2, to analyze algorithms without worrying about the specific machine they run on.

Properties of an algorithm

For a sequence of steps to be an algorithm, it must satisfy five classic properties (formulated by Donald Knuth):

Finiteness: it must terminate after a finite number of steps. A computation that never ends solves nothing.
Definiteness (precision): every step must be defined without ambiguity. Two people (or two computers) following the algorithm on the same input must do exactly the same thing.
Well-defined inputs: it must be clear what data it receives (there may be zero or more). In RutaBus: the list of stops and the user's position.
Well-defined outputs: it must produce at least one result, and it must be clear what that result is. In RutaBus: the nearest stop.
Effectiveness: each step must be basic enough to be carried out mechanically in finite time. "Compute the distance between two points" is effective; "guess which one feels closest" is not.

Let's see this with a RutaBus example. The instruction "find a stop that is near the user" violates definiteness (what does "near" mean?) and well-defined output (which one, if there are several?). By contrast:

"Given the user's coordinates and the complete list of stops, return the stop whose Euclidean distance to the user is minimal; in case of a tie, the first one in the list."

...satisfies all five properties: it terminates (the list is finite), it is precise (Euclidean distance, tie-breaking rule), it has a clear input and output, and every step can be mechanized.

Ways to express an algorithm

The same algorithm can be expressed at different levels of formality. The three most common forms are natural language, pseudocode, and the flowchart.

Natural language

This is the most accessible form, ideal for communicating the general idea:

Find the nearest stop:

Take the first stop in the list and provisionally consider it the nearest one.

Go through the remaining stops one by one.

For each stop, compute its distance to the user; if it is smaller than the current candidate's, that stop becomes the new candidate.

When the traversal ends, the candidate is the nearest stop.

Its big drawback: it is easy to slip into ambiguity and to overlook edge cases (what if the list is empty?).

Pseudocode

Pseudocode is a middle ground: it uses programming structures (conditionals, loops, variables) but without the strict syntax of any particular language. It is the usual way of describing algorithms in books and technical documentation.

ALGORITHM nearest_stop
INPUT:   user (coordinates x, y), stops (non-empty list of stops with name and coordinates)
OUTPUT:  the stop with minimal distance to the user

    best_stop     ← stops[0]
    best_distance ← distance(user, stops[0])

    FOR EACH stop IN stops[1..end] DO
        d ← distance(user, stop)
        IF d < best_distance THEN
            best_distance ← d
            best_stop     ← stop
        END IF
    END FOR

    RETURN best_stop
END ALGORITHM

Notice how pseudocode forces us to pin down details that natural language left loose: the initialization with the first stop, the strict comparison < (which resolves ties in favor of the first stop found), and the returned value.

Flowchart

A flowchart graphically represents the algorithm's control flow: diamonds for decisions, rectangles for actions. It is very useful for visualizing loops and branches:

flowchart TD
    A([Start]) --> B[best_stop = first stop<br/>best_distance = its distance to the user]
    B --> C{Any stops left<br/>to check?}
    C -- Yes --> D[Take the next stop<br/>d = distance to the user]
    D --> E{d < best_distance?}
    E -- Yes --> F[Update best_stop<br/>and best_distance]
    E -- No --> C
    F --> C
    C -- No --> G[/Return best_stop/]
    G --> H([End])

Comparing the three forms

Form	Precision	Ease of reading	Typical use
Natural language	Low	Very high	Communicating the idea to anyone
Pseudocode	High	High (for developers)	Designing and documenting before coding
Flowchart	High	High (visual)	Visualizing control flow, training

In professional practice you usually start with natural language (to understand the problem), refine it into pseudocode (to design the solution), and finally translate it into code.

From pseudocode to Python code: a first RutaBus example

Let's translate the pseudocode above into Python. We will represent each stop as a dictionary with its name and coordinates (on a simplified map of the city):

import math

# Fictional RutaBus data: stops with (x, y) coordinates in km
stops = [
    {"name": "Main Square",      "x": 0.0, "y": 0.0},
    {"name": "North Station",    "x": 2.5, "y": 4.0},
    {"name": "Central Hospital", "x": 1.0, "y": 1.5},
    {"name": "River Park",       "x": 3.0, "y": 0.5},
]

def distance(x1, y1, x2, y2):
    """Euclidean distance between two points in the plane."""
    return math.sqrt((x2 - x1) ** 2 + (y2 - y1) ** 2)

def nearest_stop(user_x, user_y, stops):
    """Returns the stop closest to the user's position.

    Input:  the user's coordinates and a NON-empty list of stops.
    Output: the dictionary of the stop with minimal distance.
    """
    # Step 1: the first stop is the initial candidate
    best_stop = stops[0]
    best_distance = distance(user_x, user_y,
                             best_stop["x"], best_stop["y"])

    # Step 2: go through the remaining stops
    for stop in stops[1:]:
        d = distance(user_x, user_y, stop["x"], stop["y"])
        # Step 3: if it beats the candidate, it takes its place
        if d < best_distance:
            best_distance = d
            best_stop = stop

    # Step 4: when the loop ends, the candidate is the nearest stop
    return best_stop

# The user is at (0.8, 1.0)
result = nearest_stop(0.8, 1.0, stops)
print(f"Nearest stop: {result['name']}")
# Output: Nearest stop: Central Hospital

Let's analyze the code piece by piece:

distance: a helper function that applies the Pythagorean theorem. Encapsulating it in a function makes the main algorithm more readable and reinforces the effectiveness property: every step is a basic, mechanizable operation.
Initialization with stops[0]: just as in the pseudocode, the first stop is the initial candidate. This avoids inventing artificial values like "infinity" and guarantees we always return a real stop (as long as the list is not empty).
for stop in stops[1:]: iterates from the second stop to the end. It is the direct translation of the pseudocode's FOR EACH.
if d < best_distance: the strict comparison means that, in case of a tie, the stop found first is kept — exactly the tie-breaking rule we defined in the specification.
return best_stop: the algorithm's well-defined output.

Note that the algorithm is the same across the three representations (natural language, pseudocode, Python): what changes is the level of detail and the syntax, not the idea.

Motivation: some algorithms are better than others

Our algorithm works, but is it good? To find the nearest stop it checks every stop, one by one. With the 4 stops of the example that is instantaneous. But picture the real network of a large city:

With 4 stops → 4 distances computed.
With 5,000 stops → 5,000 distances computed.
If the app also computes this for thousands of users per second... the cost multiplies.

And there is more than one way to solve the same problem. To preview the intuition: searching for a stop by name by scanning the whole list works, but if the list is sorted there is a technique (binary search, which we will see in Module 4) that with 5,000 stops needs barely a dozen comparisons instead of 5,000. Same problem, same result, radically different effort.

This is the big idea of the course: for the same problem there are usually several correct algorithms, and the efficiency differences between them can be enormous. Learning to compare algorithms rigorously, without stopwatches or specific machines, is precisely the goal of the asymptotic notation lesson (01-03) and of all of Module 2.

Common Mistakes and Tips

Confusing the algorithm with the program. If your solution only exists "in Python", you will struggle to reason about it and compare it with alternatives. Tip: get used to sketching the pseudocode first; the code will practically write itself.
Leaving ambiguous steps. "Pick the best option" is not an algorithm step until you define best with a measurable criterion (minimum distance, earliest time...). Review each step asking yourself: could a machine execute this without asking for clarification?
Forgetting edge cases in the inputs. Our nearest_stop fails on an empty list (stops[0] raises IndexError). A well-specified algorithm states which inputs it accepts; a robust program also validates them.
Not defining the tie-breaking rule. If two stops are at the same distance, which one is returned? Our strict < settles it (the first one wins), but that has to be a conscious decision, not an accident.
Writing code before understanding the problem. Practical tip: first write down the expected input and output with a concrete example (as we did with the user at (0.8, 1.0)). If you cannot produce an example, you do not understand the problem yet.

Exercises

Exercise 1

State which of the following descriptions satisfy the five properties of an algorithm and, if not, which property they violate:

a) "Go through the stops of line L1 and return how many there are." b) "Try routes at random until you find one you like." c) "While the bus hasn't arrived, keep waiting." d) "Given a list of departure times, return the first one after the current time; if there is none, return None."

Exercise 2

Write in pseudocode (not Python) an algorithm has_stop(name, stops) that returns TRUE if a stop with that name exists in the list and FALSE otherwise. Make sure it satisfies all five properties.

Exercise 3

Modify the nearest_stop function in Python so that it returns the two stops closest to the user (the nearest and the second nearest), without sorting the whole list. Assume the list has at least two stops.

Solutions

Solution 1:

a) Yes, it is an algorithm: input (the list of L1 stops), output (a number), precise steps, finite, and effective. b) No: it violates definiteness ("one you like" is ambiguous) and potentially finiteness (it might never end). c) No: it violates finiteness (it may never terminate) and it has no well-defined output. d) Yes, it is an algorithm: note how the clause "if there is none, return None" is what guarantees a well-defined output for every input. Without it, this would be an incomplete specification.

Solution 2:

ALGORITHM has_stop
INPUT:   name (text), stops (list of stops, possibly empty)
OUTPUT:  TRUE if some stop is called `name`, FALSE otherwise

    FOR EACH stop IN stops DO
        IF stop.name = name THEN
            RETURN TRUE
        END IF
    END FOR
    RETURN FALSE
END ALGORITHM

Property check: it terminates (the list is finite), every step is precise and effective (comparing text), and the input and output are defined for any list, including the empty one (it returns FALSE). Common mistake: forgetting the final RETURN FALSE, which leaves the output undefined when the stop does not exist.

Solution 3:

def two_nearest_stops(user_x, user_y, stops):
    """Returns (nearest, second_nearest). Requires len(stops) >= 2."""
    d0 = distance(user_x, user_y, stops[0]["x"], stops[0]["y"])
    d1 = distance(user_x, user_y, stops[1]["x"], stops[1]["y"])

    # Manually order the first two candidates
    if d0 <= d1:
        first, d_first, second, d_second = stops[0], d0, stops[1], d1
    else:
        first, d_first, second, d_second = stops[1], d1, stops[0], d0

    for stop in stops[2:]:
        d = distance(user_x, user_y, stop["x"], stop["y"])
        if d < d_first:
            # The new stop displaces the first; the old first becomes second
            second, d_second = first, d_first
            first, d_first = stop, d
        elif d < d_second:
            # It only beats the second
            second, d_second = stop, d

    return first, second

The key is to keep two candidates and, when a stop better than the first appears, not to lose the old first: it moves down into second place. A very common mistake is overwriting first without copying it into second beforehand.

Conclusion

In this lesson we defined what an algorithm is —a finite, precise, and effective sequence of steps with well-defined inputs and outputs— and what distinguishes it from a program, a vague heuristic, or a mere specification. We saw three ways of expressing one (natural language, pseudocode, and flowchart) and walked the full path down to Python code with our first real RutaBus problem: finding the stop nearest to the user. We also planted an important seed: the same problem admits several correct algorithms, and some are far more efficient than others. In the next lesson, Types of Algorithms, we will bring order to that universe: we will classify algorithms by approach (iterative and recursive), by purpose (searching, sorting, graphs...), and by other dimensions that will help us choose the right tool for each RutaBus problem.

Basic Concepts of Algorithms

Contents