Games and how computers play them

1. Topic 1Game trees and minimax How Can a Computer Never Lose at Tic-Tac-Toe? A short function that calls itself plays out every game of tic-tac-toe there could ever be, and never loses. You need lists and functions in Python (Grades 8 and 9). Recursion is explained here; Grade 11 has the whole story.  
2. Topic 2Search and evaluation How Does a Computer Play Chess? No computer can see to the end of a chess game. So how did one beat the world champion? You need the tic-tac-toe topic before this one (minimax), and lists and functions in Python (Grades 8 and 9). Recursion is in Grade 11.  
3. Topic 3Solving a game Who Wins Bagh-Chal When Nobody Makes a Mistake? Tigers or goats? Computers have worked out who wins Nepal’s own game when both sides play perfectly. You need lists and functions in Python (Grades 8 and 9). The tic-tac-toe and chess topics help; their ideas are retold here.  
4. Topic 4Reinforcement learning Can Matchboxes Learn to Play? Three hundred matchboxes of colored beads learned noughts and crosses with no rules told. The same idea later learned Go. You need lists and dictionaries in Python (Grade 9). Grade 12’s Learning from rewards is the same idea with numbers; this topic doesn’t need it.  
5. Topic 5Backtracking How Is a Sudoku Solved in a Blink? Try a number, and undo it when you get stuck. A computer does this so fast that the hardest Sudoku falls in a moment. You need lists and functions in Python (Grades 8 and 9). Recursion is explained here; Grade 11 has the whole story.  
6. Topic 6Mazes as trees How Do Games Build a New Maze Every Time? A perfect maze has exactly one path between any two squares. A random walk that never makes a loop builds one. You need lists and loops in Python (Grade 9) and breadth-first search (Grade 10). Recursion is explained here; Grade 11 has the whole story.  

Classic puzzles and algorithms

1. Topic 7Compression How Can a Message Use Fewer Bits? Give common letters short codes and rare ones long ones. A student’s term paper found the best way to do it. Coming soon. You need number systems and lists and dictionaries (Grade 9); stacks, queues and heaps (Grade 11).
2. Topic 8Ranking by links How Did Google Find the Best Page on the Web? A page matters if pages that matter link to it. A surfer clicking at random forever finds which ones they are. You need lists and dictionaries (Grade 9); graphs (Grade 10).  
3. Topic 9Stable matching How Can Students Be Matched to Colleges So No One Wants to Swap? A simple loop of offers and refusals always ends in a match nobody would break, and it matters who asks first. Coming soon. You need lists and dictionaries (Grade 9).
4. Topic 10Cellular automata Can Four Rules Make Something Alive? Cells on a grid live or die by four rules, and out of them come shapes that walk across the screen. Coming soon. You need lists and dictionaries (Grade 9).
5. Topic 11Faster multiplication How Did a Student Beat a Great Mathematician at Multiplying? A famous mathematician believed long multiplication couldn’t be beaten. A student proved him wrong within a week. Coming soon. You need counting steps (Grade 9); recursion (Grade 11).
6. Topic 12Heuristics and backtracking How Does a Knight Visit Every Square? A knight hops to all 64 squares once each. One simple rule finds a way almost at once. Coming soon. You need recursion (Grade 11).

Simulating real science

1. Topic 13Chaos Why Can’t Anyone Forecast the Weather a Month Ahead? Change a weather model’s starting numbers in the sixth decimal place, and in a few weeks it forecasts different weather. You need lists and loops in Python (Grade 9); stepping a simulation forward is explained here, and Grade 11 has the whole story.  
2. Topic 14Traffic models Why Do Traffic Jams Appear Out of Nowhere? One driver brakes for a moment, and a jam forms that drives backwards through the traffic. You need lists, loops and the random module in Python (Grade 9); stepping a simulation forward is explained here, and Grade 11 has the whole story.  
3. Topic 15Emergent behavior How Does a Flock Fly with No Leader? Each bird follows three rules about its neighbors. None of them knows the shape of the flock. Coming soon. You need objects and simulation (Grade 11).
4. Topic 16Tipping points When Does a Forest Fire Stop Spreading? A few more trees, and a fire that always died out now nearly always crosses the forest. Coming soon. You need recursion (Grade 11).
5. Topic 17Genetic algorithms Can Evolution Be Run on a Computer? Random changes, keeping the better ones, find good designs far faster than guessing, and sometimes get stuck. Coming soon. You need lists and dictionaries (Grade 9).
6. Topic 18The logistic map How Can One Formula Be Calm, Then Wild? One formula for a population settles down, then swings, then goes wild, as a single number grows. Coming soon. You need lists and dictionaries (Grade 9).

How things work

1. Topic 19Error-correcting codes How Does a Scratched QR Code Still Scan? A few extra bits don’t only show that something went wrong. They say where, and put it right. You need binary numbers (Grade 9) and lists and functions in Python (Grades 8 and 9).  
2. Topic 20Indexes How Does a Search Engine Answer in a Blink? A search engine never reads the web when you search. It has done the reading already. Coming soon. You need lists and dictionaries (Grade 9).
3. Topic 21Image filters How Does a Camera App Find Edges? One small grid of numbers, slid over a photo, blurs it, sharpens it or finds its edges. Coming soon. You need lists and dictionaries (Grade 9).
4. Topic 22Iterative methods How Does a Calculator Find a Square Root? Guess, then improve the guess by a simple average. Each step doubles the correct digits. You need loops and functions in Python (Grade 8). Newton's method is explained here.  
5. Topic 23Calendars as data Why Can’t a Formula Convert Bikram Sambat to AD? Bikram Sambat months change their length from year to year. Every converter carries a table. You need lists and dictionaries (Grade 9). Python’s datetime (Grade 10) is explained where it is used.  
6. Topic 24Transliteration How Does Romanized Nepali Typing Work? Type “nepal” and get नेपाल. The trick is in which pieces of the word are matched first, and in a list of real words. You need lists and dictionaries (Grade 9).  
7. Topic 25Finding pitch How Does a Tuner Hear Which Note You Play? Slide a sound along a copy of itself until they match. How far you slid gives the note. Coming soon. You need lists and dictionaries (Grade 9).

