Understanding Big-O Notation and the Wizards' War

Big-O notation is a method of specifying the worst case performance of an algorithm as the size of the problem grows. Big-O notation is important in understanding how algorithms scale and for comparing the relative performance of two algorithms.

Years ago, a ferocious wizards' war raged across the land. Initially sparked by a disagreement over the correct pronunciation of the word “elementary”, things quickly escalated. The battles lasted months, as the two sides fought to break the stalemate. Neither side could gain an upper hand. The strength of the two sides was almost perfectly matched, until a computational theorist shifted the balance of power forever.

Clare O'Connell was not a wizard. Her formal training was as an accountant. She worked in the Bureau of Farm Animal Accounting: Large Mammal Division, where she spent her days tracking the kingdom's cows, horses, sheep, and pigs. It was not an exciting job, but it left her plenty of time to pursue other interests.

Clare had never taken any notice of the war until she was caught in the middle of a battle. Wizards' wars tended to be well separated from daily civilian life. The wizards would bicker and fight amongst themselves, but would rarely resort to any spell that had an impact on the general population. In fact, they avoided spells that could cause any actual physical harm altogether. But during one early May morning, Clare had been accidentally caught in the crossfire. She had been leaving the baker's shop when a stray spell turned her bread into a frog. The true target, a loaf of pumpernickel held by the wizard behind her, remained unscathed and quite edible. Unfortunately, the same could not be said for Clare's bread, which promptly hopped out of her hand and down the street. Clare was furious.

That morning, Clare resolved to break the stalemate and end the war for good. So, she met with the commander of the closest faction. During a three hour meeting, she grilled him about the war’s progress. In the process, she learned how wizards thought about their spells. The interview ended with one, unmistakable conclusion: wizards knew nothing about computational complexity. Years of casting spells had made them lazy and inefficient.

Clare knew that the first side to relearn the importance of computational complexity would win the war. So, she called together all of the wizards from the faction for a tutorial at the local pub.

"Your problem," she began. "Is that your techniques are inefficient."

The wizards mumbled in protest. How dare this accountant lecture them on the art of casting spells? They threatened to transform her drink into oatmeal.

"But there is a solution!" Clare continued. "There is a new technique, called Big-O notation, that will shift the tides. This notation tells you how a spell scales as the size of the battle increases, allowing you to know which spell is most efficient. You simply ask: how many steps you need to cast a spell when facing N different enemies? Then you strip out all the constant factors and focus on just the parts that grow the fastest."

"For example," Clare continued. "If a spell takes 3 steps to cast, regardless of the number of enemies, then it is an O(1) spell -- constant cost. In contrast, if you need a single step for each pair of enemies then the cost is O(N^2) -- quadratic cost. In a large battle, you want spells that will scale well."

The wizards grumbled in protest. "That would never work." "It is simplifying the problem too much." "This accountant is crazy."

Clare was unfazed. "What is your favorite spell?" Clare asked a wizard in the front row.

He turned red at being singled out and mumbled: "The spell of Pairwise Protection."

"Which does?" prompted Clare.

"Well… if you cast it on an enemy and a friend, the friend is protected from that enemy for a full five minutes."

"How long does it take to cast?"

"Two seconds. It is a fast spell."

"But it also depends on how many people are in the battle. Doesn't it?" Clare pointed out. The wizard looked back blankly.

Clare sighed. "When you are in a large battle, you need to understand how the cost of using a spell increases as the number of people in the battle increases. Let's take the spell of Things Smelling Like Fish. You cast it once for each enemy in the battle and they smell rotting fish for the next half an hour. One step for each enemy, so it is a O(N) spell. It scales linearly with the number of enemies."

"In contrast," Clare continued. "the spell of Pairwise Protection requires you to cast it on each pair of friends and enemies. If there are N enemies and M friends, you need to cast it M*N times. So the cost is O(M*N). If you have a lot of friends, that is going to take a while."

"Good thing Henry does not have many friends," someone joked from the back row. A few muffled laughs followed. Clare ignored the comment.

"The spell of Things Smelling Like Fish takes 15 seconds to cast," objected a wizard in the back row. "Your Big-O notation does not capture that!"

"You are correct," admitted Clare. "Big-O notation is only used to compare how spells scale as the size of the battle scales. This is where your strategy is lacking. You are still accustomed to the simpler world of dueling, where the number of enemies is always one. You focus too much on the constant factors."

"Let me assure you," Clare continued, "at some size of battle an O(N^2) spell will always take much much longer than an O(N) spell. At some point the constant factors just do not matter anymore. That is the value of Big-O notation."

The same wizard went back on the offensive. "Are you telling me that it is better to cast the spell of Loud Techno Music, which takes one hour and impacts all enemies, than the spell of Temporary Elevator music, which takes one minute but impacts only one emery? It would seem that that is what your Big-O notation would recommend."

