Data Structures and Algorithms Concepts: No Coding Needed

Every phone app starts from the same place: a long row of numbered boxes. Maya has six songs, Rain, Moon, Fire, Sea, Wind and Snow, and they sit in lockers numbered 200 to 205, side by side with no gaps. When she taps song five, the phone does one sum, 200 plus 4, and opens box 204. You will see why that is so quick, and why adding a new song, Star, at the front is slow: every song shifts one box along, starting from the far end. Then the same songs are scattered across memory, each with a small note giving the next box. Reaching the fifth song now opens five boxes, but adding at the front takes just two changes. By the end you will understand that a data structure is an arrangement of boxes plus small notes, and that each arrangement is quick at some jobs and slow at others. You will meet these ideas in undo buttons, print jobs, contact lookups and the route on a map.

You will learn:

- Why memory is a row of numbered boxes where any box opens equally quickly

- How one sum, start plus the songs in front, takes the phone straight to a song

- Why adding a song at the front of a numbered row moves every song

- How boxes plus small notes make a chain, and what that makes quick and slow

- The four parts of the course: in a line, finding fast, connected, and methods

School trip sign-ups give this lecture its example. Emma has five ids, twelve, seven, nine, four and nine, and she wants to know whether anyone signed up twice. The handshake way makes every id meet every id after it, and it takes nine steps. The guest book way looks each id up once, writes it in, and spots the repeat in five steps. You will learn to count steps and to watch how they grow: four friends make six handshakes, ten make forty-five, and a hundred make four thousand nine hundred and fifty. The handshake way is at its slowest when nobody repeats, because every pair has to meet, so we always plan for the worst case. That way of describing how the cost grows with the list is called Big-O. You will meet the same question when a site checks a username at sign-up, when a game checks collisions, when a database matches two tables, and when a long list is sorted.

You will learn:

- How to count the steps of a job instead of guessing whether it is slow

- Why the handshake way grows like the list times the list

- Why the guest book way grows only in step with the list

- Why we plan for the worst case, when nobody repeated

- What Big-O means, and why a lookup is often the better choice

Emma's playlist keeps growing, so a fixed list with two slots is not enough. This lecture builds a dynamic list, using an egg box as the picture: when the box is full, you get a box twice the size and move everything across. You will follow five songs, Sunny, Rain, Stars, Waves and Night, through two grows and see that six songs are moved in all. Doubling makes the moving rare, so adding at the end stays cheap, and any slot is one jump away because the slots are equal and sit side by side. The slow case is squeezing a song into the middle or the front, where every song after it slides one slot along. A hundred thousand songs show the gap: about one hundred thirty-one thousand moves at the end, and almost five billion slides at the front. Dynamic arrays such as Python lists, Java ArrayLists and C++ vectors use this general approach; their exact growth factors differ, and so do long texts and data coming in from the internet.

You will learn:

- Why a fixed list never gets bigger, and how a dynamic list fixes that

- Why any slot is one jump away when the slots are equal and side by side

- Why doubling the box makes the moving rare, compared with growing by one slot

- Why squeezing a song into the middle slides every song after it

- Where growing lists appear in real software

Jack's party has a treasure hunt, and it shows how a linked list works. Every clue says only where the next clue is, so the hunt is a chain: Garden, Shed, Treasure. Putting a new clue in front takes two moves, and the lecture follows place numbers, so you see that a move is just copying a number. Slipping Pond in between Garden and Shed also takes two changes, but only if you do them in the right order, and you will watch what happens when the order is wrong and part of the chain is lost. The price is finding a clue far down: there is no shortcut, so Jack follows the chain one hop at a time, ninety-nine thousand nine hundred and ninety-nine hops for the last of a hundred thousand clues. You will meet linked lists inside hash tables, in a cache that forgets the oldest item, in a computer's free memory, and in a queue of jobs.

You will learn:

- How each clue holds what it says and where the next clue is

- Why putting a clue in front is two moves, however long the chain is

