The Tortoise, the Hare, and 50000 Ants

A parallel algorithm breaks a large piece of work into smaller units and solves those units at the same time. The algorithm does this by distributing the work over multiple CPUs or cores within a CPU.

"I want a rematch," screamed the hare.

"Not today," answered the turtle, "I am still tired from our race. It would not be fair."

"But… I should have won," argued the hare. "I want a rematch."

"I will race you," said a tiny voice. The hare looked around, but could not find the speaker.

"Down here," added the voice. The hare looked down and found an ant staring back at him.

"You?" the hare asked suspiciously. "You are just an ant."

"Yes," answered the ant. "I am an ant, and I would like to race you. If the turtle can win, I believe that I can too."

The hare scoffed.

"Okay," replied the hare. "I will race you. Let's make it 5,000 meters. Can you even walk that far?"

The ant thought for a moment. "That is a long way for someone as small as me. I am not sure that my legs could make it. Perhaps I could split the work with my family members. We could each race part of the way."

"Of course," replied the hare, "I am not afraid of a thousand ants."

The turtle looked at the hare in surprise. Surely, the hare had learned the price of arrogance already.

"But 5,000 meters will still take us a very long time," continued the ant. "We will be running for days. The crowd will want to see everyone finish. Perhaps my family could each run their leg of the race at the same time."

"Yes," answered the hare. "That way I will not have to wait for days to see the look on your faces when you lose."

The turtle's jaw dropped. "Really?" he asked.

The hare did not respond. He busied himself with a short warm-up jog.

Meanwhile, the ant scurried off to fetch his family. A total of 50,000 ants agreed to each run a 10 centimeter leg of the race. They lined up carefully at the start.

The turtle shuffled down the track 10 centimeters and drew a finish line with a stick. "The race is over when the hare finishes one lap and crosses the original finish line OR the last of the ants crosses this finish line. Either way a total of 5,000 meters will be run."

The turtle looked at the hare and waited for this to sink in. The hare continued stretching his legs -- there would be no rests during this race.

"On your mark," announced the turtle.

"Get set."

The hare and 50,000 ants tensed.

"Go."

The hare speed away from the line, kicking little tufts of dirt behind him as he ran. In contrast, the 50,000 ants poked along. Each pebble was a formidable obstacle, and their finish line loomed in the distance. The slowest ant, Geoffrey, lagged nearly an inch behind the leader.

Still, the ants were finished in under a minute.

As the hare rounded the final bend, he could barely hear the chorus of ant cheers. The spectators were gathered around the ant's finish line. It looked as though the race was already done.

Then, the hare realized what had happened.

--------

For other familiar tales, see Binary Searching for Cinderella or Goldilocks and the Boolean Bears.

Or see a full list of stories here.

Goldilocks and the Two Boolean Bears

Boolean logic is based on two values: TRUE and FALSE. Boolean values are used within programs to perform logic such as: determining if an IF statement executes or controlling when a loop terminates.

Once upon a time, a girl named Goldilocks came across a small cottage. She had been wandering around the woods all day and was eager to rest. She furtively peeped into the windows and listened at the door. There was no sign of life. Convinced that the cottage was empty, Goldilocks climbed in through an open window.

The smell of fresh porridge wafted through house. Goldilocks followed her nose as if in a trance. Presently, she came to the kitchen and saw two large bowls of porridge sitting on a low wooden table.

"Nobody will mind if I have just a little," thought Goldilocks. Her stomach grumbled in agreement. The smell of freshly ground cinnamon pushed away the last of her doubts.

Goldilocks skipped over to the table and tried the first bowl of porridge. It was ice cold. "This porridge is completely cold," she thought to herself. "It is not hot at all."

She tried the next bowl of porridge.

"Argh!" she screamed. The molten porridge seared the inside of her mouth. She spit the porridge across the room, eager to distance herself from the fiery pain. She then dove for the bowl of cold porridge, filled her mouth with the icy sludge, and waited for the pain to subside.

"Who makes porridge that hot?" she moaned to no one in particular.

Traumatized, she looked for someplace to rest. In the living room, she found a single small chair.

"Only one chair?" Goldilocks wondered aloud. Then, noticing the well worn patch of carpet adjacent to the chair, she concluded: "I guess one person sits and the other does not sit. That seems awkward."

Goldilocks climbed into the chair, which promptly collapsed onto the floor. After quick examination of the wreckage, Goldilocks mumbled to herself in confusion "Who makes a chair out of balsa wood? No wonder the other person did not sit down. You would have to be tiny for that chair to support you."

Continuing her search for a place to rest, Goldilocks ventured upstairs. The large bedroom held two beds. The first bed looked incredibly soft. Cotton balls filled the four foot thick mattress. In stark contrast, the second bed consisted of a flat plank of iron supported by four cinder blocks.

"What is going on?" asked Goldilocks. "One bed is clearly comfortable. The other is not. Who makes a bed out of an iron plank?"

Golidlocks debated crawling into comfortable bed when the truth dawned on her. Everything in this house was Boolean. The porridge was hot or NOT hot. One person sat in a chair and the other did NOT sit. One bed was comfortable and the other was NOT comfortable. Whoever lived in this house did not believe in a middle ground. That did not bode well for visitors.

Goldilocks dove out an open window. She sprinted down the path and away from the house before the owners returned. She had no interest in learning whether they were welcoming or not.

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