"Yes," said Clare. "If there are more than 60 enemies, the spell of Loud Techno Music is more efficient the spell of Temporary Elevator Music."

The wizard was stunned. He repeated the math over and over in his head to check her answer. She was correct.

"What about the spell of Love Triangles? That takes only 1 second to cast," argued another wizard.

"You need to cast it on ALL triplets of people. So it is O(N^3). If you have twenty opponents, that is 20*20*20 = 8000 seconds! That is over two hours!"

The wizards gasped in unison. They had never though about it like that before.

"Consider the spell of Uncomfortably Long Toenails," suggested Clare. "This spell fell out of favor a few years ago, because it needs a 120 second preparation before casting it for the first time each day. It would not work well in duels. However, once you perform that preparation once, it only takes 5 seconds an enemy. So the spell takes 120 + 5*N seconds for N people. Big-O notation strips out all those constant factors and simply asks 'What happens to the cost as N gets really large?' In this case, the answer is: the spell of Uncomfortably Long Toenails scales linearly. It is an O(N) algorithm, because as N grows that is the term that dominates."

By the end of the night, Clare had convinced all of the wizards in the room to pay attention to the Big-O cost of the spells that they were using. It was a radical shift from the way they had always looked at their spells, where they had focused solely on the cost for each time they cast it. Spells of Broken Command Chains, which had to be cast on all possible orderings of opponents, O(N!), immediately fell out of favor. Spells that scaled well became new standards.

Tired, but satisfied, Clare went home for the night. On her way home, she stopped at the baker's again for a loaf of fresh bread. While standing behind the counter, she noticed the baker using an O(N^3) algorithm to make rolls. With a put-upon sigh, she interrupted the work. "You know that that is not the most efficient way to make rolls…" she began.

--------------

For more on Big-O notation, see Paul the Pessimist and the Log-N Realization.

Checkpointing Checkers

Checkpoints are a technique for improving a program's fault tolerance by preserving the program's state. Checkpoints can be used to recover after a program crashes or used to save the state for later analysis. They are literally dumps from the program that are sufficient to reconstruct the program's current state.

The Powerful Wizard Marcus was traveling to the city of South Atlantis for the annual World Checkers Championships. The competition was legendary, and it attracted all of the best checkers players in the known kingdoms. This year the heavy favorite was Jennifer "King Me" Stratovarious. She had won thirteen of the major competitions in the last six months. Some people said that she was unbeatable. Any match where she played was guaranteed to be exciting. And, Marcus had front row tickets to the finals.

However, Marcus realized that there was a problem as soon as he arrived at the preliminary rounds. The players were playing a frantic pace. They almost looked panicked.

"What is going on?" Marcus asked King Fredrick, who had also journeyed to South Atlantis to watch the world championships.

"They are playing checkers." answered the king.

"I can see that. But, why are they playing so quickly? It almost looks as though they are trying to race through the game."

The king shrugged and returned to watching Jennifer quickly destroy a young novice from South Patagonia. Marcus had never seen a game won in so few moves. Or, for that matter, played so quickly.

Unfortunately, all too soon he understood the reason behind the players' urgency. South Atlantis happened to be the windiest city in the world. Twenty-three minutes into the preliminary round, the entire building started to shake with the force of an industrial paint mixer. Despite the strong walls and shuttered windows, wind swept through the hall. The oil lamps swayed dangerously, people fell down, and the checkers slid off the boards.

After only half a minute, the wind stopped and the contestants began to gather their pieces off the floor. The contestants that had been winning groaned and griped loudly. "This is unfair!"

"Why are they hosting the tournament in such an awful location?" And, in contrast, the contestants who had been on the losing end of the game smiled quietly, for they now had a new chance to win. Only three games had finished before the wind-storm. The winners of those games smiled broadly; they had beaten the disaster.

"Unbelievable," proclaimed King Fredrick. "All those games were lost."

"Bah." declared Marcus. "Inefficient and stupid."

"What can they do? All of those checkerboards crashed to the floor before the games were finished. There was nothing that they could do." Insisted the king.

But, Marcus had stopped listening. Instead, he was wandering down to the nearest competition table.

"Excuse me, there. Why do you make them replay the game?" Marcus asked the judge at that table. "Why not use checkpoints?"

"Checkpoints?" asked King Fredrick, who had followed Marcus down to the floor.

"Yes. Write down the entire state of the board after each move. That way, if the pieces are upset, you can reproduce the entire board from the most recent checkpoint. It would save your games from being lost." explained Marcus.

"HA! Checkpoints?" cried Jennifer "King Me" Stratovarious from behind. "That would be too slow. Have you ever seen how fast I can play checkers?"

Marcus had indeed seen how faster she could play. He had to admit that checkpointing every move could only slow down someone of her caliber. In fact, Marcus was surprised the even a judge could keep up with her.