- Why the order of the moves matters when slipping a clue in

- Why finding a clue far down is one hop for every clue

- What a doubly linked list adds, and what it costs

Press undo in a tiny editor, and the newest action is taken back first. Emma types Hello, then Jack, then makes it bold, and the lecture uses a stack of plates to explain what is going on: a new plate goes on top, and the top plate comes off first. You will learn the three words push, pop and peek, and the rule last in, first out. Her story is played step by step on five slots, so you can watch the top move up and down while the other actions stay where they are. Every move touches only the top, so a stack of three plates and a stack of a million cost the same one step. The one thing to watch is popping an empty stack, which is an error, and the reason the undo button goes grey. You will meet stacks in undo, in the back button of a browser, in functions calling other functions, and in checking brackets in a code editor.

You will learn:

- Why the newest thing in is the first thing out

- What push, pop and peek mean

- Why each move is one step, however big the stack is

- What happens when you pop an empty stack

- Where stacks appear in editors, browsers and programs

Picture the ticket line at a cinema. Emma asks for a ticket first, then Jack, then Tom, and the app must serve them in that order. This lecture explains first in, first out with three words: enqueue to join at the back, dequeue to leave from the front, and peek to look at the front. Inside the program the line is a row of cells with two markers, so nobody has to step forward when someone leaves, and the markers wrap round like a ring. You will play a four-cell line step by step, then break it on purpose: with two cells and three people, Tom writes over Emma, and the first ticket goes to the wrong person with no warning at all. That is why a real queue checks whether the line is full before someone joins. Queues appear in print jobs, chat messages, requests to a busy website and customer support calls.

You will learn:

- Why the first one in is the first one out

- What enqueue, dequeue and peek mean

- How a front marker and a back marker avoid moving everyone forward

- How the markers wrap round a ring of cells

- Why a full line must be checked before someone joins

Finding Jane among a thousand contacts is the problem here. Checking names one by one could take a thousand checks, so the lecture uses an address book with letter tabs instead. The name itself tells you which tab to open, and names that share a tab share a short list. You will learn the words hashing, bucket and collision, and play Emma, Jack, Tom and Jane into twenty-six tabs, where Jack and Jane land together. The catch is a rule that looks only at the first letter: five names starting with J all pile into tab nine, and getting Jess takes five checks. Two fixes keep the lists short: a rule that mixes every letter, and doubling the tabs once the book is three quarters full. Hash tables are behind contact lookups, spell checkers, remembered web pages and word counts, which is why they come up in so many apps.

You will learn:

- How a rule turns a name into a tab number so you jump straight to it

- What hashing, bucket and collision mean

- Why a rule that uses only the first letter piles names onto one tab

- How a better rule keeps every list short

- Why the book adds tabs as it fills up

How many dolls are hiding inside one Russian doll? Emma finds out by doing the same job again and again: open the doll, and if a smaller one is inside, do the same job on that one. The tiny solid doll does not open, so the job stops there, and the count is added up on the way back. You will learn the base case, the pile of waiting jobs that remembers the way back, and the two rules every recursive job follows: make the problem smaller, and give the smallest piece a stop rule. Then the lecture takes the stop rule away, and the pile fills until the program gives up with a stack overflow. The work grows with the number of dolls, and so does the pile. You will meet recursion in folders inside folders, in sorting a long list, in trees such as a family tree, and in mazes and puzzles.

You will learn:

- How the same job on a smaller piece finds the number of dolls

- What the base case is, and why the smallest piece needs one

- Why the answers come back in reverse order, using the pile of waiting jobs

- What happens without a stop rule, or when the pieces do not get smaller

- Why the work and the pile both grow with the number of dolls