For more about Boolean logic, see Ann's visit to the city of Bool.

For another take on familiar tale, see Binary Searching for Cinderella.

Binary Searching for Cinderella

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.

Alfred Charming could not understand his cousin, Prince Charming. For the last sixteen hours, the prince had babbled continuously about his magical, life-changing night at the ball. The prince had met the girl of his dreams, and she was perfect. Yet, the night had ended with that very same girl running from the party and diving into an oversized pumpkin on wheels. Alfred was certain that was a bad sign. It ranked somewhere between a fake headache and an actual slap to the face. Despite this setback, his cousin was still obsessed with finding this mystery girl. The prince desperately clung to her glass slipper, determined that it would lead him back to her.

Of course, Alfred could excuse his cousin's romantic notions. He had witnessed first-hand the disaster of last month's ball. He had been there to comfort the prince through the tears that had followed. His cousin was under tremendous pressure to marry, but finding his princess had been far from smooth. For now, at least, the prince could bask in the delusional glow of a magical night of dancing and small talk with a mysterious party goer.

However, Alfred could NOT excuse his cousin's flawed strategies for finding the woman of his dreams.

"I shall go forth to every house and find the owner of the slipper," proclaimed Prince Charming.

"Are you crazy?" objected Alfred. "That would take weeks. And you have to help them try on a slipper made of glass. Think of the germs. It is a health nightmare."

"I must find my true love," protested the prince.

"Fine," said Alfred. "I am still not sure why, but let's say that you do need to find this girl. You don't have to go to every house."

"I must be thorough," said the prince.

"You can still be thorough using a good algorithm," argued Alfred. "Trade data for time."

"Data? Time?" asked the prince.

Alfred thought for a moment. "Ye Old Foot Shoppe has a list of everyone in the kingdom's shoe size. Have them compute the size of the glass slipper, and you can look for a match on their list. They keep sizes with two decimal points of precision, so there will only be a few matches at most. I bet the slipper is around a size 5.75. And, if you do happen to find a few matches, you can go try them all."

The prince did not look convinced. "Spend the day searching for numbers in a list? How is that romantic? It sounds like hours of dreadful effort."

"The store's list is already sorted," explained Alfred. "You can use binary search to find a match. It is better than days of trying to fit the same glass slipper on different feet."

"Binary search?" The prince's education had not required an algorithms class.

"The search algorithm," said Alfred.

The prince continued to stare blankly back at Alfred.

"You can do it using your fingers," explained Alfred. "Use two fingers to track where in the list the slipper's owner could be. One finger indicates the start of the range, and one finger indicates the end of the range. Let's keep it simple and call them the 'start' and 'end' fingers respectively. If you do the search correctly, the matching shoe size is always somewhere between (or possibly under) your fingers."

"Initially, the entire list is under consideration," continued Alfred. "So start with your 'start' finger at the beginning of the list, and your 'end' finger at the end."

"Then I use my fingers to scan through the whole list?" interrupted the prince. "What do I do? Move one finger up then the other down? Sounds dreadful. I might get a paper cut!"

"No," answered Alfred. "Then you do binary search. First, you look at the list entry halfway between your fingers. Call that the 'middle' entry, because it will be in the middle. Second, you can compare the middle value to the one from the shoe. And third, you move one of your fingers depending on the value of the middle entry.

"There are only three cases to consider:

1) If the glass slipper is smaller than the middle value, you only have to work on the 'smaller' half of the list. Move the 'end' finger to where the middle value is, because all of the entries after the middle are too large to match. The matching size will still be between your two fingers.

2) If the glass slipper is larger than the middle value, you only have to work on the 'larger' half of the list. Move the 'start' finger to where the middle value is, because all of the entries before the middle are too small to match. Again, the matching size will still be between your two fingers.

3) If the middle value matches the slipper's size, you are done. You found a match. Yay."

"Your method only eliminates half the list," objected the prince.

"You repeat the process on the remaining half of the list," sighed Alfred. "Pick the entry halfway between your two fingers and call that the new 'middle'. Compare the middle value to the shoe size and use the same logic to eliminate half the list. After each step, you cut the size of the list in half, and still guarantee that the target value is between your fingers."

"When do I stop?" asked the prince. "When do I find my princess?"

"You stop when you find a match," answered Alfred. "Unless, of course, there is no match. If you reach a point where there is nothing left to search, then the list does not contain a match."

"How will I know that there is nothing left to search?" asked the prince.

"There is nothing left to search when there are no new values between your fingers. This can happen if both fingers point to the same place or if they are right next to each other. As I like to say: 'If your fingers touch, you are out of luck'."

"That does not rhyme. It would sound better if it rhymed," observed the prince. "More importantly, what if my princess's name gets skipped? Your algorithm involves big jumps early on. I am not sure that I could survive losing her."

"It won't skip her," answered Alfred. "At each step we guarantee that if there is a match, it is between your fingers. However, it is true that binary search will only give you ONE match and it might not be the first one. If you want all the matches, which you do, you will need to check the list entries near the match. Scan outward from the match."

The prince nodded solemnly. "I am sure that there will only be one match. My princess is perfectly unique."

Alfred stifled back a thousand comments and smiled politely.

After a moment, the prince continued. "While your idea has merit, I believe that I shall stick to my original plan. I shall go forth to every house and test the slipper."

