Bog Dragons Do Not Support Multithreading

Multithreading is a technique in modern computer architectures to process multiple sets of instructions on a single CPU core. Different sets of instructions run in different threads, and the operating system switches between these threads. Unlike multi-core or multi-processer systems, multithreaded systems are not actually running these sets of instructions in parallel (at the exact same time). Instead, a single CPU core is rapidly switching between the threads to allow each to make progress.

The ability to multithread instructions allows modern computers to effectively do work "in the background". For example, the spell check operation in a word processor might run in a separate thread, allowing the user to continue to work as the full document is being spell checked. In the absence of multithreading, computationally expensive operations can cause the entire computer to "freeze" as the CPU is stuck on one task.

Ferr dove low as another bog lizard snapped at her from a nearby tree branch. She hated traveling through the bog. It was filled with nasty creatures, and it always smelled like… a bog. At least there was only a few miles left to go. She would be home in time for dinner. For a brief moment, Ferr let her mind drift and wondered what dinner would be.

Then, Ferr heard a loud screech. The sound sent a chill through her. It was a bog dragon, and it sounded hungry.

Bog dragons are particularly vicious creatures, especially with respect to fairies. In fact, fairies seemed to be either their sworn enemies or their favorite snacks. Nobody was really sure which it was. Regardless of the dragon's motivation, Ferr knew that she was in grave danger. She took off flying as fast as she could.

Ferr dodged trees as she flew through the swamp. Unfortunately, bog dragons are much smaller than regular dragons, being about the size of a house cat, and thus are able to maneuver quickly in the dense swamp. Ferr knew that she had little chance of winning this race. The bog dragon was both fast and familiar with the swamp. It was only a matter of time before it caught up to her.

Her mind raced, trying to find anything that would save her. She mentally ran through the list of all of her spells. Nothing seemed promising. She cursed herself for having not perfected any defense spells against a bog dragon. Bog dragon sightings were rare enough that she had never made it a priority. Now, that seemed like a mistake.

She could hear the bog dragon breathing behind her.

Distracted by the sound and her own thoughts, Ferr clipped a tree. Her left wing missed a beat, and she was thrown off balance. She spun through the air, trying to regain control. But, it was no use. She had been flying too fast. She barreled into the soft mud with a loud squish, sliding fifteen feet. She was coated from head to toe in brown bog mud.

Above her, the bog dragon circled eagerly.

As she scolded herself for not paying more attention, a memory popped into her head. Bog dragons were not multithreaded. They could not multitask. They could only ever do one thing at a time! No matter what it was, that one thing would occupy their full attention. Right now, the dragon was doing one thing: hunting her. But, if she could distract it with some other task, it would not be able to context switch. She could escape.

Ferr ran through the list of spells again in her mind. Finally, she hit upon the perfect solution: the spell of Mental Flash Cards.

Ferr had used this spell on herself to prepare for her finals last year. When cast, it ran through five minutes of simple math flashcards in the back of the target's mind. Ferr would use this to practice math while flying to school. Since the math was simple, she could balance the two tasks. She would quickly solve each flash card and then concentrate on flying: one card, one beat of her wings, one card, one beat of her wings, and so forth. As long as she switched between the tasks, she could do both safely. But, the bog dragon could not.

Hoping that she was remembering this characteristic of the bog dragon correctly, Ferr cast the spell. If she was mistaken, and the bog dragon could multitask, then giving it math flash cards would probably just anger it. It would be like having someone rudely scream "WHAT IS 1 + 3?" in your ear every few minutes. Nobody enjoyed that.

Three seconds later, the bog dragon flew directly into a tree. It fell to the ground with a squishy thud.

The spell had worked. The bog dragon was fully occupied with the flash cards. It was unable to switch between the flash cards and flying.

Ferr did not waste any time. She was up and flying immediately. The five minutes would give her enough time to escape.

Ferr looked back once. The bog dragon was lying on the ground looking miserable. Ferr could not feel too bad. After all, she would have been the dragon's lunch. And even though the dragon had lost its lunch, at least it would learn some simple math in exchange.

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.

Hunting Dragons with Binary Search

Binary search is an algorithm for efficiently finding a target value within a sorted list. The algorithm maintains a shrinking search window. It narrows down that window by repeatedly ruling out half of the remaining search space.

At each step, the algorithm checks the middle item in the current window and compares it with the target value. If the value in the middle is less than the target, you can rule out the lower half of the window. If the value is greater than the target, you can rule out the upper half. This process repeats until the target item is found or the window shrinks to a single (non-matching) item.