Higher or lower? That guessing game is the way into binary search trees. Emma hides a number card, Jack guesses, and every answer throws away half of the cards, so sixty is found in three looks instead of six. You will build the tree from fifty, thirty, seventy, twenty, forty, sixty and eighty: smaller goes left, bigger goes right. Then you will see where it breaks. If the cards arrive already sorted, every card goes right, the tree becomes a stick, and a search takes seven looks for seven cards, no better than checking a list. The same cards in a better order give just three levels. Because every new level doubles the room, twenty levels hold over a million cards. Search trees sit behind databases, behind the sorted maps and sets of many languages, behind the way Linux picks the next job, and behind lookups such as every price from thirty to sixty.

You will learn:

- How a higher or lower game turns into a tree of cards

- How to insert a card by walking one path down to an empty spot

- How a balanced search tree keeps the search path short

- Why sorted cards turn the tree into a stick, and how the order of arrival fixes it

- How one walk finds the smallest, the biggest and where a new card belongs

Walking round Emma's house, room by room, explains tree traversals. The house has seven rooms, and each room has at most two doors, one on the left and one on the right, just like the cards of a search tree. The tour rule in every room is: left side first, then this room, then the right side. Played on the cards, it prints twenty, thirty, forty and so on up to eighty, sorted, without any sorting at all. You will also see the other two tours, this card first and this card last, and what each is good for: copying a tree, and cleaning one up. A tour visits every card once, so a million cards mean a million visits. The cost to watch is room: a tall, thin tree makes the tour keep many rooms waiting, and every tour needs a rule to step back when a door leads nowhere. You will meet tours when reading a sorted list, showing a folder, deleting a folder, and working out a formula.

You will learn:

- What a traversal is, and why we call it a tour

- Why left side, this card, right side gives sorted cards in a search tree

- How the card first and card last tours differ, and what each is for

- Why the work grows with the number of cards, and the room with the height of the tree

- Why every tour needs a stopping rule

Four patients in a hospital waiting room show why we need heaps. They are Emma, Jack, Tom and Kate, each with an urgency number, and one is the most urgent. Kate came in last, but she must be seen first. Checking every patient each time the doctor is free is slow, so the lecture uses a game of king of the hill: a new kid joins at the bottom and swaps upward, and when the king leaves, the last kid jumps to the top and sinks. A computer keeps the hill in a row of seats, and the seat numbers alone tell you who is above and who is below. Adding and taking out are each one trip along a hill that is only about twenty levels tall, even for a million patients. The weak spot is finding one particular patient, because a heap promises only the top. Task schedulers, route finders, timers and top ten scores all use heaps.

You will learn:

- Why checking everyone each time is slow, and what a heap does instead

- How a new patient climbs the hill and how the top is taken out

- How seat numbers tell you the kids and the parent of every seat

- Why the hill is only about twenty levels tall for a million patients

- Why finding one particular patient is the weak spot

Looking up the word kite shows two ways to find something in a list. Going page by page takes eleven looks. Opening the dictionary in the middle and throwing half away each time takes only four. This lecture follows the halving on fifteen sorted words: fifteen, seven, three, one. You will learn why a million words need only about twenty checks, and why doubling the words adds just one more check. Then you will see where it breaks: if the list is not in A to Z order, binary search trusts the order, throws away the wrong half, and says kite is not there, with no crash and no warning. The trade is simple: sort once, then search as often as you like. You will meet the idea in spell checkers, in the contacts on your phone, in the guess the number game, and in finding the change that broke a program.

You will learn:

- The difference between linear search and binary search

- How each check throws half of the list away

- Why a million words need only about twenty checks

- Why binary search gives a wrong answer on an unsorted list

- Why sorting once and searching many times pays off

Playing cards give the picture for insertion sort. Emma is dealt seven, three, nine, two and five, and she sorts them the way people do: take the next card and slide it left past every bigger card until it fits. The lecture counts the slides, and this hand needs six. A hand that arrives backwards needs ten, the most it can ever cost for five cards, and a hand already in order needs none. You will see why the work climbs so fast: ten cards in the worst order cost forty-five slides, and a hundred thousand cost nearly five billion. When the hand gets ten times bigger, the work gets about a hundred times bigger. So insertion sort is a good choice for small or almost sorted lists, and a poor one for huge mixed-up lists. You will meet it in hands of playing cards, inside bigger sorting methods, in a leaderboard when a new score arrives, and in log lines that come in almost in time order.