"Why?" asked Alfred. "What if someone is not home? What if your mystery girl is locked in a basement by evil family members? What if someone breaks the slipper? That plan has so many problems."

The prince smiled. "I want the people to know that I am searching for my true love. If I use your binary search, I miss the excitement of the search. Binary search is not romantic."

Alfred sighed. He did not have an argument to counter that.

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

For more about binary search, see Hunting Dragons with Binary Search.

Also see my recent note on why updates will be less frequent for a while.

Coming Soon (or Maybe Later)

If you follow this blog, you might have noticed that the frequency of new stories has dropped off significantly in the past few weeks. Do not worry. I am not out of ideas.

I have been working on assembling an initial collection of stories for publication For the most part, I have been spending time editing and reworking previous stories. I have also been working on filling in some gaps.

What to expect from the collection:

• A few new stories - Covering some earlier concepts and filling in the gaps.
• More details of Ann's quest.
• A reasonable ordering (both by concept and plot)
• Extensive editing - At least 10% fewer gramatical errors!

I am planning on continuing adding new stories here, but with a slightly lower frequency than before. I am also cleaning up and even rewriting stories as I go. Admittedly, a lot of the stories are still in very rough form and could use a round or two of reworking.

In the mean time, feel free to check out the current set of stories (around 70): By Topic or By Level.

Or to learn more about this blog, its goals, etc. at the FAQ.

Names for Ingredients (and Variables)

The use of clear variable names can help make code more readable and reduce the likelihood of mistakes.

"Excuse me. I am looking for powdered rose petals." said Marcus.

"On the shelf behind you." replied the young clerk without looking up. He continued to sit behind the counter, copying text onto a sheet of parchment.

Marcus glanced behind himself to confirm that he had already checked those shelves. Marcus turned back to the clerk.

"I did not see it there." responded Marcus. "In fact, I did not see any ingredients that I recognize. Everything seems to be encoded."

"Shorted," responded the clerk without additional explanation. Before Marcus could ask for clarification, the clerk hopped off his stool and walked around the counter. He proceeded up to the nearest shelf, selected a small bottle, and returned to the counter. He placed the bottle on the counter.

"That will be three copper pieces." said the clerk.

Marcus studied the bottle. It was labeled with large letters: "RP3p". He picked up the bottle and turned it over in his hands, searching for any other markings. There were none.

"Are you sure this is powdered rose petals?" Marcus asked.

The clerk nodded. "Yes. This one clearly states 'RP3p', which means 'Rose Petals Powdered'."

"I see. You abbreviated it. RP for Rose petals and p for powdered. But why the 3?" asked Marcus.

"There is more than one ingredient that can be abbreviated as RP. RP1 is 'Raspberry Puree', RP2 is 'Red Pollen', RP3 is 'Rose Petals', and so forth." answered the clerk.

"That is terribly confusing." exclaimed Marcus. "I have never heard of such a strange system."

A troubled look crossed the clerk's face. "It is my own scheme. It is more efficient." he explained.

"More efficient? You have to figure out awkward abbreviations in order to understand anything." objected Marcus. "It is a wonder that anyone can find what they need."

"But the abbreviations all make sense." responded the clerk. "They are all quite simple actually. How else would you abbreviate 'Rose Petals'?"

"I would not!" answered Marcus. "I would label each ingredient clearly with its proper name."

"But that is so inefficient." complained the young clerk. "Everyday, I have to copy hundreds of potions to sell to patrons. I have to do that all by hand. Do you know how much faster it is to copy potions with this new system? I save hours."

"My word!" exclaimed Marcus. "You sell potions that use this idiotic encoding? Are you serious?"

The clerk did not respond.

"Do you know how dangerous that is? What if one of your customers confuses rose petals and rabbit pellets? It could be a disaster!" argued Marcus.

"But it is more efficient." protested the clerk.

"For you… and at the moment." countered Marcus. "But it makes the potion recipes harder to understand. Worse, it makes it easier to make a mistake."

"But it is shorter." tried the clerk.

Marcus shook his head sadly. "I know it seems faster and more efficient now, but there is a high price for using such shortcuts. It is much better to use clear names. Trust me. I have confused ingredients before; it never ends well."

"You have?" asked the clerk.

"Yes. I once copied down a recipe with 'S' for Salt. Unfortunately, three weeks later, I mistakenly read it as Sulfur. S for sulfur seems quite reasonable. Needless to say, the bread tasted terrible. It was completely inedible."

The clerk did not seem to have an argument for that. "I guess that I could change them back." he said.

"Yes. You should." encouraged Marcus. "Now. Are you absolutely sure that this is the ingredient that I need?"

The clerk hesitated.

"I see." said Marcus. "I will be back some other time then."

And with that Marcus left the store. He turned down a side street and started for the "Potion Ingredients and More" shop on the other side of town. It was a long walk and the prices were higher, but he needed to be absolutely certain that he had the correct ingredients. The last time he had incorrectly mixed up a batch of magic soap, he had ended up smelling like a skunk for a week. There were some things on which he refused to take any chances.

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

Also see Ann's experience with names in The Importance of (Variable) Names.

Or read more practical advice by Marcus in: The Importance of Unit Testing Magic Spells; Data Validation, Marcus, and the Minstrel of Cheese, or Version Control in Magic Spell Development.

Recursion, Overhead, and Computational Graffiti

