D. Topics in Computer Science · Topics in Computer Science: Sustainability, Ethics, Emerging Technologies and CareersTheoretical Computer Science: Graphs, Automata and the Limits of Computing
D4.2About 75 minutes
Learning goals- I can model problems with graphs and use breadth-first search to find shortest paths in Python.
- I can describe, trace and program a deterministic finite automaton.
- I can explain the halting problem and why some problems can't be solved by any program.
- I can investigate a topic in theoretical computer science and produce a report.
Words to know
graph
A set of vertices joined by edges, used to model networks and relationships.
breadth-first search (BFS)
A graph search that visits vertices level by level using a queue, finding shortest paths in unweighted graphs.
adjacency list
A way to store a graph by listing each vertex's neighbours.
deterministic finite automaton (DFA)
A machine with finitely many states that reads symbols one at a time and accepts or rejects a string.
computability theory
The study of which problems can be solved by any algorithm at all.
halting problem
Deciding whether any given program halts on a given input; Turing proved no program can do this in general.
undecidable
Describes a yes-or-no problem that no algorithm can always answer correctly.
The theory behind the code
Every program you write rests on ideas from theoretical computer science: what can be computed, how efficiently, and how to describe problems precisely with mathematics. Expectation D4.2 asks you to investigate a topic in theoretical computer science (examples include cryptography, graph theory, logic, computability theory, attribute grammar, automata theory, data mining, artificial intelligence, robotics, computer vision and image processing) and produce a report.
In Grade 11 (ICS3U) you met cryptography, AI and data mining, robotics and computer vision. This lesson introduces three topics that are new: graph theory, automata theory and computability. At the end you'll choose one topic for your report.
Graph theory
A graph is a set of vertices (nodes) joined by edges. Graphs model road and transit networks, friendships (social network analysis, from Interdisciplinary Research), web links, computer networks and dependencies between tasks (you met these in Gantt and PERT charts in Grade 11).
Breadth-first search (BFS) finds the fewest edges from a start vertex to every other vertex. It visits vertices in levels: first the start, then all its neighbours, then their unvisited neighbours, and so on, using a queue (first in, first out).
from collections import deque
graph = {
"A": ["B", "C"], "B": ["A", "D"], "C": ["A", "D", "E"],
"D": ["B", "C", "F"], "E": ["C", "F"], "F": ["D", "E"],
}
def bfs(graph, start):
dist = {start: 0}
queue = deque([start])
while queue:
v = queue.popleft()
for w in graph[v]:
if w not in dist:
dist[w] = dist[v] + 1
queue.append(w)
return dist
print(bfs(graph, "A"))
print(bfs(graph, "F"))
The graph is an adjacency list: a dictionary from each vertex to its neighbours. deque gives a fast queue.
{'A': 0, 'B': 1, 'C': 1, 'D': 2, 'E': 2, 'F': 3}
{'F': 0, 'D': 1, 'E': 1, 'B': 2, 'C': 2, 'A': 3}
Output of the program above (what Python prints).
Automata theory
An automaton is a mathematical model of a machine. The simplest is a deterministic finite automaton (DFA): a finite set of states, a start state, some accepting states, and a rule that says, for each state and input symbol, which state comes next. A DFA reads a string one symbol at a time and accepts it if it ends in an accepting state.
DFAs are behind text search, input validation, the lexers that break your Python code into tokens, and the regular expressions in many programming languages. They are deliberately limited: a DFA has no memory except its current state. For example, no DFA can check that an arbitrarily long string of brackets is balanced, because that needs unlimited counting; more powerful machines (with a stack) can.
Worked exampleExample 1: Running the DFA by hand
Trace the DFA on the binary strings (a) 110 (six) and (b) 1011 (eleven). Which are accepted?
- (a) Start in r0. Read 1: (2 × 0 + 1) mod 3 = 1 → r1. Read 1: (2 × 1 + 1) mod 3 = 0 → r0. Read 0: (2 × 0 + 0) mod 3 = 0 → r0.
- It ends in r0, the accepting state: accepted. Check: 6 = 3 × 2. ✔
- (b) r0 → read 1 → r1 → read 0 → r2 → read 1 → (2 × 2 + 1) mod 3 = 2 → r2 → read 1 → (2 × 2 + 1) mod 3 = 2 → r2.
- It ends in r2: rejected. Check: 11 = 3 × 3 + 2, remainder 2. ✔
(a) accepted (ends in r0) (b) rejected (ends in r2, remainder 2).
delta = {("r0", "0"): "r0", ("r0", "1"): "r1",
("r1", "0"): "r2", ("r1", "1"): "r0",
("r2", "0"): "r1", ("r2", "1"): "r2"}
def accepts(s, start="r0", accepting={"r0"}):
state = start
for ch in s:
state = delta[(state, ch)]
return state in accepting
for s in ["110", "1011", "1001", "1111"]:
print(s, int(s, 2), accepts(s))
The transition function is a dictionary keyed by (state, symbol). int(s, 2) converts binary to decimal so we can check the answers.
110 6 True
1011 11 False
1001 9 True
1111 15 True
Output of the program above (what Python prints).
Computability: problems no program can solve
In 1936 Alan Turing described a simple mathematical model of computation, now called a Turing machine, and proved that some problems can't be solved by any program. The most famous is the halting problem: write a program halts(p, x) that always correctly answers whether program p eventually stops when given input x.
Proof sketch (by contradiction). Suppose halts existed. Build a program trouble(p) that calls halts(p, p); if the answer is "halts", trouble loops forever, and if the answer is "loops forever", trouble stops. Now ask: what does trouble(trouble) do? If it halts, then halts said it halts, so it loops forever. If it loops forever, halts said so, so it halts. Both are impossible, so halts can't exist.
This is why no tool can perfectly detect every infinite loop or every piece of malware. Practical tools work on most cases and accept that some answers will be "don't know" or occasionally wrong.
Logic
Propositional logic (AND, OR, NOT, implication) is the mathematics of the conditions in your if statements and of digital circuits. Hard open questions in logic and complexity, such as the famous P versus NP problem (can every problem whose solution is quick to check also be solved quickly?), are central to theoretical computer science and to cryptography.
Just for funThere are only 10 kinds of people in the world: those who understand binary, and those who don't.
(The DFA in this lesson would reject that joke: 10 in binary is two, which isn't divisible by 3.)
Hands-on activityTheoretical computer science report
You need: a computer with Python and internet access, and presentation software or a website builder (optional).
- Choose one topic from D4.2's list: graph theory, logic, computability theory, automata theory, attribute grammar, cryptography, data mining, artificial intelligence, robotics, computer vision or image processing. (If you choose a topic from Grade 11, go deeper than that lesson.)
- Research the topic's key definitions, one important result (for example BFS finds shortest paths in unweighted graphs; the halting problem is undecidable), who developed it and when, and two real applications.
- Write or adapt a short Python program that demonstrates one idea (BFS on a map of your town, a DFA that validates a pattern, a truth-table generator), and explain its output.
- Produce a report (website, presentation or video) with a worked example, a diagram you made yourself, and numbered references.
What to look for: accurate definitions, a correctly explained result, a working program with explained output, applications linked to the theory, and reliable references (textbooks, university course notes, ACM or IEEE sources).
Your turn
1What are the vertices and edges of a graph? Give a real example.
Vertices are the objects (nodes); edges connect pairs of them. Example: transit stations (vertices) and direct routes (edges).
2What does bfs(graph, "F") return for the lesson's graph?
{'F': 0, 'D': 1, 'E': 1, 'B': 2, 'C': 2, 'A': 3}.
3Why does BFS use a queue rather than a stack?
A queue processes vertices in the order they were found, so all vertices at distance k are processed before distance k + 1. That guarantees the first distance found is the shortest.
4Trace the DFA on 1001 (nine). Is it accepted?
r0 →1→ r1 →0→ r2 →0→ r1 →1→ r0: ends in r0, accepted (9 = 3 × 3).
5State the halting problem in your own words.
Is there a program that can always correctly decide, for any program and input, whether that program will eventually stop? Turing proved there isn't.
6Name two real uses of DFAs or regular expressions.
For example: validating input (postal codes, email formats), text search, and lexers in compilers and interpreters.
More practice: warm-up
Deterministic finite automaton.
2Who proved the halting problem undecidable, and in what year?
3In the lesson's graph, what is the distance from A to E?
4What does int("1111", 2) return?
5Is 1111 accepted by the DFA?
Yes: 15 is divisible by 3 (r0 → r1 → r0 → r1 → r0).
More practice: on your own
1Add an edge between A and F to the graph (in both lists). What does bfs(graph, "A") return now?
{'A': 0, 'B': 1, 'C': 1, 'F': 1, 'D': 2, 'E': 2}. F is now a neighbour of A.
2Explain why the DFA's rule is new remainder = (2 × old + bit) mod 3.
Appending a bit to a binary number doubles the number and adds the bit: n' = 2n + b. Only the remainder matters, so (2n + b) mod 3 = (2 × (n mod 3) + b) mod 3.
3Design a DFA (states and transitions) that accepts binary strings with an even number of 1s.
Two states: even (start, accepting) and odd. On 0, stay in the same state; on 1, switch (even ↔ odd).
4Why can't an antivirus program perfectly detect every possible malicious program?
Deciding in general what an arbitrary program will do is undecidable, like the halting problem. So detectors use signatures and heuristics, which can miss some malware and wrongly flag some safe programs.
5Give a real problem that can be modelled as shortest paths in a graph.
For example: the fewest transfers between transit stations, the fewest network hops between routers, or "degrees of separation" in a social network.
Challenge
1Modify bfs to also record each vertex's parent (the vertex it was discovered from), then write path(parent, target) that rebuilds the shortest path. What path does it give from A to F in the original graph?
def bfs_path(graph, start, target):
parent = {start: None}
queue = deque([start])
while queue:
v = queue.popleft()
for w in graph[v]:
if w not in parent:
parent[w] = v
queue.append(w)
path = []
while target is not None:
path.append(target)
target = parent[target]
return path[::-1]
From A to F it returns ['A', 'B', 'D', 'F'] (B is discovered before C, so D's parent is B).
2Write the delta dictionary for a DFA that accepts binary multiples of 4, and explain why it only needs to look at the last two bits.
States r0 to r3 with (2k + b) mod 4 transitions: r0: 0→r0, 1→r1; r1: 0→r2, 1→r3; r2: 0→r0, 1→r1; r3: 0→r2, 1→r3; accept r0. A number is divisible by 4 exactly when its last two bits are 00, because 4 = 2², and all earlier bits represent multiples of 4.
3In the halting-problem proof, why is it essential that trouble is given itself as input?
Feeding a program its own description creates self-reference: halts must predict a program that does the opposite of whatever halts predicts about it. That contradiction shows no correct halts can exist (a technique called diagonalization).
Quiz
1. What does breadth-first search compute in an unweighted graph?
2. In the lesson's DFA, which state does the string 10 (two) end in?
3. What did Alan Turing prove about the halting problem in 1936?
4. Which task is a DFA unable to do for strings of any length?
5. Which data structure does BFS use to decide which vertex to visit next?
6. Why is the halting problem relevant to security software?
Big idea: D4.2 asks students to investigate a topic in theoretical computer science and produce a report. This lesson introduces graph theory, automata and computability (topics not covered in Grade 11) and sets up the report.
How to help: Ask your teen to trace the DFA aloud on a binary number you choose and check the answer by dividing by 3. Draw a graph of your family's usual routes (home, school, store, work) and have them run BFS by hand.
Common difficulties:
- Confusing BFS (queue, levels) with depth-first search (stack, goes deep first).
- Forgetting that a DFA's answer depends only on the final state.
- The halting-problem proof is subtle; it's fine to understand the idea of self-reference and contradiction without every detail. This is first-year university material.
- Choosing a report topic that is too broad ("AI"); narrow it to one idea and one result.