Marcus grinned widely. "Perhaps I can be of service." he offered. Then, without any more explanation, he picked up the table's timing clock and waved his hands over it. After a moment he set it back down.

King Fredrick looked at the clock. It appeared mostly unchanged, except that it now had two additional buttons "Save" and "Restore".

"May I?" inquired Marcus. Then, without waiting for an answer, he pressed the "save" button. The clock chirped once like a bluejay. Marcus smiled widely at the assembled crowd and, with a quick flick of his hand, knocked the table's board onto the floor. Checkers flew everywhere. The judge and both players scowled at him.

"Now, observe." commanded Marcus with his best wizard's voice. He reached over and pressed the "Restore" button. Magically, all of the pieces flew up off the floor and reassembled themselves on the board. In less than a second, the full state for the board had been restored.

Everyone gasped and burst into applause.

"Woah." King Fredrick said.

Then, Marcus felt a tap on his shoulder. Behind him stood four hundred and ninety-nine other table judges. Each judge held their table's timing clock out toward Marcus and looked at him expectantly. As he took the clock from the nearest judge and started his spell again, Marcus suddenly regretted having felt the need to show off.

Const and Library Books

Const is a modifier in the C++ programming language that marks a variable as constant or un-modifiable. One of the primary uses of const is to simply have variables behave like constants. For example, this can be helpful in making complex equations readable. Another use of const is to prohibit a method from modifying data that is passed in by reference. This prevents intentional or unintentional side effects to that data.

Peter was frustrated. In his first seven months as an apprentice at the library of Alexandria he had never had a patron intentionally deface a scroll. Now it was happening almost every day.

Peter had noticed the first incident while re-shelving a scroll on building donkey-pulled carts. Half-way through the scroll one of the instructions was edited. The phrase "Secure with four nails." had been rewritten as "Secure with three nails (that is good enough)." How could someone do this? Peter knew that the perpetrator probably believed that they were being helpful and improving knowledge. But in reality, they were defacing the library's scrolls with their own opinions.

Peter decided to consult the master librarian.

"It is a sad day." agreed the librarian. "We need to find out who is doing this and ask them to stop."

"Ask them to stop?" cried Peter. "We need to do something more than just 'ask'. How about a lifetime ban from the library?"

The librarian shook his head sadly. "Perhaps." he agreed.

But after three more edited scrolls were found, Peter was too angry to wait. One night after work, he explained the problem to his friend Sarah. She had gone to high school with Peter and was now employed a few blocks over as a wizard's apprentice. She often grumbled dreadfully about the lack of interesting problems for apprentices in her field.

"Oh! Oh! I can help!" she claimed excitedly. She was visibly bouncing in her seat.

"How?" Peter asked suspiciously. He had had mixed luck with help from wizards in the past. In fact, he still remembered the incident that had left him without eyebrows for almost three months.

"I just learned the Const spell of immutability!" she proclaimed happily.

"Const spell of immutability?" asked Peter. This sounded like the type of spell that would end in disaster.

"Yes." answered Sarah. "The spell makes it so that you cannot edit written documents. It is usually used for things that you do not want changed, such as legal documents or poems."

"Poems?"

"Sure. Poets sometimes ask us to cast the const spell on their poems, so that they are forced to stop fiddling with their work. This one poet was stuck tweaking on the same line for 10 years before we finally made the work constant. It actually happens more than you would believe."

"Oh… interesting." was all that Peter could think to say.

"Can I use it on your scrolls? Please? I am so bored. I could really use the practice." pleaded Sarah.

Peter fought back images of the library accidentally being destroyed by a rogue spell. He quickly agreed before he could think better of it.

That night Sarah spent the entire night wandering around the library casting her spell on the scrolls. It was a slow process. Peter sat behind the desk watching nervously. Nothing burned down or exploded, so he considered the night a victory.

As Sarah was finishing, Peter realized that there was a question that he had never asked.

"What happens if someone tries to modify the scroll?" he asked.

"They can't." answered Sarah.

"I know, but what stops them? A voice in the back of their mind? A forcefield? A stabbing pain?"

"Forcefield." answered Sarah. She sounded tired. Then again, she had been casting the same spell over and over for hours.

The next day Peter sat behind the main counter of the library, trying hard not to fall asleep. Then, he heard a man at a nearby desk muttering something loudly. Peter peered over at the man. The man was trying to write something on the scroll, but his hand was stopped inches from the paper. The man looked confused as he struggled to move the pen closer. Finally, the man shouted something at the paper and stormed out of the library. Peter smiled to himself; Sarah's const spell had worked.

Functions and Sailing

Functions are self-contained blocks of code within a program. They have defined inputs and outputs, and they can be called from other parts of the code. Thus functions allow programmers to re-use a common block of code in different places within the program.

During her voyage to New Atlantis, Ann spent a good deal of time observing the ship's crew. After witnessing the ships' pointers coordinate the expansion of their convoy, she had become fascinated by all aspects of the ship’s operations. Ann spent hours watching as the sailors hoisted sails, tied off ropes, cleaned the decks, recorded headings, and checked the ocean depths. Driven by intense curiosity, Ann tried to learn as much as she could about each of these jobs.

One morning Ann asked the captain where she could learn more. Always eager to help, the captain disappeared into the ship's command cabin and returned with a 4,096 page Sailor's Manual (3rd edition). Ann was shocked.

"Why is it so large?" she asked.

"There is a lot to know," responded the captain with pride. "It takes the average sailor 5 years to learn the basics and another 35 to learn the rest of the manual."

"I see," Ann said. That seemed like a large cost to learn sailing. Then again, it probably took years to simply read through the manual itself. In Ann’s experience, operational manuals were rarely quick reads.

That night, Ann took the sailing manual out onto the deck. She opened to a random page and started reading. It was a section on how to tie the ship to the dock. The instructions occupied 3 full pages of tiny print. The level of detail was astounding. Each instruction spelled out every last aspect of the task. Ann read each line, trying to absorb the information. She even practiced the instructions for tying the ropes into knots (25 lines long) on her own shoe laces. After about half an hour, she felt that she actually had a pretty good understanding of the procedure.

The next section described how to tie a dingy to the side of the boat. Again, the section occupied 3 pages of tiny print. As Ann scanned the pages, she began to recognize instructions from the last section. In fact, the 25 lines about tying the rope were absolutely identical. She flipped back and forth rapidly between the two sections to confirm.

The next day, Ann approached the captain about this discovery.

"How observant!" he congratulated her. "Many of the concepts are very similar. For example, take ropes. There are only a few really good ways to tie knots."

"Why repeat the instructions line for line?" asked Ann.

"Because you need to do them each time. It would be horrible to skip the part about tying the knot. The dingy would drift off."

"I understand that. Why not just say something like: 'Tie the rope with a granny knot'. It would save you a lot of space -- 24 lines in this section alone. All that you need to do is to break out the common tasks into their own sets of instructions." suggested Ann.

"Wouldn't that make it much harder to understand the instructions?” asked the captain. “Right now, every step is laid out perfectly. I can hand any sailor the 35 pages about trimming the main sail without having to assume any prior knowledge."

"It would make it easier," argued Ann. "Once a sailor learns how to tie a specific knot, he or she could do it in any context. It would become a fundamental step itself… like a computer function."

"I guess it would make things shorter," agreed the captain. "But really, the length of the book is not a big problem. We also use the books for ballast, so having heavy books can be useful."

"It is better than that," argued Ann, ignoring the comment about ballast. "What if you find a better knot? Right now you have to change every single instruction that uses the current knot. It is probably a long and error prone process. If you are writing the same thing a hundred times, you will make a mistake one of those times. You probably have dozens of mistakes in here already.”

“What if you want to instruct a sailor to do something new, such as tie down a hot air ballon?” Ann continued. “Do you have instructions for that?"

"Well… no," admitted the captain.

"Wouldn't it be easier to say: 1) Grab the rope, and 2) Tie it to the port railing with a granny knot. Those are instructions you can even give verbally. The sailor only needs to know how to perform a few basic functions to start."

The captain fell silent and stared out into the sea. After a moment he nodded slowly.

"I think you are correct!" he declared loudly. After three days at sea with him, Ann had realized that the captain was a big fan of declaring things loudly.

Ann smiled.

"I bet it goes beyond simply tying ropes. The signals that we use to communicate can be broken off into functions too.” The captain trailed off as he slowly looked around the ship, assessing the resuse of different skills.

Suddenly, he spun back toward Ann. “Will you help me rewrite the book? We could break things up into these standalone units that you describe. It would revolutionize the entire sailing industry!"

Ann's smile faltered. While she could not resist an opportunity to improve the performance of the entire royal navy, she was still on her quest to save the kingdom. She weighed the options in her head. Finally, with much regret, she declined the offer. However, since she believed deeply in the value of the effort, she wrote a request to her father to send six of the kingdom's top computational thinkers to aid the effort. Satisfied that together they would be as helpful as herself, Ann let her mind wander to other questions.

Malloc, Free, and the Mall of New Athens

Malloc and Free are commands in the C programming language that are used for dynamic memory allocation. Malloc allocates a block memory of a given size (passed in as an argument) and returns a pointer to that memory. Free takes in a pointer to a block of memory and releases that memory. While this level of memory management is often hidden in many modern programming languages, understanding it can provide valuable insights into how computer memory works.

In ancient times, the mall of New Athens served eighteen different neighboring kingdoms with a combined population of millions. The mall itself was an engineering marvel. It was designed by the the famous architect Hans Lloyd Wright IV. It had the first known three story eatery and the third known use of stained-glass skylights. Visitors would gasp in awe at the sheer number of shops and miles of kiosks. A shopper could find any item they were looking for in at least six different stores.

