Dynamic programming solves a big problem from the answers to smaller ones and remembers them: the ways to climb n stairs are the ways for n − 1 plus the ways for n − 2
You climb a staircase one or two steps at a time. In how many different ways can you reach the top? Build the answer up stair by stair from the answers before it, and see why remembering answers beats working them out again and again.
Halving the range each time finds any number from 1 to 100 in at most 7 guesses, because 7 halvings are enough to shrink 100 numbers to 1 (2⁷ = 128): the idea behind binary search
Think of a number from 1 to 100 and let the computer guess. It always guesses the middle of what is left, and each “too high” or “too low” throws half the numbers away. Count its guesses and find the number that makes it work hardest.
The work a program does grows with its input: one loop over n items takes about n steps, a loop inside a loop takes n × n, and halving n each time takes only about log₂ n; Big O names this growth
Count the steps three small programs take for the same n: one loop, a loop inside a loop, and a loop that halves n. Double n and see one count double, one grow four times and one hardly move: a first look at Big O.
Big O describes how an algorithm's steps grow with the size of its input n: O(1) stays the same, O(log n) grows by one when n doubles, O(n) doubles, O(n log n) a little more than doubles, and O(n²) quadruples
Race a hash lookup, binary search, linear search, merge sort and bubble sort as the number of items grows from 8 to 1024. See some lines barely rise while bubble sort shoots up past half a million steps, and learn the Big O names for how each one grows.
Breadth-first search (BFS) visits cells in order of distance using a queue, so its path is always a shortest one; depth-first search (DFS) follows one way as far as it can using a stack, so its path can be longer
Send a search through a maze, one cell at a time. Breadth-first search spreads out in rings with a queue and finds the shortest way; depth-first search dives down one corridor with a stack. Compare the paths they find and how many cells each one visits.
Bubble sort compares each pair of neighbours and swaps them when they are in the wrong order; each pass carries the largest number left to the end, and a pass with no swaps means the list is sorted
Watch bubble sort put a list of numbers in order, one comparison at a time. Count the comparisons and swaps, see the largest number bubble to the end after every pass, and compare a jumbled, a sorted and a reversed list.
A network of friends is a graph; when every link counts as 1, the shortest path is the fewest links, found by settling people in order of how many links away they are, nearest first
In a small network of friends, find how many links separate two people: a friend is 1 link away, a friend of a friend 2. A shortest-path search spreads out from one person, nearest friends first, and finds the fewest links, or shows that someone cannot be reached at all.
Linear search compares the target with each item in order; it needs 1 comparison at best and as many as there are items at worst, or when the target is missing
Search a list of test marks or shop prices for a number, checking one item at a time. Count the comparisons when the number is first, in the middle, last, or not in the list at all.
A greedy algorithm makes the best-looking choice at each step: for change, it gives the largest note that still fits, again and again, until nothing is left
A shopkeeper's program gives change in Nepali notes and coins. Run it for different amounts and watch the greedy rule at work: always give the largest note that still fits. Count the notes, and find out when being greedy is not the best plan.
Insertion sort keeps a sorted part on the left and inserts the next number into it by sliding it past every bigger number; on a list that is nearly sorted it does very little work
Watch insertion sort take each number in turn and slide it left into its place among the numbers already sorted, the way you sort cards in your hand. Count its comparisons and swaps, and compare it with bubble sort and selection sort on a jumbled, a sorted and a reversed list.
A number is prime when only 1 and itself divide it; a program tests divisors with %, stops at the first one that divides, and only needs to try divisors up to the square root, because any bigger factor comes with a smaller partner
Choose a number and watch a program try divisors 2, 3, 4 … with the remainder. It stops at the first divisor it finds, or as soon as the divisor times itself is bigger than the number. Count the tries and find out why it never needs to go further.
Binary search compares the target with the middle of a sorted list and throws away the half it cannot be in, so 16 items need at most 5 comparisons instead of 16; it only works on sorted input
Search 16 numbers two ways: one by one, and by halving the list at each step. Compare the comparisons each needs, then run binary search on a list that is not sorted and see it miss a number that is there.
Merge sort divides the list into halves until each part has one number, then merges sorted parts by always taking the smaller front number; its comparisons grow like n log n, far slower than the n² of bubble sort
Split a list of eight numbers in half again and again until every part holds one number, then merge the parts back, always taking the smaller front number. Count the comparisons and compare them with bubble sort and insertion sort on jumbled, sorted and reversed lists.
Selection sort looks through the unsorted part for the smallest number and swaps it into the next place at the front; it always makes the same number of comparisons, but at most one swap per pass
Watch selection sort put a list in order by finding the smallest number left and swapping it to the front, pass after pass. Count its comparisons and swaps, and compare it with bubble sort on a jumbled, a sorted and a reversed list.
Dijkstra's algorithm settles towns in order of their distance from the start; each settled town's distance is final, and trying the roads out of it can only make the other towns' distances shorter
Find the shortest way by road from Kathmandu or Pokhara to another town. Watch Dijkstra's algorithm settle the nearest town first, try the roads out of it, and keep the shortest distance it has found to every town.
An algorithm is a list of exact steps done in order; changing the order or one step changes the result, and debugging means finding the step where the plan breaks
Put move and turn blocks in order so a robot crosses a 5 × 5 grid to its battery. Run a broken plan to find the block where it bumps into a wall, fix it, and then find the shortest plan.
A Caesar cipher replaces each letter with the letter a fixed number of places (the shift) further along the alphabet, going round from Z back to A; shifting back by the same number decodes it
Hide a message by moving every letter the same number of places along the alphabet, then read it back by moving the other way. Watch the program code a word letter by letter, see what happens after Z, and crack a coded word.
A state machine is always in one of a few states and moves to the next state by a rule; a traffic light keeps its state in a variable and goes round red, green, yellow with (state + 1) % 3
Run a traffic light for a number of ticks. A loop moves it from red to green to yellow and back to red, using one variable for the state and % to go round again. Count each colour's turns and predict the light at any tick.
A big problem is easier when it is broken into small parts (decomposition); each part becomes a few steps, and a mistake in one part, such as one move too many, breaks the whole plan
Guide a robot through a 7 × 7 maze to its battery. Break the long route into short parts, find the block where a plan with a counting mistake breaks, and build the shortest plan.
A linked list stores each item in a node with a link to the next node; adding at the front is instant, but reaching node i means following i links from the head
Build a train where each carriage is hooked to the next one. Add a carriage at the front or after another, take one out, and find one, and count how many links you have to follow each time, because a linked list has no index to jump to.
A stack keeps items in a pile: push puts an item on the top, pop takes the top item off and peek only looks at it, so the last item in is the first one out (LIFO)
Push plates onto a stack, pop them off and peek at the top. See why the last plate you put on is always the first one you take off, and what happens when you try to pop from an empty stack.
A queue keeps items in a line: enqueue adds an item at the rear, dequeue takes the item at the front and front only looks at it, so the first item in is the first one out (FIFO)
Serve customers at a ticket counter with a queue: new people join at the rear, the person at the front is served first, and front shows who is next. See why a queue is fair, and what happens when nobody is left to serve.
In a binary search tree every number on a node's left is smaller and every number on its right is bigger, so a search throws away half the tree at each step, but only while the tree stays bushy and short
Insert seven numbers into a binary search tree, smaller ones to the left and bigger ones to the right. Search it with very few comparisons, print it in order, and see how numbers that arrive already sorted turn the tree into a long chain.
To check brackets, push each opening bracket on a stack; a closing bracket must match the bracket on top, which is popped; at the end the stack must be empty
Every ( needs a ), every [ a ] and every { a }, closed in the right order. Watch a program check an expression with a stack: push each opening bracket, pop it when the matching one closes, and stop at the first bracket that does not fit.
A hash table turns each key into a bucket number with a hash function; adding and finding a key look in that one bucket, so they stay fast however many keys there are, as long as collisions are few
Add names to a table of buckets, where a hash function works out each name's bucket from its letters. See two names land in the same bucket (a collision), find a name by looking in one bucket only, and change the number of buckets to spread the names out.
A list (array) keeps items in order; each item has an index, counted from 0, so a list of n items has indexes 0 to n − 1
Keep a shopping list in a program. Read an item by its index, change one, add and remove items, and find out what happens when you ask for an index past the end of the list.
A two-dimensional array is a list of rows, each a list of values; grid[row][col] picks one value, a loop along a row or down a column adds them up, and two nested loops visit every cell
Store a class's marks in a table with a row for each student and a column for each subject. Read one mark with grid[row][col], add up a student's row or a subject's column, and find the highest mark with a loop inside a loop.
A traversal visits every node of a tree once; pre-order visits a node before its children, in-order between its left and right children, post-order after them, and level order row by row with a queue
Build a binary search tree of seven numbers and walk it four ways: in-order, pre-order, post-order and level by level. See four different orders of the same numbers, why in-order comes out sorted, and how a queue walks the tree row by row.
An if / else statement checks a condition: when it is true the program runs the then part, otherwise the else part, never both
Change the chance of rain and run a small program that decides whether to take an umbrella. Watch the condition turn true or false, see which branch runs, and fix a condition that gives the wrong answer.
NOT turns true into false; AND is true only when both parts are true; OR is true when at least one part is true, so a long condition can be worked out one part at a time
Tell the program whether it is raining, whether your homework is done and whether it is a holiday, and watch it work out each part of the rule with NOT, AND and OR before it decides whether you can play outside.
Conditions can be joined with AND (all must be true) and OR (one is enough), and an if / else can sit inside another, so the program checks one question after another until one is true
Enter marks in maths, science and English and run a result program: it works out the total and the percentage, checks with AND that every subject is passed, and then uses nested if / else to give the division. Find the marks that reach each branch.
A year is a leap year when it divides by 4 and not by 100, or when it divides by 400; the remainder % tests divisibility and AND / OR join the rules into one condition
Choose a year and run a program that decides whether February has 29 days. See how the remainder operator % tests divisibility, and how AND and OR join three rules into one condition that gets 1900 and 2000 right.
A loop condition joined with AND stops as soon as either part is false: here when the PIN is right or when three tries are used up
An ATM gives you three tries to type your PIN. Choose the PINs typed on each try and run the program: a while loop keeps asking while the card is locked AND fewer than three tries are used, then either welcomes you or blocks the card.
A function keeps a rule in one place: to_fahrenheit(c) returns c × 9 ÷ 5 + 32, and every call gives it a new argument for its parameter c
Write to_fahrenheit(c) once and use it for Kathmandu, Jumla and Biratnagar. Change each town's temperature, watch every call get its own c, and see one rule give three answers.
Euclid's rule gcd(a, b) = gcd(b, a % b) makes the numbers smaller at every call, so a recursive function reaches its base case, b = 0, where the answer is a
Find the greatest common divisor (HCF) of two numbers with a function that calls itself: gcd(a, b) calls gcd(b, a % b), and the numbers shrink until the remainder is 0. Watch the call stack, count the calls, and see which pairs share no divisor but 1.
fib(n) = fib(n − 1) + fib(n − 2) with fib(0) = 0 and fib(1) = 1; because each call makes two more, the number of calls grows very fast, and the same answers are worked out many times
Work out Fibonacci numbers with a function that calls itself twice. Count the calls as n grows, watch the same small calls happen over and over on the call stack, and see why remembering answers is so much faster.
A function is a named set of steps written once and used many times: its parameters receive the arguments of each call, and return sends its answer back to where it was called
Define a function area(length, breadth) once and call it for a kitchen, a hall and a bedroom. Watch each call open a new frame with its own parameters, see the value it returns, and change the bedroom's size to reach a target area.
A recursive function solves a problem by calling itself on a smaller version of it; a base case answers the smallest version directly, so the calls stop and the answers come back up the call stack
Work out factorials with a function that calls itself. Watch the call stack grow one frame for every call down to the base case, then shrink as each call returns its answer, and see why a recursive function needs a base case.
To move n disks, move the top n − 1 out of the way, move the biggest, then move the n − 1 back on top; the same plan solves the smaller towers, so the moves double and add one each time: 2ⁿ − 1
Move a tower of disks from peg A to peg C, one disk at a time, never a bigger disk on a smaller one. A recursive plan solves it for any number of disks: watch the calls and the moves, and find the pattern 2ⁿ − 1.
In nested loops the inner loop runs all the way through for every turn of the outer loop, so a table of r rows and c columns has r × c products
Print a multiplication table with two loops, one inside the other: the outer loop chooses the row, the inner loop goes along it. Change the size of the table, count the products, and see how the inner loop starts again on every row.
n % 10 is the last digit of n and floor(n / 10) is n without it, so a while loop that repeats both until n is 0 visits every digit once
Choose a number and watch a while loop take it apart: % 10 gives the last digit, dividing by 10 drops it, and the loop adds each digit to a total until the number reaches 0. Count the digits on the way.
A loop can make a decision on every repeat: i % 3 == 0 is true when 3 divides i exactly, and in a chain of ELSE IFs the first true check wins, so the most special case must come first
Count from 1 to n, but say Fizz for multiples of 3, Buzz for multiples of 5 and FizzBuzz for multiples of both. Watch the remainder decide each number, and see why the order of the checks matters.
A loop repeats the same lines: a for loop runs once for each value of its counter, an accumulator adds something on every repeat, and a while loop repeats until its condition becomes false
Choose how many times a loop repeats, then run or step through it: watch the counter go up, each repeat light up and the running total grow, and learn when a while loop stops, and when it never does.
A while loop repeats its body as long as its condition is true, so the body must change something that makes the condition false in the end, or the loop never stops
Save the same pocket money every week until you have enough for something you want. A while loop keeps adding while the savings are less than the price: count the weeks, see the loop stop, and find out what makes a loop run forever.
In nested loops the inner loop runs completely for every turn of the outer loop; when the inner loop goes from 1 to row, row r prints r stars and n rows print n(n + 1)/2 stars
Run two loops, one inside the other, to print a triangle of stars. Change the number of rows, count how many times the inner loop runs, and work out how to turn the triangle into a square.
A variable is a named box that holds one value; an assignment works out the right-hand side and puts the answer in the box, replacing what was there, and the program uses the latest value
Buy notebooks at a shop with a small program: put in the price, how many and the money you pay, then step through it and watch each variable's box fill and change until the total and the change are printed.
Repeatedly dividing a number by 2 gives its binary digits as the remainders, from the last bit to the first; each remainder is placed one place further left
Choose a number and run the algorithm that turns it into binary: divide by 2, keep the remainder as the next bit, and repeat until nothing is left. Watch the bits build up from the right and count how many a number needs.
A string is a list of characters with indexes from 0; a loop can visit each one in turn, and two pointers moving in from both ends test a palindrome with only half as many comparisons
Go through a word one letter at a time: count its letters and its vowels, write it backwards, and test whether it is a palindrome by comparing letters from both ends at once.