Recursion can allow a complex algorithm to be specified in a short, simple, and often beautiful form. A function calls itself on a subset of the data, using the results from those subproblems to form the final solution. However, Recursion can also add computational overhead due to the new recursive function calls.

On her way to the library of Alexandria, Ann could see the signs of chaos engulfing the kingdom. The traditionally smooth operation of the kingdom's services inefficiently squeaked along under the burden of additional complexities. Overhead the pigeons of the kingdom's vast carrier network flew about aimlessly. The postal carriers had given up sorting the mail before embarking on their delivery routes. Instead, they stood in front of each mailbox and flipped through their full bag to find that house's letters. Everything was a mess.

Ann first noticed the computational graffiti in the outskirts of Alexandria. Initially, it looked harmless -- the rebellious proclamations of teenagers: "DFS Rulez" or "Dynamic Programming FTW". The signs soon became more troubling: "Say 'No' to Big-O" and "BRUTE FORCE ALGORITHMS FOREVER". At first, Ann thought these signs were jokes. Who would argue against an efficient algorithm? The absurdity made them almost unbelievable.

Then Ann saw a message that stopped her cold:

int RecursiveAdd(int n, int m) {

if (m == 0) return n; // base case

return RecursiveAdd(n, m-1) + 1;

}

The recursive algorithm for adding two numbers covered the entire North wall outside a Florist's shop. While technically valid, the sheer inefficiency of the of the approach shocked Ann. Why take a simple mathematical operation, m + n, and embed it within a chain of m function calls? The overhead was staggering. The graffiti clearly pointed to the complete collapse of computational thinking.

Tearing herself away from the disturbing image, she broke out in a full run. There was no time to lose.

The Curse of Excessive Commenting

Good comments can improve the readability of code. However, over-commenting can do the opposite. Unnecessary comments waste both space and the reader's attention without adding value. Many lines of code do not require additional explanation. If you find yourself writing "// set i to 0" before the line "i = 0;", you are doing something wrong.

The town's blacksmith, Drex, had been cursed. Drex freely admitted that he had provoked the wizard, but the curse seemed like an extreme reaction. The wizard could have simply insulted him back or walked away. There were plenty of reasonable options. He did not have to curse Drex.

As annoying as the curse was to Drex, his apprentice Rachel was suffering more. The Curse of Excessive Commenting was designed to annoy both the teacher and the student. Whenever Drex explained something, he now did it in excruciating detail.

"Now, watch how I form this hinge." Drex instructed his apprentice. "First, I pick up the metal with these large tongs. They are made of a heavier metal, so they will not burn or melt in the fire. Then I use the tongs to put metal in the fire where it will heat up."

As he spoke, Drex grabbed a small blob of metal with his tongs and shoved it into the fire. After a moment, Drex felt obligated to add "I am still heating it up in the fire." He reiterated this observation five more times before the metal was hot enough to work.

"Now I will use the hammer to flatten the metal." Drex explained. "I am hitting the metal with the hammer. I am hitting it again. I am hitting it again."

Rachel stood off to the side, watching. After the tenth repetition of "I am hitting it again", she rolled her eyes. Not only were these descriptions incredibly annoying, but it also made it hard for her to actually follow what was going on. Drex was narrating at such a low level that it was difficult to pay attention to the high-level flow. The concept of forming the hinge was overrun by a constant stream of tiny details.

"I am hitting it again." narrated Drex.

The first time that Drex had described the process of making a hinge it had been simple. He described the entire first ten minutes of work as: "First, flatten out a small piece of metal." That is all. He had left unspoken the low-level details that any blacksmith should easily pick up -- to flatten metal you heat it and hit it with a hammer.

"I am hitting it again." narrated Drex.

The commentary was driving Rachel crazy. She thought back bitterly to the encounter with the wizard three days ago. Drex had confronted the wizard to complain about his magic candle. The candle had burnt out, which is exactly what magic candles should not do. When Drex had discovered that the candle was the creation of the wizard's apprentice, he had made the fateful mistake of insulting the wizard's teaching skills. "At least I tell my apprentices what they need to know." Drex had bragged. It turned out to be a mistake to taunt a sleep-deprived wizard at two in the morning.

"I am hitting it again." narrated Drex.

At least the wizard was not evil. He had placed only a temporary curse on Drex, forcing him to over-comment on all of his actions for the next week.

"I am hitting it again." narrated Drex.

Unfortunately, Rachel did not know if she could last another four days.

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

Also read about the importance of good comments in baking. Or read more about Drex in Loops and Making Horseshoes.

Sorting During the Flu Outbreak: The Reality of Sorting Small Sets

When selecting an algorithm, it is important to understand the context in which it will be applied. An algorithm's computational complexity only tells part of the story. Other factors to consider include: the size of the data, the existence of other constraints, and additional problem structure that can be used. For example, bubble sort is a reasonable algorithm to use for a very very small amount of data that is almost in the correct order.

For years, Mrs. Magee's kindergarten class won every sorting competition in the kingdom. The powerful combination of constant practice and the merge sort algorithm made them unstoppable. Records were decimated weekly. Soon it was no longer enough for her class to win; they had to finish sorting themselves in less than half the time as their competition. The only true victory was total domination.

Thus, it came to pass that Mrs. Magee became overconfident in the ability of her class. She firmly believed that her kids could win regardless of the situation, and she had no problem explaining that to everyone she met.

