Some problems are easy to solve, some are hard, and some cannot be solved by any program at all. Theory tells us which is which.
🧮 Growth classes
Polynomial algorithms (n, n², n³) scale to large inputs. Exponential algorithms (2ⁿ) quickly become impossible, and factorial (n!) is worse. P is the set of problems solvable in polynomial time; NP problems can have a solution checked in polynomial time.
Big-O describes how the cost grows, not the exact time. An O(n²) algorithm becomes very slow on large inputs, while O(n log n) stays practical.
🛑 The halting problem
Alan Turing proved that no program can decide, for every program and input, whether it will stop. Some problems are undecidable. When no exact algorithm is practical we use heuristics and approximations.
2ⁿ doubles for every +1 in n
from n = 20 to n = 30: ×1024
Turing machine: tape + head + rules (states)
brute-force a 3-digit lock: 10³ = 1000 tries
Exponential does not scale. Even a computer a million times faster only adds about 20 to n.
✏️ Quick check · 1 of 7
P class
A problem is in class P if it can be:
Efficient.
✏️ Quick check · 2 of 7
Halting problem
The halting problem shows that:
Turing.
✏️ Quick check · 3 of 7
Heuristic
A heuristic is used when:
Rule of thumb.
✍️ Type your answer · 4 of 7
An algorithm needs 2ⁿ steps.
How many steps for n = 10?
Enter an exact answer, without rounding.
Powers of two.
✍️ Type your answer · 5 of 7
The same algorithm runs for n = 20.
How many steps?
Enter an exact answer, without rounding.
Powers of two.
✍️ Type your answer · 6 of 7
Routes through 10 cities (start fixed, direction ignored): (n − 1)!/2 with n = 10 is 9!/2.
How many routes? (9! = 362 880)
Enter an exact answer, without rounding.
Divide by two.
✍️ Type your answer · 7 of 7
A 3-digit lock is opened by trying all combinations 000 to 999.
What is the maximum number of tries?
Enter an exact answer, without rounding.
Count the codes.
📝 Lesson quiz · 5 questions
0 / 5
Re-read the lesson, then give it another go.
Question 1 of 5
Which growth is hardest to handle as n grows?
Question 2 of 5
NP means:
Question 3 of 5
A Turing machine is:
Question 4 of 5
An undecidable problem is one for which:
Question 5 of 5
Approximation algorithms:
Lesson 2 · Algorithms
🗺️ Graph Algorithms in Depth
Maps, networks, schedules and recommendations are all graph problems. A few algorithms cover most of them.
🧭 Shortest paths and spanning trees
For weighted graphs: Dijkstra finds shortest paths from one node, and a minimum spanning tree (Kruskal or Prim) connects all nodes with the least total weight using n − 1 edges.
4 nodes, edges: AB 1, BC 2, CD 3, AC 4, BD 6
Kruskal: take AB 1, BC 2, CD 3 (no cycle)
MST weight = 6, edges = 4 − 1 = 3
A* adds a heuristic: f = g + h
g = 5 travelled, h = 3 estimated → f = 8
🖼️ See it
Edges: A–B 4, A–C 1, C–B 2, B–D 1, C–D 5. Always visit the unvisited node with the smallest distance. The shortest route to D is A → C → B → D, of length 4.
🔀 Ordering and flow
A topological sort orders tasks so every prerequisite comes first (only for graphs with no cycles). Graphs can store data as an adjacency matrix (n × n) or an adjacency list.
tasks: A before B, A before C, B before D, C before D
one valid order: A, B, C, D
adjacency matrix of 6 nodes: 6 · 6 = 36 entries
undirected graph with 5 edges: degree sum = 2 · 5 = 10
Matrix vs list: lists use less memory for sparse graphs.
✏️ Quick check · 1 of 7
MST
A minimum spanning tree:
Cheapest connection.
✏️ Quick check · 2 of 7
Topological sort
A topological sort requires the graph to be:
No loops of dependency.
✍️ Type your answer · 3 of 7
A graph has 4 nodes. A spanning tree uses n − 1 edges.
How many edges does it have?
Enter an exact answer, without rounding.
n − 1.
✍️ Type your answer · 4 of 7
Edges AB 1, BC 2, CD 3, AC 4, BD 6. Kruskal picks AB, BC and CD.
What is the MST weight?
Enter an exact answer, without rounding.
Add the three edges.
✍️ Type your answer · 5 of 7
In A* the cost so far g = 5 and the heuristic h = 3.
What is f = g + h?
Enter an exact answer, without rounding.
Add.
✍️ Type your answer · 6 of 7
An adjacency matrix for a graph with 6 nodes is 6 × 6.
How many entries does it have?
Enter an exact answer, without rounding.
Multiply.
✍️ Type your answer · 7 of 7
An undirected graph has 5 edges.
What is the sum of all node degrees?
Enter an exact answer, without rounding.
Handshake lemma.
📝 Lesson quiz · 5 questions
0 / 5
Re-read the lesson, then give it another go.
Question 1 of 5
Which structure suits a sparse graph better?
Question 2 of 5
A cycle in a graph is:
Question 3 of 5
A* is faster than Dijkstra mainly because it:
Question 4 of 5
Which problem fits a graph?
Question 5 of 5
Dijkstra fails when edges have:
Lesson 3 · AI
🤖 Machine Learning Basics
Machine learning lets programs improve from examples instead of following rules written by hand. The ideas are simple: fit a model, measure the error, reduce it.
📊 Learning from data
In supervised learning a model learns from labelled examples. Regression predicts a number and classification predicts a category. In unsupervised learning (such as clustering) there are no labels. Always test on data the model has not seen.
model: y = 2x + 1
x = 3 → prediction 7; true value 8 → error = 1, squared error = 1
mean squared error over errors 1, 2, 3 → (1 + 4 + 9)/3 = 4.67
data split: 80% train, 20% test of 500 examples → 100 test
🖼️ See it
Testing on data the model has never seen is what reveals overfitting.
📉 Gradient descent and evaluation
Gradient descent improves the parameters step by step in the direction that reduces the error: new = old − learning rate × gradient. Classifiers are judged by accuracy, precision and recall.
Overfitting means the model memorises the training data and fails on new data.
✏️ Quick check · 1 of 7
Overfitting
Overfitting is when a model:
Memorising.
✏️ Quick check · 2 of 7
Supervised
Supervised learning needs:
Labels.
✍️ Type your answer · 3 of 7
A model predicts y = 2x + 1. For x = 3 the true value is 8.
What is the squared error?
Enter an exact answer, without rounding.
Square the difference.
✍️ Type your answer · 4 of 7
Errors on three predictions are 1, 2 and 3.
What is the sum of squared errors?
Enter an exact answer, without rounding.
Square and add.
✍️ Type your answer · 5 of 7
w = 5, the gradient is 4 and the learning rate is 0.5.
What is the new w (w − rate × gradient)?
Enter an exact answer, without rounding.
Apply the update rule.
✍️ Type your answer · 6 of 7
A classifier gives 85 correct predictions out of 100.
What is the accuracy, in %?
Enter an exact answer, without rounding.
%
Correct ÷ total.
✍️ Type your answer · 7 of 7
A classifier has TP = 8 and FP = 2.
What is the precision, as a decimal?
Enter an exact answer, without rounding.
TP ÷ (TP + FP).
📝 Lesson quiz · 5 questions
0 / 5
Re-read the lesson, then give it another go.
Question 1 of 5
A test set is used to:
Question 2 of 5
Clustering is an example of:
Question 3 of 5
Which indicates bias in a model?
Question 4 of 5
The learning rate controls:
Question 5 of 5
A neural network is made of:
Lesson 4 · Security
🔑 Cryptography
Modern security relies on mathematics that is easy in one direction and very hard to reverse. That is how strangers can share secrets over the internet.
🔒 Symmetric, asymmetric and hashing
Symmetric encryption (AES) uses one shared key and is fast. Asymmetric encryption (RSA) uses a public key to encrypt and a private key to decrypt, which solves the problem of sharing a key. A hash (SHA-256) is a one-way fingerprint used to check integrity and store passwords.
AES-128 key: 2¹²⁸ possible keys (cannot be brute-forced)
SHA-256 output: 256 bits = 32 bytes
small change in the input → completely different hash
digital signature = hash signed with the private key
🖼️ See it
Anyone can lock the message; only the holder of the private key can open it.
🧮 A tiny RSA example
RSA uses modular arithmetic. Choose primes p and q; n = p·q; φ = (p − 1)(q − 1); public exponent e; private exponent d with e·d mod φ = 1.
p = 3, q = 11 → n = 33, φ = 2 · 10 = 20
e = 3, d = 7 (3 · 7 = 21 = 1 mod 20)
encrypt m = 4: 4³ mod 33 = 64 mod 33 = 31
decrypt: 31⁷ mod 33 = 4
17 mod 5 = 2; (3 · 7) mod 20 = 1
Real RSA uses primes hundreds of digits long, so factoring n is impractical.
✏️ Quick check · 1 of 7
Public key
In asymmetric encryption, a message is encrypted with the recipient’s:
Public.
✏️ Quick check · 2 of 7
Hashing
Hashing is:
One-way.
✏️ Quick check · 3 of 7
Signature
A digital signature proves:
Authenticity.
✍️ Type your answer · 4 of 7
p = 3 and q = 11 in RSA.
What is n = p · q?
Enter an exact answer, without rounding.
Multiply.
✍️ Type your answer · 5 of 7
φ = (p − 1)(q − 1) with p = 3 and q = 11.
What is φ?
Enter an exact answer, without rounding.
Multiply the reduced primes.
✍️ Type your answer · 6 of 7
Encrypt m = 4 with e = 3 and n = 33: c = 4³ mod 33.
What is c?
Enter an exact answer, without rounding.
Divide 64 by 33 and keep the remainder.
✍️ Type your answer · 7 of 7
SHA-256 outputs 256 bits.
How many bytes is that?
Enter an exact answer, without rounding.
Divide by 8.
📝 Lesson quiz · 5 questions
0 / 5
Re-read the lesson, then give it another go.
Question 1 of 5
Why is asymmetric encryption useful?
Question 2 of 5
HTTPS combines asymmetric and symmetric encryption because:
Question 3 of 5
A salt added to a password hash:
Question 4 of 5
Brute-forcing a long random key is:
Question 5 of 5
A man-in-the-middle attack:
Lesson 5 · Systems
🗂️ Operating Systems & Concurrency
The operating system shares the hardware between many programs at once. Scheduling and memory management make this feel seamless, and concurrency creates new kinds of bugs.
⏱️ Scheduling
The OS decides which process uses the CPU. In round-robin scheduling each process gets a fixed time slice in turn. First-come-first-served runs jobs in arrival order.
FCFS: jobs of 4, 3, 2 ms arriving together
waiting times 0, 4, 7 → average = 11/3 ≈ 3.67 ms
round-robin, quantum 2 ms, jobs of 4 and 2 ms:
A runs 2, B runs 2 (finishes), A runs 2 → B waited 2 ms
🖼️ See it
The scheduler picks a ready process to run. It returns to ready when its time slice ends, and waits when it needs input or output. Threads share memory, so shared data needs locks.
🧠 Memory and concurrency
Virtual memory uses disk space when RAM is full, divided into pages. When two processes use shared data at the same time there can be race conditions; locks prevent them but can cause deadlock.
page size 4 KB; a 16 KB program needs 16 / 4 = 4 pages
race condition: counter = 5, two threads each do counter = counter + 1
expected 7 but may get 6
deadlock needs: mutual exclusion, hold and wait, no pre-emption, circular wait (4 conditions)
Lock only what you must and always acquire locks in the same order.
✏️ Quick check · 1 of 7
Deadlock
Deadlock occurs when:
Waiting in a circle.
✏️ Quick check · 2 of 7
Race condition
A race condition happens when:
Timing.
✏️ Quick check · 3 of 7
Round-robin
Round-robin scheduling gives each process:
Turns.
✍️ Type your answer · 4 of 7
A 16 KB program is stored in pages of 4 KB.
How many pages does it need?
Enter an exact answer, without rounding.
Divide.
✍️ Type your answer · 5 of 7
Jobs of 4, 3 and 2 ms arrive together and run first-come-first-served. The second waits 4 ms and the third waits 7 ms.
What is the total waiting time in ms?
Enter an exact answer, without rounding.
ms
Add the waits.
✍️ Type your answer · 6 of 7
The same jobs have a total wait of 11 ms across 3 jobs.
What is the average wait, to one decimal place?
Round your answer as the question asks.
Total ÷ jobs.
✍️ Type your answer · 7 of 7
Deadlock needs how many conditions to hold at once?
Give the number.
Enter an exact answer, without rounding.
Count them.
📝 Lesson quiz · 5 questions
0 / 5
Re-read the lesson, then give it another go.
Question 1 of 5
Virtual memory is:
Question 2 of 5
A process is:
Question 3 of 5
A thread is:
Question 4 of 5
Which is a job of an OS?
Question 5 of 5
Mutual exclusion means:
Lesson 6 · Society
⚖️ Data, Ethics & Society
Technology affects privacy, fairness, jobs and the environment. Good computer scientists ask what should be built, not only what can be.
🔍 Privacy and bias
Laws such as the GDPR give people rights over their personal data: to see it, correct it and have it deleted. Data should be collected for a clear purpose and kept only as long as needed. Algorithms can be biased if the training data under-represents a group, producing unfair decisions.
a hiring model rejects 10 of 40 applicants from group A
and 5 of 50 from group B
rejection rates: 25% vs 10% → a gap worth investigating
anonymising data: remove names, but combined details can still identify people
🖼️ See it
Technology can help or harm; developers and users are expected to weigh these questions before building and deploying systems.
🌱 Impact and responsibility
Computing uses energy (data centres, mining) and creates e-waste. Automation changes jobs. The digital divide leaves some people without access. Developers have professional duties, for example to follow a code of conduct, be honest about limits and protect users.
server uses 500 W for 24 h = 12 kWh
at 0.5 kg CO₂ per kWh → 6 kg CO₂ per day
open source licence: others can read, use and change the code
Ask who is affected before you release software, especially those who are not users.
✏️ Quick check · 1 of 7
Right to erasure
Under data protection law, people can usually ask for their data to be:
Remove.
✏️ Quick check · 2 of 7
Bias source
Algorithmic bias often arises from:
Data.
✏️ Quick check · 3 of 7
Open source
Open-source software is software whose:
Open.
✍️ Type your answer · 4 of 7
A hiring tool rejects 10 of 40 applicants in group A.
What is the rejection rate, in %?
Enter an exact answer, without rounding.
%
Part ÷ whole.
✍️ Type your answer · 5 of 7
The tool rejects 5 of 50 applicants in group B.
What is the rejection rate, in %?
Enter an exact answer, without rounding.
%
Part ÷ whole.
✍️ Type your answer · 6 of 7
A server uses 500 W for 24 hours.
How many kWh is that?
Enter an exact answer, without rounding.
kWh
Convert watts to kilowatts.
✍️ Type your answer · 7 of 7
At 0.5 kg of CO₂ per kWh, the server above uses 12 kWh per day.
How many kg of CO₂ per day?
Enter an exact answer, without rounding.
kg
Multiply.
📝 Lesson quiz · 5 questions
0 / 5
Re-read the lesson, then give it another go.
Question 1 of 5
Personal data includes:
Question 2 of 5
The digital divide is:
Question 3 of 5
Informed consent means users:
Question 4 of 5
Which action reduces e-waste?
Question 5 of 5
A code of ethics for computing professionals asks them to:
Final Challenge
🏆 12-Question Challenge Quiz
Questions from every topic in this course. Pick an answer for each one, then hit Check My Answers.
0 / 12
💪 Keep practicing — go back through the lessons and retake the quiz!
Q1 · Complexity & Computability
Exponential time complexity is written:
Q2 · Complexity & Computability
Approximation algorithms:
Q3 · Graph Algorithms in Depth
The number of edges in a spanning tree of n nodes is:
Q4 · Graph Algorithms in Depth
Dijkstra fails when edges have:
Q5 · Machine Learning Basics
Gradient descent aims to:
Q6 · Machine Learning Basics
A neural network is made of:
Q7 · Cryptography
A certificate authority is trusted to:
Q8 · Cryptography
A man-in-the-middle attack:
Q9 · Operating Systems & Concurrency
The part of the OS that decides which process runs next is the:
Q10 · Operating Systems & Concurrency
Mutual exclusion means:
Q11 · Data, Ethics & Society
Collecting only the data you actually need is called:
Q12 · Data, Ethics & Society
A code of ethics for computing professionals asks them to: