Maths and computer science · Solid · Dissertation or artefact

How compression makes files smaller: a maths EPQ idea

Why it works as an EPQ

Huffman coding is a short algorithm with a proof of optimality, and entropy gives a clear limit to test against.

Scope and difficulty

Solid. Solid. Huffman coding and entropy on texts you choose.

The maths

Builds on these A Level topics: Probability · Exponentials and logarithms.

You would learn:

• Prefix codes and binary trees
• Entropy
• Optimality of Huffman codes

Learning maths beyond the course is expected in a maths EPQ, but you must understand and explain everything you use.

One possible plan

1. Build Huffman codes by hand for small texts.
2. Calculate the entropy and compare average code length with it.
3. Implement it and test on English text, code and random data.
4. Judge why some files barely compress.

Pitfalls

• Forgetting to count the space needed to store the code table.
• Lossy and lossless compression mixed up.

Where to start reading

• Search for: Huffman coding optimality proof
• Search for: Shannon entropy source coding theorem simple

Prefer books, lecture notes, journal articles and official data to a single website, and record every source as you read (how to reference).

Making something? Read the artefact guide first: an artefact still needs a research-based written report.

Similar ideas

• How a neural network learnsHow does a neural network learn, and how much of it is calculus you already know?Computer scienceAmbitiousDissertation or artefact
• Quick routes for the travelling salesmanHow close can quick methods get to the best route in the travelling salesman problem?Computer scienceSolidDissertation or artefact
• How computers fake randomnessHow can a computer, which follows rules, produce random numbers, and how random are they?Computer scienceSolidDissertation or artefact
• Hash collisions and the birthday problemHow likely are two different files to share a hash, and what does the birthday problem say about security?Computer scienceSolidDissertation

All maths and computer science ideas · all 93 ideas

Your EPQ must be your own work. These pages coach: ideas, structure, checklists and planning. Submitting text, proofs, code or analysis written by someone else or by an AI tool as your own is malpractice. How to use help and AI honestly.