Then, in January, the flu hit. Almost all of Mrs. Magee's class was out sick, leaving just three students in class. It was under these conditions that Mr. Wallace's second graders challenged her to a sorting competition. He also had three healthy students, so the classes were equally matched. But his class only understood the lesser "Bubble Sort" technique. His search could take O(N^2) time!

As soon as the moderator shouted "Go", Mrs. Magee's class split into two groups. One group had two students, and the other had only one student. The merge sort had begun.

In contrast, Mr. Wallace's students looked at each other. Billy and Sue did a quick comparison in their head and swapped places. All three were now in the correct order.

"No!'" wailed Mrs. Magee, but it was too late. The competition was over.

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

Read about the skill of Mrs. Magee's class in Merge Sort and Lines of Kindergarteners. Or read about other sorting algorithms in Why Tailors Use Insertion Sort or Bullies, Bubble Sort, and Soccer Tickets.

Merge Sort and Lines of Kindergarteners

Merge sort is a recursive, sorting algorithm based on two intuitive principles:

1) It is easy to sort very short lists. In fact, it is trivial to sort lists containing only one item.

2) It is easier to merge together two sorted lists than it is to sort a long list.

Using those ideas, the merge sort algorithm can be described simply as: "Break the data to sort in half, sort each half separately using merge sort, and merge the halves back together into a single sorted list."

Ann's kindergarten teacher, Mrs. Magee, was fiercely competitive. She insisted that the class excel in everything. Her class always had the highest test scores. Her class always won at dodgeball. And, most important of all, her class could form a sorted line faster than any other class in the kingdom.

It did not matter how the class was being sorted. They could line up by height, by first name, by last name, by length of their left pinky toe, or even by their skill at dodgeball. Mrs. Magee would call out an attribute, and the class would spring into action.

Like all winning teams, their excellence depended on more than natural talent. In fact, most kindergarteners in the class were absolutely dreadful at sorting when they started school. Once, two students, Jack and Jake, had spent fifteen minutes trying to compare the order of their names. It was embarrassing.

The class's ability came from practice. Mrs. Magee drilled the class for hours at the start of the school year. Every time the students went to the bathroom or to lunch, she would first make them line up in some sorted order.

Of course, there was also a strategy -- Merge Sort. It was her secret weapon, her key to winning.

At the command "LINE UP!" the class would split into two equally sized groups.

Class before sorting

First split

Those groups would then each split into two smaller groups.

The splitting continued until each group had just a single person.

Then, starting from each pair of singletons, the groups would reform. Each child would look at their partner and quickly line up in order. With only two people it was easy. A single quick comparison provided the order.

After the groups of two were in order, the kids would merge into larger groups. Again, merging was simple -- you only needed to compare the two kids at the front of the two lines. The person with the smallest value had to be one of the first two kids, because the lines were sorted. The first two kids would compare, and one would step forward to start the new sorted line.

Merge Step 1

Now the second smallest still had to be one of the front two kids.

Merge Step 2

And so forth.

Merge Step 3

Merge Step 4

Merge Step 5

The lines would quickly merge together, forming larger groups. This would continue until the entire class was in order.

That is how Mrs. Magee's class won the sixth annual kingdom sorting championship. Her class was in order a full five minutes before the runners up. In fact, Mr. Frizzle's fifth graders were still comparing the numbers of freckles on their right arms when Mrs. Magee's champions had left for lunch.

To be continued in Sorting During the Flu Outbreak: The Reality of Sorting Small Sets

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

To learn more about other sorting techniques see Why Tailors Use Insertion Sort or Bullies, Bubble Sort, and Soccer Tickets.

Connected Components and the Birthday Sign

A connected component in an undirected graph is a set of nodes such that any node in the component can reach any other node in the component via a path of edges. Two sets of nodes are not in a single connected component if there is not path between them.

When many people think about connected components in graphs, they think about: abstract circles and lines, island bridges, computer networks, or the power grid. These are classic examples of graphs and the importance of connected components. Power cannot flow from one end of the city to the other unless there is an edge (i.e. power line) linking the two sides. Similarly, two computers cannot communicate without a network link between them.

In contrast, when I envision connected components, I often go back to a story from childhood: the tragedy of the large, paper, birthday sign. Granted, birthday signs are not the typical example of a graph. And as far as graphs go, they are relatively boring. A single party-sized birthday sign might include 13 nodes (the letters H-A-P-P-Y-B-I-R-T-H-D-A-Y) joined by 11 edges (metal fasteners or small lengths of string). Each node is connected to at most two other nodes -- the letters on either side. And together, they form a single connected component. Except when the sign is broken.

The tragedy of the broken birthday sign is that, as two separate components, the sign does not hang correctly. Instead, the two sides, each containing part of the original message, hang awkwardly down. It is a disheartening sight that has forced more than one party-goer to run from the room and compose themselves.

To break a new birthday sign all that you need is a small rip in the paper -- a single fastener losing its hold. This can happen in a variety of ways. The most popular disasters tend to be: the young kid that believes the sign can support his or her weight, the uncle that was not paying attention while walking, the rogue piñata stick, and the arrival of hungry giraffes.

But despair not. The good news is that, in almost all of these cases, the graph can be restored to a single connected component with a small amount of tape.

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

For more about graphs, read about Ann's trip to the City of G'Raph.

