Concepts Equations and definitions

Program

A program is a finite description of a computation. In practice it is text, bytecode, or machine code plus assumptions about the runtime environment.

program + input + environment -> output + side effects

The environment matters: files, network, clocks, GPUs, package versions, locale, and permissions can all change behaviour.

Algorithm

An algorithm is a procedure for solving a class of problems. It is more abstract than a program: quicksort is an algorithm; one particular C++ implementation of quicksort is a program.

Data structure

A data structure is a representation chosen to support operations efficiently. The useful question is not “is this structure good?” but “good for which operations?”

array: fast indexed access
linked list: cheap local insertion if node known
hash table: average-case fast lookup by key
graph: relationships between entities

Complexity

Common asymptotic notation:

O(f(n))      upper growth bound
Ω(f(n))      lower growth bound
Θ(f(n))      tight growth bound

For coursework and engineering, pair asymptotics with constant factors and memory movement. An $O(n)$ GPU kernel can still lose to an $O(n)$ CPU loop if launch overhead or PCIe transfer dominates.

Invariant

An invariant is a condition intended to remain true at specific points in a computation. Invariants are the debugging cheat code: when output is wrong, find the earliest invariant violation.

Current local links

• Concepts Key concepts
• Concepts Examples
• Concepts Common pitfalls
• Concepts index