The morning's news was nothing short of dismal. King Fredrick had only been awake for twenty minutes when he decided that today was going to be awful. It had started manageably enough, with his head butler informing him that his favorite crown was still being polished and was not available. However, that news was quickly followed by his chief knight, Sir Braver, informing King Fredrick that a dragon was now terrorizing his kingdom.

"Tell me what happened," commanded the king in a weary tone. He hated dragons.

"There is a dragon," declared Sir Braver.

"You have already told me that part. Now tell me what has happened. Has anyone seen this dragon? Has it attacked anyone?" prompted the king.

“Yes, sir. We have received six confirmed sightings. Farmer McDonald has lost his prize cow."

"The one that won last year’s competition?" inquired the king. If he recalled correctly, it was a sizable cow and would be a perfect target for the dragon.

"Yes, sir," answered the knight.

The king sighed. The story sounded like a textbook dragon attack. Soon the dragon would eat half the cows in the kingdom. "Well, you had better take the dragon hunter and get rid of the dragon."

"But sir, no one knows where the dragon is. How shall we hunt it?" asked the knight.

"Really?" the king asked, surprised that his head knight did not know how to hunt a dragon.

Sir Braver remained silent.

"Find the last farm that it attacked,” said the king. "Dragons take long naps after each meal, so you have time to catch it there.”

"But sir, how will we know where that is?" asked the knight.

"Have you studied dragon attacks at all?" the king asked. "There is an order to these attacks. Dragons are smart. They eat the biggest cow in the area, then the second biggest, then the third, and so forth. They keep eating smaller and smaller cows, until the only remaining cows are too small to be worth the bother. Then the dragon goes on to the next kingdom."

"But sir…" started the knight.

"Use the rankings from last year's cow competition!" cried the king, losing his patience. "They have a sorted list of the largest cows!"

"Ah. Of course, sir. We shall work down the list until we find the dragon!" confirmed the knight.

The king nodded, relieved that the knight was finally thinking on his own. Sir Braver and the dragon hunter would visit the each of the farms on the list, in order, and find the dragon. Even as he tried to comfort himself with this thought, warning bells went off in the king's head.

"Not down the list," the king admonished. "Do you know anything about searching?"

The knight looked confused. He had been certain that he was on the correct track. "But sir, I don't understand" he said.

"How long does it take you to travel between farms?" asked the king.

"A few hours, sir."

"How many farms are on the list?"

"Maybe a hundred."

"That means that it could take you hundreds of hours. By that time, the dragon will have eaten more cows. It might even be gone by then."

"But, sir…"

"Use binary search," commanded the king.

"Binary search, sir?" asked Sir Braver, regretting having fallen asleep in his 'Algorithms for Knights' class.

"Start in the middle of the list and check whether the cow is still there. If it is still there: rip the list in half, throw away the bottom half, and repeat the process on the top half of the list. If the cow is gone: rip the list in half, throw away the top half, and repeat the process on the bottom half of the list. Each time you visit a farm, rip the list in half and concentrate your search on only one of the two halves."

"But sir, that sounds complex," protested Sir Braver.

“It is not," argued the king. "It is simple. If the cow in the middle of the list is still at the farm, then so are all the cows below it on the list. That is how dragons eat. It is not going to eat a smaller cow first. That would be absurd.

“On the other hand, if the cow is missing, then so are all the cows above it on the list. Dragons do not skip around lists randomly. There is an order to these things."

“What if the dragon moves while we are searching?” asked the knight.

Finally, a reasonable question. “Your search effectively tracks two bounds: the smallest cow that you know has been eaten and the largest cow that you know has not been eaten. If you get to a point where those bounds are next to each other on the list, and you do not see a dragon, then proceed to the largest uneaten cow and wait there.”

"But sir, how is that any faster than just scanning down the list?" asked the knight.

The king sighed, again. His confidence in the knight’s ability to handle this task was eroding rapidly. "If the dragon has attacked 45 farms, how long will it take you to scan those farms? 90 hours? But in the case of binary search: after the first farm you will have ruled out 50 farms on the list -- one way or another. After the second farm, you will have ruled out another 25. Each time, you are cutting the problem in half. In fact, you can find the dragon after checking only 7 farms."

The knight nodded, yet looked unconvinced. "But sir, are you sure?"

The king screamed. "Of course I am sure! I am the king! And, further, every idiot knows that binary search is a logarithmic time algorithm while scanning down a list is a linear time algorithm. NOW GO AND GET THAT DRAGON!"

For the first time in his long career as a knight, Sir Braver ran away. He told himself that he was running in order to carry out the king's orders as quickly as possible. But in truth, the king looked really mad.

As he watched his top knight clank noisily down the hall, the king decided that it was indeed time to go back to bed.

For more on binary search also see Binary Searching for Cinderella.