Even the parking lot itself was hundreds of years more advanced than any other civilization. It introduced an entirely new approach to parking lots: dynamic, coordinated parking. The system was devised by two entrepreneurial brothers: M'Alloc and F'Ree. They had first conceived of the dynamic parking allocation system after spending seventeen hours searching for a parking space in Alexandria. Frustrated, they eventually drove their horses home, vowing to never let this happen in their own town.

The coordinated parking system itself was relatively simple. It was based on centralized coordination with the brothers. The two brothers sat in a small, but surprisingly comfortable, kiosk at the parking lot's only entrance and exit. One brother sat facing a window toward the entrance and the other sat facing the exit. Between them was a giant map of every parking space around the mall.

Upon entry, visitors would pull their horses, carts, double-carts, or long-cart-trains up to the entry attendant M'Alloc's window. M'Alloc would consult the master map, find them spaces in which to park, and hand them a small blue stone token. The token would list the starting slot number where they could park. Horses needed one slot, carts needed three slots and double carts needed five. If there was an appropriately-sized, open space for you to park, M'Alloc would know about it and direct you there. He would also mark off the appropriate spaces as occupied, so that he would not accidentally send someone else there.

Shoppers would keep their small blue tokens while they shopped. If they ever needed to go put bags in their car, they would consult the token and know where they had parked. But if a shopper lost their token, they were in trouble. With nearly two million parking slots it took a lot of walking to find your cart. It is said that, it took one unfortunate shopper two years of checking different slots in order to locate his cart after he had made the blunder of mistaking his parking token for a piece of hard candy.

And on the way out of the mall, shoppers would return their token to the exit attendant F'Ree. F'Ree would mark the corresponding slots on the master map as open. He would smile, wish you a good day, and help point you to the freeway.

It was a great system. However, like all great systems, it relied on a certain level of competency among the shoppers. If a shopper lost a token, they had to slog through the entire parking lot looking for their carts. And without a token F'Ree refused to cross that space off the master map, so it would be marked "occupied" forever. In fact, after five years of operation there were over a thousand "wasted" spaces due to lazy shoppers losing tokens. It was a sore subject with the brothers.

Despite the downsides, the parking lot was a monumental achievement. It handled millions of shoppers coming in and leaving every week. Not until the opening of the Manhattan Mega Mall, which itself encompassed the entire island of Manhattan, would another parking lot even start to compete with its scale or efficiency.

Packets, Supply Chains, and the Road to Alexandria

Packets are discrete units of data that are transmitted over certain types of communication networks. Packets can also contain metadata used to route, decode, and assemble the data. Large data payloads can be broken up and transmitted using multiple packets. The receiver can use the information in the packets to reassemble the full data on the other side.

Ann was traveling to the famed library of Alexandria. If any single location in the known lands held information about the coming darkness, it would be the library of Alexandria. Ann had heard the library described in a whispered reverent tone since she was a little girl. It was rumored to have almost 100,000 scrolls!

As she approached the great Mississoppoly river, she saw something that surprised her. The road traveled straight to the river's edge and stopped. There was no bridge. Ann saw a cluster of people and carts standing near the river's edge.

"Where is the bridge?" she asked.

An old man gave her careful look. "There is no bridge." he finally answered.

"But, how can I get across?" Ann inquired. The very core of her mission was threatened if she were trapped on the western side of the Mississoppoly.

"Ferries." responded the man.

"Fairies?" inquired Ann, scanning the air around her to see if there were any flying nearby. Ann loved fairies. They were such wonderful magical creatures. She had once met the Fairy King in the royal palace when he had come to visit her dad.

"Yep." said the man.

"But, I don't see any." responded Ann. At the same time, she was struggling to figure out how a fairy could help her cross the river. They could not exactly care very much. And, despite the stories, fairy dust was nothing more than sparkly dust that was almost impossible to get out of your clothes.

The man pointed out across the river at a few small boats slowly making their way across the river. A few were heading toward the opposite shore and a few were coming toward Ann.

"Oh. Ferries. I see." Ann was disappointed.

"It'll be 'bout a 2 hour wait." the man advised.

Ann nodded an acknowledgement and dismounted her horse. She led the horse over to a shady patch with long grass. While the horse chewed at the grass, Ann sat and watched the boats come in. The first boat to arrive held 8 crates of supplies. Two soldiers unloaded the boat, placing the crates on a a half empty train of carts nearby. As soon as they had finished, they returned to waiting against the last cart. Twenty minutes later, another boat arrived with 4 more crates of supplies and a third soldier. Together, the three soldiers moved the crates onto a cart. Ann was intrigued.

"Excuse me." she called. "What are you doing?"