The limits of computing

1. Topic 26Unsolved problems Will This Simple Rule Ever Stop? Halve it if it’s even, triple it and add one if it’s odd. Does every number reach 1? Nobody knows. Coming soon. You need loops in Python (Grade 8).
2. Topic 27Turing machines How Long Can a Tiny Machine Run Before It Stops? A machine with five rules runs tens of millions of steps and then stops. With six, nobody can say. Coming soon. You need the limits of computing (Grade 12).
3. Topic 28Chatbots Can a Computer Fool You into Thinking It’s a Person? A program with a few dozen rules and no understanding at all, and people told it their secrets. You need lists, dictionaries and functions in Python (Grades 8 and 9). The regular expressions it uses are explained here; Grade 11 has the whole story.  

Famous bugs and stories

1. Topic 29Overflow Why Did a Rocket Destroy Itself 37 Seconds After Launch? Code that worked on one rocket was used on a faster one. One number got too big for its box. You need binary numbers (Grade 9) and functions and loops in Python (Grades 8 and 9). Floats and try/except are explained where they are used.  
2. Topic 30Rounding error How Did a Rounding Error Stop a Missile Defense? A tiny error in storing one tenth added up, hour by hour, until a defense system missed. You need 0.1 in binary and floating point (Grade 11), and loops and functions in Python. Fixed point is explained here.  
3. Topic 31Scheduling How Did the Moon Landing’s Computer Survive an Overload? Minutes before landing, the guidance computer flashed alarms. It had been built to drop what mattered least. Coming soon. You need stacks, queues and heaps and floating point (Grade 11).
4. Topic 32Ada Lovelace’s program What Did the First Published Program Do? In 1843 Ada Lovelace published a program for a machine that was never built. Run it today and see. Coming soon. You need lists and dictionaries (Grade 9).
5. Topic 33Grammars and rules Did a Grammar from 2,500 Years Ago Lead to Programming Languages? Pāṇini wrote rules that build Sanskrit words step by step. Programming languages are defined in a similar way. Coming soon. You need lists and dictionaries (Grade 9); recursion (Grade 11).

Making art and music

1. Topic 34Sound synthesis How Does a Computer Make a Sitar-Like Note Out of Noise? Fill a list with random noise, go round it averaging neighbors, and the hiss becomes a plucked string. You need lists and dictionaries (Grade 9); how computers store sound and pictures (Grade 7).  
2. Topic 35Fractals How Does a Computer Grow a Fern? Four simple rules, picked at random, draw a fern. Much of nature’s look is copies of itself. Coming soon. You need lists and dictionaries (Grade 9); recursion (Grade 11).
3. Topic 36The Mandelbrot set What’s the Most Complicated Picture from the Simplest Rule? Square and add, again and again. The points that never fly away make a picture with new detail at every zoom. Coming soon. You need lists and dictionaries (Grade 9); floating point (Grade 11).
4. Topic 37Generating music Can a Computer Compose a Tune That Follows a Raag? A model that picks the next note, with a raag’s rules to keep it in bounds, makes tunes with no idea of a raag’s feeling. Coming soon. You need language models (Grade 10); lists and dictionaries (Grade 9).

Real data from Nepal

1. Topic 38Flow on a height map Which Way Would Rain Flow from Your Roof? Send each square’s water to its lowest neighbor, and Nepal’s rivers draw themselves from heights alone. You need lists and dictionaries (Grade 9); recursion (Grade 11).  
2. Topic 39Earthquake statistics How Often Does Nepal Shake? Small earthquakes are common and big ones rare, in a pattern so regular it makes a straight line. You need pandas (Grade 10). Fitting a line is explained here; Grade 12 has the whole story.  
3. Topic 40Word frequencies Why Do a Few Words Fill Half of Every Book? Count the words in a school book. The most common ones follow a pattern, in Nepali as in English. Coming soon. You need lists and dictionaries (Grade 9).

Where technology is going

1. Topic 41Qubits What Can a Quantum Computer Do That Yours Can’t? A qubit’s chances can cancel out like waves. One question is answered in one look instead of two. Coming soon. You need lists and dictionaries (Grade 9).
2. Topic 42Moore’s law How Long Can Computers Keep Getting Faster? For fifty years the transistors on a chip doubled every two years or so. Can it go on? Coming soon. You need pandas (Grade 10).

Practice

• Unit quizpractise the units you choose, at your level→

How to use this book

These topics go past the school course, for anyone who wants to know more. Each one starts from things you learned in class, linked under its title, so you can look back. Each is a question, with the subject it belongs to beside its number. They are not in any exam. Inside you’ll find:

• Worked examples: try them first; the answer stays hidden until you open it.
• Try it questions and each topic’s questions at the end, with hints and answers to open when you’re ready.
• Diagrams to play with: drag, slide and change things to see what happens.
• Did you know? boxes with the stories and surprises behind the computers.

Every fact here has been checked against reliable sources, but these topics have not yet been reviewed by subject experts. If you find a mistake, please tell us.