You will learn:

- How the sorted part on the left grows by one card each time

- How to count the slides for any hand

- Why the same five cards can cost between zero and ten slides

- Why the work grows about a hundred times when the hand gets ten times bigger

- When insertion sort is a good choice and when it is not

Exam papers piled on a desk are the example for merge sort. Ms Kate has eight marked papers, and she wants them in order of score. The idea is to split the pile in half again and again until each pile is one paper, and then to merge sorted piles by always taking the lower top paper. You will see that eight papers need three levels of merging, with eight papers placed on each level, which is twenty-four steps. A million papers need only about twenty levels, so about twenty million steps. A messy pile, an ordered pile and a backwards pile all cost the same. The price is room: merging inside the same row can wipe out a paper that has not been placed yet, so a merge needs a second place as big as both piles together. Java and Python sort their lists with a method built on merging, and databases and searches across many servers use the same idea.

You will learn:

- How merging two sorted piles works, one top paper at a time

- Why splitting down to single papers gives piles that are already sorted

- Why eight papers cost twenty-four steps, and a million about twenty million

- Why the order of the papers does not change the work

- Why a merge needs a second place to work in

Photo day at school gives the picture for quick sort. Seven kids stand in a mixed-up line, and the photographer wants the shortest on the left and the tallest on the right. Pick one kid as the friend, send shorter kids left and taller kids right, and the friend steps into a spot that never changes again. Then the same trick runs on each side. You will play it with Tom, one hundred fifty centimetres, and finish in ten compares. Then you will break it: if the line is already in order and the friend is always the last kid, the work is twenty-one compares, because nobody goes right. Choosing a pivot near the median gives a more even split; simply choosing the middle position does not guarantee balance. A fair split is why a million kids take about twenty-five million compares. Quick sort sits behind the built-in sort of many languages, behind database results, behind finding the middle value, and behind sorting on many computers at once.

You will learn:

- How one friend splits a line into shorter kids and taller kids

- Why the friend's spot is final after the split

- How the same trick runs on each side until every part is one kid

- Why a line already in order, with a bad friend, costs twenty-one compares instead of ten

- Why pivot choice matters and why a median-like pivot improves balance

Ripples on a pond are the picture for breadth-first search. In Emma's friends app each circle is a person and each line is a friendship, and the app wants to suggest friends of friends, like Kate and Lucy, who are two hops away. You will learn how the computer keeps one list of friends for each person, called an adjacency list, and how a waiting line makes the search spread level by level. Played step by step, it shows why the hops it finds are the fewest possible. Then you will break it by forgetting the note of who has been seen, and watch three friends who all know each other keep the line going for ever. The work follows the size of the network, and nobody is visited twice. You will meet this idea in friend suggestions, in the fewest stops on a metro map, in web crawlers, and in puzzles solved in the fewest moves.

You will learn:

- What a graph is, and how an adjacency list stores it

- How a waiting line makes the search spread level by level

- Why the first hops found are the fewest possible

- Why the note of who has been seen stops the search from going round for ever

- Why the work follows the size of the network

Rooms joined by corridors, like a maze, are the picture for depth-first search. We use the same six friends as in the last lecture, but this time we follow one friend, then that friend's friend, as deep as we can. At a dead end we back up one step and try the next corridor, and we chalk a tick in every room we visit so nobody is visited twice. The lecture plays this with a pile that remembers the way back, and shows why the ticks matter: without them, a loop of friends is walked round and round for ever. Then it shows where depth-first search breaks. A very long row of friends adds one waiting job for every step deeper, so the pile can fill and crash the program. The walk also finds a way to everyone, but not always the shortest way. You will meet it in mazes and puzzles, in folder searches, in checking whether everything is connected, and in putting jobs in order when some need others done first.

You will learn:

- How going deep, backing up and ticking rooms visits everyone once