The soldiers looked confused. "Shipping supplies." one of them answered as though it was the most obvious thing in the world.

"Yes. I understand that." agreed Ann. "But, why do you send them over different boats? Why not just ride one boat over?"

"Too much stuff." called the old man from behind her. "You can't fit all that on the boat."

"Then why not use bigger boats?" asked Ann.

"Ah. Right. Why did I never think of that?" laughed the old man, who Ann now realized was the ferry master. "Just use bigger boats."

Suddenly, his face got serious. "You know what big boats cost to run? Or how long they take to load and unload? I could end up holding up a tiny shipment for days while I am loading a bigger boat. And how big a boat should I get? No matter how big a boat I pick, someone will always have a bigger shipment to get across. No, no, no. Better to use packets."

"Packets?" asked Ann.

"Yes. That's the name of these here smaller boats. Sure, we have to split up some shipments to get them across, but it is a tradeoff. Sometimes we have a lot of little trips to make and the boats have some empty space. And sometimes we have bigger loads. But as long as we can break the loads up and put them on packets, I can get them across. It just means that someone has to wait at the other side for all the packets to arrive and then reassemble their shipment. "

"But what if you have a HUGE supply train?" asked Ann.

"Then I send a lot of packets across, don't I?"

"I guess so." agreed Ann. There was a simplicity to the system. "But doesn't a large shipment slow everything down?"

"The nice part about using many small boats is I can do multiple shipments in parallel. If I am shipping a hundred packets worth of wheat across the river and someone comes on their way to the hospital, I can send them off in parallel. That is one of the beautiful things about using a lot of small boats. I do not need to finish loading one huge boat before starting the next. I can have multiple streams of shipments going on at once. Of course, there is some per-boat overhead; you need to get it into the dock in the first place. So, really tiny boats would be too much coordination."

Ann had to admit that the system did sound flexible. She remembered hearing that her brother had to wait for three days before his first ocean voyage, because it took that long to load the boat. She could not imagine such delays being feasible for a river crossing.

"And they just go back and forth all day?" she confirmed.

"Mostly. Although there is a little more to it than just the cargo and the boat. The captains can get instructions to travel upstream or downstream a bit - to different landings, you know. There are four on this side and three on the other. This particular landing gets most of the traffic, because of the road."

"Are there any south of here? Closer to Alexandria?" inquired Ann.

"Sure. I can send a packet to the landing at Gretock. It is a nice, little, basket-weaving village. Might save you a few hours if you are on your way to Alexandria. It will still be about a two hour wait though."

Ann was thrilled. She continued to watch the small boats flow in-to and out-of the landing for the next two hours. Then, when her turn arrived, she happily boarded one of the boats and continued on her journey.

Stacks, Queues, Priority Queues, and the Prince's Complaint Line

Stacks and queues are very simple, yet fundamental, data structures in computer science. Simply put: they store data. You put a piece of data in the stack or queue, go about your business and later take that piece of data out. Where they differ is in how they order the data that is extracted. Stacks are last-in, first-out data structures that return the most recent data inserted. Queues are first-in, first-out data structures that return the least recent data inserted. And priority queues return the highest priority data inserted (accord to some priority value). Understanding these ordering effects is the key insight into understanding how these data structures can effectively be used.

Before he became king, Prince Fredrick had a tradition of hearing his future subjects' complaints every Tuesday in the great room. At 10 am the doors would open, and his loyal subjects would fill the room to raise their complaints. On days that he was feeling particularly generous, Prince Fredrick would even task his steward with addressing some of the complaints. However, on most days Fredrick felt that he had done his part by just listening and he would promptly forget everything that was said.

By 6 am every Tuesday a great crowd formed outside the doors to the Hall of Complaints. In fact, farmers with particularly pressing concerns camped out for days or weeks hoping to be near the front of the crowd and thus be selected to discuss their complaint. The fact that their complaint would likely be ignored did not dampen their resolve. They needed to be heard.

Fredrick never gave much thought to what happened before the doors opened. After all, he was the prince. Why should he care about what happened outside of his room?

Then, Rok the Dragon arrived. In early June the dragon started burning crop fields and eating the livestock -- typical dragon activities. However, Fredrick continued to use his system, selecting the subjects from the front of the room.

In late July, Fredrick finally selected a farmer who was there to talk about the dragon. "What is your complaint?" asked Fredrick.

"A dragon ate my farm." the farmer replied.

"A dragon?" Fredrick screamed. "We must act now before it destroys a second farm!"

Silence followed Prince Fredrick's proclamation.

"What is it?"

Fredrick

asked, but nobody responded. Fredrick singled out another farmer and directed the question at him.

"It is just... Well... The dragon has destroyed over twenty farms since it arrived here in June. My farm was actually destroyed six weeks ago."

"Then why am I only hearing about it now?" screamed the prince.

