Difficulty: Introductory to Intermediate | Prerequisites: Basic programming concepts, introductory maths
Big Picture: This material covers two foundational pillars of computer science that you will use in nearly every course that follows. Data structures and algorithms are about organising data and solving problems efficiently. Programming language theory is about how programming languages are designed, analysed, and formally verified. Together, they form the bridge between abstract computation and practical software. If you are new to programming, make sure you can write basic loops and conditionals before tackling this material.
Data structures are ways of organising data so it can be accessed and modified efficiently; algorithms are step-by-step procedures for solving computational problems. Programming language theory studies how languages are designed, what they can express, and how to prove software correct. Formal methods use mathematics to specify and verify that software and hardware behave as intended.
Data structure
A way of organising and storing data so that it can be accessed and modified efficiently. Examples include arrays, linked lists, trees, hash tables, and graphs. Think of it as: the filing system you choose for your data, which determines how fast you can find, add, or remove things.
Algorithm
A finite, well-defined sequence of steps that solves a specific computational problem. Think of it as: a recipe that a computer follows to get from input to output.
Computational efficiency (time and space complexity)
A measure of how an algorithm's resource usage (time or memory) scales with input size. Usually expressed using Big-O notation, e.g. O(n), O(n log n), O(n²). In simple terms, this tells you whether your algorithm will still be usable when the input gets large.
Programming language theory (PLT)
The branch of computer science concerned with the design, implementation, analysis, and classification of programming languages and their features. It draws on mathematics, software engineering, and linguistics.
Formal methods
Mathematically rigorous techniques for specifying, developing, and verifying software and hardware systems. Think of it as: using mathematical proof to guarantee that a program does what it is supposed to do, rather than just testing it and hoping.
Formal verification
The process of using formal methods to prove that a system meets its specification. Distinct from testing, which can only show the presence of bugs, not their absence.
Program semantics
The mathematical study of what programs mean, i.e. what a program actually computes. Includes operational semantics (step-by-step execution rules), denotational semantics (mapping programs to mathematical objects), and axiomatic semantics (reasoning about programs using logical assertions).
Data structures and algorithms are studied together because the choice of data structure directly affects which algorithms are efficient
Common data structures at the introductory level: arrays, linked lists, stacks, queues, trees (binary trees, binary search trees), hash tables, graphs
Common algorithm categories: sorting (bubble sort, merge sort, quicksort), searching (linear search, binary search), graph traversal (BFS, DFS)
Computational efficiency is measured by how time and space requirements grow with input size
Big-O notation gives an upper bound on growth rate
O(1) is constant time, O(log n) is logarithmic, O(n) is linear, O(n log n) is linearithmic, O(n²) is quadratic
The goal is to choose or design algorithms that solve problems correctly using the fewest resources
PLT sits at the intersection of computer science, mathematics, software engineering, and linguistics
It covers the design, implementation, analysis, and classification of programming languages
Key concerns include:
Type systems: rules that assign types to expressions, catching certain errors before runtime
Syntax and parsing: the formal grammar that defines valid programs
Semantics: what programs mean, mathematically
Language paradigms: imperative, functional, object-oriented, logic-based, and others
PLT is an active research area with its own dedicated academic journals
Formal methods use mathematical techniques to specify what a system should do and to verify that it does so
They complement testing: testing shows that specific inputs produce correct outputs, but formal verification can prove correctness for all possible inputs
In practice, the cost of applying formal methods is high, so they tend to be used only in high-integrity or safety-critical systems (aviation, medical devices, nuclear controls, financial systems)
Formal methods draw on logic, automata theory, type theory, and program semantics
They form a theoretical foundation for software engineering, particularly where reliability or security is paramount
Every piece of software you use depends on data structures and algorithms. A search engine uses graph algorithms and inverted-index data structures to return results in milliseconds. Formal methods are used in industries where failure is not an option: the flight control software on commercial aircraft, cryptographic protocol verification, and hardware chip design all rely on formal verification to guarantee correctness before deployment.
Students often think a faster algorithm is always better. It is not. An algorithm with better Big-O complexity may have large constant factors or overhead that make it slower for small inputs. Context matters.
A common confusion is treating Big-O as an exact measurement. O(n²) does not mean the algorithm takes exactly n² steps; it means the growth rate is at most quadratic for large n.
Students sometimes believe formal verification replaces testing entirely. It does not. Formal methods verify against a specification; if the specification itself is wrong or incomplete, the verified program can still behave unexpectedly in practice.
PLT is sometimes dismissed as "just theory." In reality, every language feature you use (type checking, garbage collection, pattern matching) exists because of PLT research.
⚠️ Be able to identify appropriate data structures for a given problem (e.g. when to use a hash table vs. a binary search tree).
⚠️ Know the Big-O complexities of common sorting algorithms (bubble sort: O(n²), merge sort: O(n log n), quicksort: average O(n log n), worst O(n²)).
⚠️ Understand the difference between testing and formal verification, and when each is appropriate.
⚠️ Be prepared to explain what a type system does and why it is useful.
True or False: An array allows O(1) access to any element by index.
Fill in the blank: Big-O notation describes the ______ bound on an algorithm's growth rate.
True or False: Formal verification can prove a program is correct for all possible inputs.
Fill in the blank: The branch of CS that studies the design and classification of programming languages is called ______.
True or False: Merge sort has a worst-case time complexity of O(n²).
Q: What is the difference between a data structure and an algorithm?
A: A data structure is a way of organising and storing data. An algorithm is a step-by-step procedure that operates on data (often stored in a data structure) to solve a problem. The two are closely linked because the choice of data structure affects which algorithms are efficient.
Q: What does O(n log n) mean in plain language?
A: It means that as the input size n grows, the algorithm's running time grows proportionally to n multiplied by the logarithm of n. This is typical of efficient sorting algorithms like merge sort.
Q: Why are formal methods not used for all software?
A: Formal verification is expensive and time-consuming. The cost is justified for safety-critical or high-integrity systems (aircraft, medical devices, cryptographic protocols), but for most commercial software, testing and code review are more cost-effective.
Q: Name three concerns that programming language theory addresses.
A: Type systems, language semantics (what programs mean), and the classification of language paradigms (imperative, functional, object-oriented, etc.).
Q: What is the worst-case time complexity of quicksort, and when does it occur?
A: O(n²). It occurs when the pivot selection consistently produces maximally unbalanced partitions, e.g. when the input is already sorted and the first or last element is always chosen as pivot.
Data structures and algorithms connect to virtually every other area of CS. Information theory relies on efficient algorithms for encoding and decoding. Computer graphics uses specialised data structures (scene graphs, spatial partitioning trees). Formal methods connect to logic and automata theory, which you will encounter in courses on theory of computation. Programming language theory influences every language and tool you will use throughout your degree.
Data structures, algorithms, Big-O notation, time complexity, space complexity, arrays, linked lists, stacks, queues, binary trees, binary search trees, hash tables, graphs, sorting algorithms, bubble sort, merge sort, quicksort, linear search, binary search, BFS, DFS, programming language theory, PLT, type systems, formal methods, formal verification, program semantics, operational semantics, denotational semantics, axiomatic semantics, automata theory, computability, safety-critical systems