- How the pile of waiting jobs remembers the way back

- Why the ticks stop the walk from going round in circles

- Why a very long row of friends can crash the program

- Why the way found is not always the shortest

Eight gifts on a shop shelf, sorted from cheapest to dearest, set up this lecture. Emma has a gift card worth thirty-six dollars, and she wants two gifts that add up to exactly thirty-six. Trying every pair means twenty-eight pairs. Two pointers starts at both ends of the sorted list and walks inwards: if the sum is too little, the cheap end steps up, and if it is too much, the dear end steps down. Every check drops one gift for good, and the answer, fourteen plus twenty-two, comes after six checks. You will see why dropping a gift is safe, and then break it on purpose with a list that is not in order, where the wrong gift is dropped and the answer is wrong. For a hundred gifts, trying every pair takes four thousand nine hundred fifty checks, against ninety-nine. You will meet this in budgets on sorted price lists, in words that read the same backwards, in reversing a word, and in merging two sorted piles.

You will learn:

- How two markers at both ends of a sorted list find a pair

- Why every check drops one gift for good

- Why dropping a gift is safe on a sorted list

- Why an unsorted list can give a wrong answer

- Why the checks grow only with the number of gifts, not the gifts times the gifts

Sliding a cardboard frame along a calendar is the picture for this method. Emma sold four, two, seven, one, eight, six and three cups of lemonade over a week, and she wants the best three days in a row. Adding every group of three from scratch takes fifteen steps. Sliding the frame along takes eleven: add the day that comes in, take away the day that leaves, and keep the best total, which turns out to be seventeen, from days five, six and seven. You will see why the width of the window never matters to a slide, and why a hundred thousand days with a window of a thousand days is about five hundred times less work. Then you will break it: a window of eight days on a calendar of seven hangs over the end, and a careful program checks first. Fitness apps, views in the last hour, moving averages and request limits all slide a window along.

You will learn:

- How the new day comes in and the oldest day leaves

- Why the first window is added once, and every slide is two steps

- Why the work is about the number of days, and not the width of the window

- What happens when the window is wider than the calendar

- Where sliding windows appear in real apps

Giving change at a till is the picture for greedy algorithms. Tom buys a juice for seventy-two cents and pays one hundred, so Kate owes twenty-eight cents from a till of ten, five, two and one. The rule is to grab the biggest coin that fits, and never go back: ten, ten, five, two, one, which is five coins in all. Greedy is quick because each coin is one choice, and the lecture shows that a hundred times more money needs only about forty-six times more coins in a full till. Then it breaks the rule. With coins of four, three and one, change for six gives four, one, one, but three and three is only two coins. So the best-looking choice is not always the best in the end, and greedy must be tested before it is trusted. Zip files, route finders, meeting rooms and office cabling all use greedy choices that people have proved give the best answer.

You will learn:

- How the biggest coin that fits gives change one choice at a time

- Why greedy never goes back to change a choice

- Why greedy is quick, even when the amount gets large

- Why the best-looking choice can miss the best answer

- Which question to ask before you trust greedy on a new problem

Climbing stairs is the way into dynamic programming. Emma climbs one or two stairs at a time, and the lecture counts the ways to the top of five stairs: eight. The ways for five stairs equal the ways for four stairs plus the ways for three, so the same small questions keep coming back. The plain way asks them again every time: nine questions for five stairs, and more than two hundred million for forty. The fix is a notebook, called a memo: work an answer out once, write it down, and read it back. You will play it from the top with the notebook, and then fill the notebook from the bottom, which needs only three additions for five stairs. The notebook costs a little space, and it helps only when the same questions come back, which a sorted phone book never does. Spell checkers, file comparison, line breaking in publishing software and some route finders use the same idea.

You will learn:

- How the ways up five stairs are the ways up four plus the ways up three

- Why the plain way works out the same small question again and again

- How a notebook turns repeated questions into one answer each

- Two ways to use the notebook: from the top, or filled from the bottom

- When a notebook helps, and what it costs