NEW at Computation Fairy Tales: A list of stories index by level of CS background. Feedback welcome.

Remember for all the updates, follow CompFairyTales on twitter.

The Marvelous IF-ELSE Life of the King's Turtle

The IF-ELSE statement is a computational construct that allows the program to branch off and execute one of two different blocks of code. The IF statement starts by evaluating a Boolean clause. If this clause evaluates to true, the block of code conditioned on this IF statement is executed. If an ELSE statement is present, it can provide a block of code to execute in the case where the Boolean clause evaluates to false.

Fido, the King's prized pet turtle, lived a charmed life. He spent his days in the garden fountain, swimming and sleeping. He did not have any magic powers, aside from the ability to amuse himself for an hour by staring at a pebble, but King Fredrick was quite fond of him. The castle's servants took good care of him. They made sure that his fountain was always mostly clean -- Fido did enjoy the occasional patch of slime on the ground.

Fido lived by a series of simple rules. In fact, since his brain was roughly the size of a pebble, they were incredibly simple IF-ELSE style rules. These rules made up Fido's entire daily routine. For example, he had very simple logic to determine when he ate:

IF he is hungry

eat

This logic worked out great for Fido, because he ate when he was hungry. And, as a natural consequence, he did not eat when he was not hungry. It was quite a good system.

For some aspects of life, the IF statement could have two different actions depending on the condition. For example, when he was swimming:

IF the fountain is on

play in the fountain

ELSE

swim around the large rock

Obviously, Fido enjoyed the fountain more than the rock.

Sometimes the decisions would be complex enough to require a series of chained IF-ELSE statements:

IF it is sunny

sit in the grass

ELSE IF it is warm

go swimming

ELSE

sleep

The gardener responsible for taking care of Fido often joked that: "All that turtle does is eat, sleep, and swim", which was not far from the truth. The logic that ruled Fido's life consisted of about fifty different actions contained within chained and nested IF-ELSE statements.

A scholar had once spent a week studying Fido, and he had managed to record the entire logic for Fido's routine on a single scroll of parchment. If Fido had been intelligent enough to understand what that meant, he might have been offended. Instead, he sat in the grass -- it was sunny.

Then, one day, the unthinkable happened. The gardener decided that Fido was probably getting bored, so he added a SECOND large rock. This addition threw off Fido's IF-ELSE based routine completely. It took almost a full week for Fido to come up with a new routine that suited his new environment. In the end, he added another IF-ELSE:

IF he is closer to the right rock

swim around the right rock

ELSE

swim around the left rock

Thus order was restored to his life.

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

For more discussion of IF-ELSE also see Learning IF-ELSE the Hard Way.

Inheritance in Cheeses and Magic Spells: Part 4 of Marcus and the Cursed Cheese

In object oriented programing, inheritance refers to the ability to create derived classes (or subclasses) of a class. These derived classes can reuse attributes or code defined in the original (or base) class. The subclasses are said to inherit the attributes and methods from their base class. In addition, these new classes can also contain code that is specific to the new class itself. This process allows programmers to reuse common blocks of code while still creating more specific classes. [For more information on classes see the previous story].

"Can you tell me anything more about the visitor?" asked Marcus. He was very worried.

The foreman thought for a moment, but shook his head. "Only that he asked a lot of questions and seemed particularly interested in an outgoing shipment of cheese."

"This is bad," stated Marcus.

"Why?" asked both the cheese minstrel and the foreman.

"The wizard that cursed my cheese did so without knowing what type of cheese it was." Marcus explained.

"So? Is there really a difference in cursing different types of cheese?" asked the cheese minstrel.

"There can be a big difference." answered Marcus. "All classes of cheese are derived from a common 'Cheese' base class. Thus they inherit certain properties and actions. For example, all cheese is created from milk. And all cheese has a weight, density, etc. So to that extent, you could target a spell at the base class of cheese itself. All you would need to know is that you are dealing with some class of cheese."

"But, in addition to the inherited properties, each class of cheese has properties of its own." continued Marcus. "For example, some cheeses cause a little popping sensation when eaten."

"Likely Patagonian Popper?" asked the cheese minstrel. Honestly, he was more interested in the cheese aspect of this story than in the magic spells.

"Yes. Exactly." confirmed Marcus. "Knowing which subclass you are dealing with has certain advantages. For example, you can tailor your spell to easily hide within the specific properties of the cheese. In this case, I thought that the wizard who cast this spell was explicitly using the fact it was bleu cheese."

"But since we do not label the boxes with cheese type, the wizard must not have known what cheese he was dealing with." finished the foreman.

"Yes. And that means that we have a very sophisticated wizard on our hands." confirmed Marcus. "Since the shipping labels have the names on them, he could also target my cheese directly. Was anyone else here that might have seen him?"

"Only Sam, the logistics manager." answered the foreman. "But he is having some personal issues at the moment."

"What sort of issues?" asked Marcus.

"He became unnaturally obsessed with some salesman routing problem. He claimed that he could revolutionize my cheese sales if he just solved it. But after 2 weeks, he had not made any progress. I finally had to send him home."

"The traveling salesman problem." Marcus whispered under his breadth. Then louder: "When did this start?"

The manager thought for a moment. "You know, it was right after that visitor."

Marcus nodded. "I have seen this curse before -- the spell of Unnatural P=NP Obsession. It is a powerful spell. Luckily for you, I am one of three wizards in the kingdom that can break this spell."