"Noble sir, I have been lining up for six weeks to discuss the dragon. It is only today that you gave me an audience." answered the second farmer.

"How many others are here to talk about the dragon?" inquired the prince. Half the people in the room raised their hands. The prince screamed at everyone in general. Eventually he calmed down enough to send his best knights to run the dragon out of town.

"This will never happen again." the prince vowed. "From hence forth there will be a SYSTEM. Each person will write down their complaint and put it on top of a complaint stack. Each Tuesday from 10 am to 11 am I will take the top complaints off the stack and read them. This way I will always hear the most recent complaints."

Everyone in the room looked at each other. They gave a half-hearted cheer. "Yay."

For the next few months life returned to normal and the Royal Complaint Stack worked about as well as the unorganized mob of people in the complaint room. Then Rok returned. On Wednesday he ate one farm and took a week-long nap.

On the following Tuesday the prince read through the first ten complaints on the stack. All ten were about the refereeing at last Sunday's sporting event. The blue team had lost and its fans were unhappy. The prince had an easy solution and told the steward to bet against the blue team next week. Feeling like he had fulfilled his duty to the people, the prince decided to quit early and play some golf.

The prince found Rok sleeping on the golf course. The prince screamed when he saw the dragon. "What is it doing here? Why was I not told?" He threw his golf clubs at his caddy in frustration and stormed back to the castle.

He was still fuming when he got back to the castle. "I should have been told. Why did no one complain?"

"Your honor" started the steward very carefully. Fredrick picked up on his tone immediately.

"Where is the complaint stack?" he demanded. The steward brought in the stack of complaint papers. The prince started to leaf through them. The top eight were something about food poisoning from today's special at some local restaurant. Under those were more complaints about refereeing. Then he found it. Complaint number thirty one on the stack was about the dragon.

"Curses!" he yelled at the stack of papers.

"No more complaining about minor things when there are important problems!" the prince declared.

The steward sighed. "Sir, how will we tell? The people want to be able to complain about what is bothering them."

"Then there shall be a NEW SYSTEM." Everyone groaned quietly.

The prince retired to his study and began working on the new system. It had to let people voice their frustrations. It had to allow the prince to find the most important issues. More importantly, it could not take too much of his time; he really hated dealing with complaints. He spent three weeks in isolation working on his system.

The following Monday, he addressed his subjects. "I have devised a new system: a priority queue. Each of you shall write your complaints on a piece of paper. Every Monday night, the steward shall read each complaint and assign a priority from 0 to 10. We shall then deal with the highest priority complaints first." The prince paused and waited for the applause. A few subjects clapped lack-lusterly. The steward audibly groaned at his new task. He knew quite well that everyone was going to complain to him about the assigned priorities.

And so the kingdom adopted a priority based complaint system. Over time, the subjects embraced this system. The prince went on to become king and guide his kingdom through a period of unprecedented happiness and quick responses to dragons. Everyone in the kingdom was happy... except of course the steward.

Arrays, Linked Lists, and Zed's Coffee Shop

Arrays and linked lists are simple data structures that store multiple values in memory. Where these data structures differ is in how they store and allow access to the data. Arrays are like a set of bins with a fixed number of slots. Their structure makes it easy to read from or write to an arbitrary element in the array. In contrast, linked lists are easily extensible chains of data. However, you must scan to the correct location in the chain to read or modify a piece of data in that node.

One year after Zed opened his coffee shop, business was great. Zed had a devoted set of regulars who bought coffee every morning on their way to the castle. They were mostly bureaucrats, specializing in such jobs as counting the kingdom's cattle or copying maps. They loved their coffee.

Then, one day, a competitor opened shop across the street. Zed started losing business to MegaCup’s low prices and flashy signs. Zed knew he had to expand.

Looking over the books, Zed noticed that he sold a lot of coffee in the morning but almost none at night. None of his customers wanted to be jittery as they headed home and went to sleep. Zed needed a new product -- something he could sell at night.

His supplier told him about a new type of coffee coming from the southern region of the kingdom: “Low Jitter Coffee”. Immediately, Zed knew this coffee would solve his evening sales slump. He ordered eight cases.

Zed needed a way to market his new coffee. The sign outside his store read “Coffee” and did not have room for anything else. After a week of intense thought, Zed ordered a new ArrayDesignBoard menu board for outside his shop. The board had four slots where you could slide in menu items to display. He slid in “Coffee” and “Low Jitter Coffee” tags.

The new coffee was a huge success. Zed's business doubled in a week. He added four baristas to the evening shift.

However, Zed’s competition soon caught on. A week later, Zed noticed a new shingle on MegaCup’s sign: “Low Jitter Coffee”. The war was on.

Then his supplier told him about another type of coffee. It was called “Double Bold Coffee”, and it was significantly stronger than the normal brew. A single cup could keep you awake all night. Zed ordered eight cases and a the new menu tag for the ArrayDesignBoard menu.