The moment he said those words, Marcus realized a few things. First, he knew why he had been targeted with cursed cheese. Second, the kingdom was in grave danger. Third, and most shocking, he was not longer hungry for cheese.

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

See how the saga of the cursed cheese began with Part 1: Data Validation, Marcus, and the Cheese Minstrel. Or read about Ann's discover of the spell of Unnatural P=NP Obsession during her trip to G'Raph.

Or if you think the cheese minstrel has it bad, also check out the plight of the king's hedgehog walker in The Incident at the North Gate (or Why = is not ==).

Want more updates and commentary? Follow CompFairyTales on Twitter or follow the author (Jeremy Kubica) on Google+.

Classes of Cheese: Part 3 of Marcus and the Cursed Cheese

In objected oriented programming, a class defines the type of an object. In particular, an object's class defines the data and methods for that object. Alternately, the individual objects in a program can be viewed as specific instances of a class.

There were stacks of cheese everywhere. The tables were covered with half-filled containers of bleu cheese, brie, feta, mozzarella, and ricotta. Along the wall were large wheels of cheddar and blocks of swiss cheese. It smelled like a good cheese shop should. Marcus suddenly realized that he was incredibly hungry.

"Pardon the mess," started the foreman. "We are in the middle of packing today's soft-cheese shipment."

"There is so much cheese." the cheese minstrel breathed quietly. He was in awe. Never in his life had he been around so much cheese. And for a cheese minstrel, that is saying a lot.

"And over at that table, we are preparing for our shipment of the Swiss Cheese class." added the foreman while motioning to a table covered with blocks of swiss cheese. There had to have been at least fifty blocks of cheese on the table, stacked into neat piles.

"Class?" asked the cheese minstrel. Before the foreman even started to answer, the minstrel had his pad of paper out and was ready to record every detail.

"Yes. Those cheese blocks were all formed by our machines using the same recipe." answered the foreman. "We simply tell the machines: make a block of the swiss cheese class. The blocks have different attributes, such as size or number of holes, but they are all instantiations of swiss cheese."

The foreman walked over to the swiss cheese table. "Take these two blocks. We would describe both as Swiss. They are described by the same internal attributes, such as: weight, size, number of holes, sourness, etc. Granted, they actually have different values for those attributes depending on the specific block, but the attributes themselves are the same. And they have the same range of behaviors, such as EmitSmell."

"Emit smell?" asked the cheese minstrel without looking up from his notepad.

"Yes. Cheese does not have many actual behaviors, but it certainly does smell. Come have a sniff of our new triple-mold ultra-bleu cheese. I think that you will find it most interesting."

Marcus shook his head to try to clear away his current cheese-inspired trance. He had been staring at the massive quantities of bleu cheese for the better part of the conversation. His stomach was rumbling, but he had a mission. He needed to determine who had cursed his cheese. "Can you tell me what your visitor was looking for?" he asked.

"I am not sure. He just wandered around for a little while muttering to himself. He stopped and looked at some of the outgoing cheese shipments. But that was all. He never touched anything."

"Boxed or unboxed?" asked Marcus. "Was the cheese already packaged?"

"Uh..." the foreman seemed confused. "I think it was already in its boxes. Why?"

Marcus did not answer. His mind was racing. It was worse than he had thought.

To be continued in Part 4: Inheritance in Cheeses and Magic Spells...

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

See how the entire saga of the curse cheese began in Part 1: Data Validation, Marcus, and the Minstrel of Cheese

Objects, Encapsulation, and Cheese Factories: Part 2 of Marcus and the Cursed Cheese

In object oriented programming, objects are types of data structures that include both data and methods for operating on the data. By including both the data and the methods in the same structure, it allows each object to trivially work with its own data. One of the major advantages of objects is that they allow easy encapsulation. Internal data can be hidden from external code and thus only be operated on by the object's own methods.

"I assure you that I inspect all of that machines daily. There is no way that they could produce any inferior cheese. We maintain the highest standards!" argued the foreman.

"I am not claiming that your cheese was inferior, spoiled, or even contained bog dragon droppings. I am not questioning your cheese making standards or your ability to maintain them." argued Marcus. "What I am saying is that the cheese was CURSED. Curses do not happen by accident. This was intentional."

After fifteen minutes of arguing, Marcus was already exasperated. He was on a mission to determine who had cursed his cheese, and the foreman of the Cheswick Castle Cheese Factory was not being helpful. It was not as if the foreman was intentionally dodging Marcus's questions; he simply seemed unable to accept that anything could be amiss with his cheese. Cheswick Castlle was known across the kingdom for producing superior quality cheeses.

"That is simply not possible." countered the foreman. "I would know!"

"How?" asked the cheese minstrel, who had been quietly standing off to the side and scribbling notes. He had promised Marcus that he would not get in the way. So he really did not want to interfere with this discussion, but this seemed like an important point for his new "Ballad of the Cheswick Cheeses". The minstrel wanted to make sure that he got the details correct.

"Yes. How?" added Marcus. "I already told you that this particular curse only targets wizards."

"We have a very sophisticated cheese making process here. We use the latest cheese making objects. They are fully self-contained." explained the foreman.

"Cheese making objects?" asked the minstrel. In all of his years as a cheese minstrel, he had never heard of cheese making objects. He suddenly wondered if he was failing as a cheese minstrel. The self-doubt was crushing.