The coffee was a huge success. His morning crowd loved it. He also started attracting new customers from the castle’s night guards. They needed something strong to keep them awake during their watch.

Alas, it was not long before MegaCup added a new shingle to the end their sign.

The next time his supplier visited, Zed grilled him on the other types of coffee available. After obsessing over the supply lists, Zed decided to try a novel approach. He order one case each of ten different flavors. He put these flavors into a rotation, constantly offering new variety. This approach worked particularly well with Zed’s sign. Every time he switched a flavor, he would remove one tag and slide a new one in. Sometimes he changed the menu a few times in one day, such as replacing “Double Bold” with “Low Jitter” after noon.

MegaCup took a different approach. The manager quickly found that, while adding new shingles to the end of the list was easy, removing them was frustrating. In order to remove a shingle, he had to: unlink it from both the shingles above and below, then reattach the shingle below to the one above. It was a time consuming process. He decided to take advantage of the ability to easily expand offerings. He offered six different coffees on a semi-permanent basis. On rare occasions, he would grudgingly spend fifteen minutes to unlink a shingle on his sign and add a new one.

The two coffee shops operated in that mode for years. Zed’s coffee shop rotated through different options, and MegaCup offered a more constant, but larger, selection.

Both businesses thrived as the market for coffee grew. Eventually, Zed's Coffee House became one of the largest businesses in the kingdom with over a hundred different locations. Zed continued to expand aggressively until the great sugar famine hit. With business dropping due to the lack of sugar, Zed decided to leave the world of coffee and speculate in coconut sales.

----------------

Interested in learning more about linked lists? See why choose your own adventure stories should never be linked lists. Or, read about Ann's ocean voyage and her insights into linked lists.

Bullies, Bubble Sort, and Soccer Tickets

Bubble sort is a simple sorting algorithm. The algorithm repeatedly passes through an array, swapping adjacent elements that are out of order. As a result, larger elements "bubble" up to the end of the array, while smaller numbers "sink" down. This process continues until the array is sorted. Like insertion sort, bubble sort's worst case performance is O(N^2).

Peter had been in line for two hours when he felt the tap on his shoulder. He felt a pang of fear as he looked behind him. Terrible Todd glared angrily back. Then again, Terrible Todd always looked angry to Peter.

Terrible Todd was best known for his recent performance at the annual Alexandria area rock throwing contest. He was the first candle maker's apprentice to win the main event. His winning throw used a two hundred pound rock and the reverberation could be felt two miles away. Unofficially, he was also known for being a mean bully.

"Hi Todd." Peter meekly greeted him.

Todd grunted back and motioned Peter out of the way. Peter held firm. He refused to give up his place in line. Season ticket sales for the East Alexandria soccer team started in an hour. This year Peter was determined to get premium season tickets. He had his heart set on midfield.

"I am sorry, Todd. I was here first." Peter explained.

Todd looked Peter up and down. Then, with a louder grunt, Todd picked up Peter, turned, and set him down behind himself.

"Hey!" Peter cried, but Todd was already tapping the shoulder of the next person in line.

Peter fumed. This was not fair. Why should Todd get to go in front simply because he was larger? There were principles to these things.

As Peter ranted silently in his own head, he watched Todd slowly work his way up the line. One person at a time, Todd swapped places with smaller people. Todd’s advance was only halted when he reached Wren, the muscular blacksmith.

Then Peter felt another tap on his shoulder. Turning, he saw Big Jim. With a sigh, Peter stepped to the side and let Jim go ahead. Like Todd, Big Jim worked his way forward through the line. To Peter's pleasure Jim even moved in front of Todd to take the spot behind Wren.

Now Tiny Mike stood behind Peter. Peter tried to glare at Tiny Mike, making it clear that Mike was not moving ahead. Mike did not even try.

This process continued for the next hour. Every time a larger person found themselves waiting behind a smaller person, there was a polite tap on the shoulder and a switching of positions. Each time Peter moved back in the line he felt a little more demoralized. He was not a big person, and thus he found himself unable to swap with anyone. By the end of the hour the entire line was sorted by size, and Peter was near the back. Discouraged, Peter left the line and returned to the library.

As Peter sulked behind the library's counter, he remembered that now tickets were also available by pigeon message. He hurriedly filled out the form, requesting "Best Available". The pigeon flapped away, carrying Peter's only hope for reasonable seats. Ten minutes later, the pigeon returned with a confirmation of second-row, mid-field. Peter was thrilled. He must have gotten his tickets before even Big Jim.

That day Peter learned two important lessons. First, bubble sort is great for bullies. Second, standing in line was not worth it in the age of near-instantaneous pigeon-based ordering.

-----------------------

Read more about sorting algorithms with Merge Sort and Lines of Kindergarteners, Why Tailors Use Insertion Sort, or Sorting During the Flu Outbreak.