"He means machines." explained Marcus. Then turning to the foreman, Marcus asked "Why do you call them objects?"

"It was something a recent visitor said," explained the foreman. "He was very impressed with the machines, and he spent a good hour looking one over. He said that the machines were like objects -- they contain both attributes and methods to work with those attributes. The attributes are things like temperature, tray orientation, or humidity. And the machine can operate on these with methods like Bake, Cool, or SpinTray. That way the operators do not need to work directly with the internal attributes, they can just use the externally facing methods."

"Isn't that the case with most machines?" asked Marcus. "That is what makes machines different from something like the minstrel's notebook. The notebook contains data, but cannot do anything with it. It just stores it." Marcus was unimpressed, and he was beginning to think that the foreman was stalling.

"Well..." The foreman thought for a while. "I think you are correct. But our machines are top of the line."

"How do you know?" asked Marcus. "One of the advantages of encapsulation is that you do not need to know about the internal workings. Even the values of the attributes can be hidden from you. How do you know the temperature is correct? Or that the machines even use a process involving temperature? Maybe the machines just bake the cheese at a random heat for a random period of time. All you know if that you get good cheese at the end."

"Ah." The foreman smiled. "In addition to consistently producing superior cheeses, we also have created an extensive suite of unit tests to confirm that the machines are doing what we expect. Here at Cheswick Castle, we maintain the highest standards."

"Yes. But do you test for curses targeting wizards?" pushed Marcus.

"Well... No." answered the foreman. He suddenly looked very worried.

"Tell me more about this visitor." commanded Marcus.

"I can't tell you much." answered the foreman. "I never got his name. He wore a long, dark cloak. He claimed that he was here to inspect the machines, but he only looked at one. He spent an hour with it."

"Can I see the machine that this visitor was so obsessed with?"

Marcus had to admit that the machine was impressive. It must have stored and controlled over a hundred different variables that represented the cheese's current state. But all of that complexity was hidden from the operator behind a simple, clean set of controls.

Unfortunately, a quick check of the machine revealed no signs of a curse causing subroutine.

"Did the visitor look at anything else?" inquired Marcus.

The foreman, now sufficiently panicked, nodded vigorously. "He wanted to see our shipping facility. He said something about wondering where all our cheese went."

Marcus was certain that in the shipping area, he would find both stacks of cheese and a list of wizards awaiting their shipments.

To be continued in Classes of Cheese: Part 3 of Marcus and the Cursed Cheese...

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

Read about how Marcus met the cheese minstrel in Part 1: Data Validation, Marcus, and the Minstrel of Cheese.

Or read about Marcus and the importance of unit testing in The Importance of Unit Testing Magical Spells or good version control in Version Control in Magic Spell Development.

Integer Overflow and 00000 Customers Served

Integer data types store values that are mathematical integers. Depending on the programming language and the exact data type, the amount of storage space allocated for an integer can differ. The space directly determines the maximum number of values that can be stored in the variable, and thus the highest value that can be represented. For example, an unsigned 16 bit integer can store 2^16 = 65536 different values-- the numbers 0 to 65535. In some programming languages, assigning a value outside this range will cause the value to "wrap around". Luckily, most modern program languages allow 64 bit integers, providing an upper bound that will match almost every possible use case.

"I like the sign." declared Zed. It was his first visit back to the castle and his pilot store since he had left the coffee business to speculate in coconut sales.

While the new management had resisted making any radical changes to Zed's Coffee shop, they had insisted on a flashy new sign. The sign was at least six feet wide and stood fifteen feet above the ground. It was lit by ten different torches around the base so that it could continue to attract in patrons at night. Some people had claimed that this sign represented the future of coffee advertising.

However, one thing about the sign bothered Zed: the message saying "02053 Served". It reminded him of a problem that he had once encountered with the coffee shop. So he had decided to ask the new manager about it.

"How do you update the sign?" inquired Zed.

"It is pretty simple." answered the manager proudly. "Each digit is a different card. Every morning Rob, over there, climbs up a ladder and changes the digits to reflect the previous night's count. He has to pull down the old cards and put up new ones."

Zed nodded politely. He was, of course, familiar with the principle. Anyone who had been in the coffee industry would know how such a sign worked. He was simply warming up to his real question.

"So, you have five digits -- zero through nine." confirmed Zed. "But what happens when you rollover?"

"Rollover?" asked the manager.

"Yes." replied Zed. "What happens after you serve customer 99,999?"

The manager looked shocked. "We... Well... I... I never thought of that." he answered.

"Ah." responded Zed knowingly. He had considered the same board a few years ago, but his experience with the coffee menu board had taught him to be wary of a fixed number of slots. Specifically, a fixed number of digits limited the maximum number that could be displayed. And, in this case, five digits was absurdly small for a successful coffee chain.

When Zed left, ten minutes later, the coffee shop's manager was still on the phone with the sign company. Zed could hear the manager shout: "I can't just let it overflow. Do you know how bad it would look to have it wrap around to say '00000 served'?"

Zed smiled to himself. While coconut speculation did not have the same level of excitement as coffee shops, sometimes that was a good thing.

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

See how Zed's coffee shop got its start with: Arrays, Linked Lists, and Zed's Coffee Shop.

Or learn more about how numbers are represented in binary with: Unhappy Magic Flowers and Binary.