Who is the target audience?

I have seen the questions of "Who is the target audience for these fairy tales?" and "How can they teach computer science?" come up a few times. Most recently, this was asked by an reviewer of the book.

To be honest, these are questions that I asked myself many times when I was starting.

Below I outline some of the thought process behind the stories, the book, and how they can be used.

Computational Fairy Tales is not a textbook:

I contemplated using the stories to frame a full introductory textbook. But there are a lot of good textbooks out there already. Honestly, I have always seen these stories as supplementing a class or standard textbook. The stories are designed to motivate topics, provide context, and (hopefully) generate interest. The best parallel that I can draw is that each story is meant to serve the same role as an illustration in a textbook; it provides a different way of viewing the problem.

Motivating computational thinking:

The goal of Computational Fairy Tales is not to provide comprehensive coverage of each topic, but rather to provide a high level overview of the breadth and excitement of computer science. Ideally the stories inspire that reaction of "That's interesting…" or "I had not thought about it that way…", followed by a desire to learn more. In rare cases, there might even be laughing involved.

Using Computational Fairy Tales in a class:

Last week, I had the pleasure of talking to a group of high school teachers at CS4HS about Computational Fairy Tales and how they could be used in classes. I proposed using the stories as motivation during the discussion of the material:

1. Introduce the concept.
2. Use the story to motivate it or put a new spin on it.
3. Go into more details, possibly involving real code or formal proofs.
4. Assign copious amounts of homework on the topic.

A few of the teachers suggested swapping 1 and 2, assigning the stories to be read the night before as homework. I have seen some of the stories used this way in courses already.

Suggestions? Comments?

I am very interested in learning more about how people use these stories or would like to use them. Please feel free to contact me with questions, suggestions, requests, or comments.

Book (and FAQs)

The Computational Fairy Tales book is available (in print and on the Kindle). More details can be found at the book page, including links to the various stores.

The Computational Fairy Tales book includes ~30 rewritten or revised stories from the online collection and 15 all new chapters. Each story serves to illustrate a computational concept, supplementing official instruction or motivating computer science concepts. The stories have also be set up to provide a natural progression both within the computer science concepts and within the fairy tale quest.

Go to the book page.

A few FAQs:

Q: Is this a print copy of your blog? Why should I buy the book?

A: There are a few significant changes. First, there are fifteen new chapters. Second, the book covers the full tale of Ann's quest to save the kingdom from the darkness. The stories are set up to provide a natural progression both within the computer science concepts and within the fairy tale quest. Third, the stories have been rewritten and edited by a professional editor.

Q: What is the target audience for this book?

A: It is primarily written for junior high to high school students who are interested in computer science (and their teachers). However earlier versions were read and enjoyed by younger readers. It can also be amusing for people who know about computer science, but want to read about it in a different light.

Q: My favorite story is not there! What's the deal?

A: Not all stories fit into the book. In fact, less than half the online stories were used. Some were redundant and some just didn't fit.

Q: Does this mean that the online collection is going away?

A: No. I want these stories to continue to be useful. I plan to leave the current collection of stories online. However, I do not plan on updating them all (I have updated a few). So think of the online versions as very rough first drafts of the final stories.

The Importance of Design in Five Course Meals

For any moderately complex program or algorithm, it often helps to design the solution before work begins. Good design practices can save a significant amount of time, help avoid wasting effort, and prevent mistakes.

"I can fix this," Chef Pepperton said to himself as he rummaged through a box of fresh vegetables.  "I just need some radishes."

Behind him, the kitchen was in chaos.  The other cooks dashed about, trying to prepare the remainder of a five course meal.  The soup had just been carried out, and the other four courses were far from ready.  In fact, they were not exactly decided yet.

"Radishes?!?" screamed Chef Pepperton.  "Do we have any radishes?"

One of the other chefs paused for a moment in thought.  "No," he said.

Pepperton turned back to the box.  "I can fix this," he mumbled. "Carrots.  I can do it with carrots."

Then he loudly announced, "We are changing the menu to carrot ravioli.  CARROT RAVIOLI."

In the back corner of the kitchen the dessert chef groaned.  Since Chef Pepperton had now claimed the carrots, the dessert chef scratched his plans for carrot cake and started working on a chocolate pudding.  He hated when Pepperton changed his mind halfway through a meal.

"How is the appetizer coming?" Pepperton asked.

"A little burnt, but we can peel off the worst bits," answered his assistant.

Pepperton looked at the stove top.  Three pots and two pans occupied the stove's five burners.  Delicious aromas crept from two of the pots and a beautiful sauce simmered in one of the pans.  In the other pan, the cooked tomatoes for the appetizer sent up curly wisps of black smoke.  The final pot contained boiling water, but Pepperton could no longer remember what he had meant to boil.

Pepperton cursed under his breadth.  He thought for a moment, surveying the countertop for inspiration.  Then he replied, "Add some lime juice and call it something festive."

An hour ago he had felt a lot better about this meal -- confident even.  "I can whip up a five course meal for his majesty," he had boasted.  "I'm sure we have everything we need in the kitchen."

"If we do ravioli, we need another burner," noted his assistant. "Something else will have to come off."

Pepperton looked at the stove.  He counted the burners to confirm the problem.  Even if they took off the now charring tomatoes, they were one burner short.  He racked his brain and scanned the kitchen.  He again saw the mysterious pot of boiling water.

"Forget the mashed potatoes," he said, his memory kicking in. "Throw the potatoes in the fire for two minutes and call them charred potatoes.  Say they go with the tomatoes.  We'll use the boiling water for the ravioli."

"I need the fire for the salad," protested the assistant.

"Make it a cold salad," ordered Pepperton.  "And where is the salt?"

"Over here," called the dessert chef.

Pepperton dashed over to retrieve the salt.  "Curse the king's surprise visit," he thought.  Then he quickly amended his internal commentary to include a statement on how nice it was that the king had chosen this dining establishment. You could never be too careful.

"And the radishes?" asked Pepperton.

"You switched to carrots," reminded the assistant.

"Hold on a second," said Pepperton. "I think I might need to write this down."

An unnatural hush fell through the kitchen. It was worse than if someone had screamed it out loud.  Pepperton knew what everyone was thinking.  He could hear his own boastful words echo through his head, "We don't need any planning. We've done this a hundred times. We'll just put something together."  He shook his head to clear away the doubts and tried to concentrate on saving the meal.

He was halfway through finally writing down a menu when his assistant interrupted him. "Chef, your carrots are burning."

Pepperton groaned and crossed "Carrot Ravioli" off his menu.

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

Want to read more about programming and kitchens?  See Variable Initialization in Busy Kitchens or Computer Memory and Making Dinner.

Book update: The second draft of the book is complete.  It includes 30 revised stories and 15 new stories.  Story list coming soon.

Enums and Hair Colors

Enums, or enumerated types, are data types that can take on a fixed set of values. The elements in the enumerated set are named, allowing programmers to reference specific elements in an understandable form. These data types allow stricter checking (elements must be one of a limited set) and improved code readability (actual names are used).

"It is blue!" wailed a lady three chairs over.

Angela snuck a glance. Sure enough, the woman's hair was a vibrant, electric blue. Angela turned her attention back to the head in front of her.

"I… I…" stammered Derek. He stood behind the blue-haired woman. His face registered a mixture of shock and fear.

"It is supposed to be blond," screamed the lady. "But it is blue!"

"I know," said Derek. "It is just that… I thought… Umm... let me go check something."

Angela heard Derek rush toward the supply room. Knowing the seriousness of the problem, Angela paused, excused herself, and followed Derek. It was only Derek's first week; he could probably use some help.

Angela found Derek in the supply room staring at a shelf full of dye bottles. The salon's owner Karen stood next to him gesturing angrily.

"I picked the wrong bottle," moaned Derek. "I thought blond was bottle #14, but it was #15. Oh no! What am I going to do?"

"It is not his fault," interjected Angela. After a brief pause she added, "Well, technically it IS his fault. But this system makes it easy to make mistakes."

Karen spun toward Angela, anger in her eyes. "Not this again! I have used this system for ten years. Everyone who works here learns it."

Feeling protective of Derek, Angela pressed on. "It is a bad system. You have 20 different hair dyes in numbered bottles. In order to find the correct dye, you need to either remember or look up the correct 'magic number' for that color. It is too easy to make a mistake."

Karen waved dismissively. "What would you suggest?" she asked. "We already implemented a bunch of your ideas, and they always seem to add overhead. Just last month, we started unit testing the hair dryers. What now?"

Angela noticed the Karen had omitted the fact that the ideas also prevented errors. She decided not to press the point.

"Enums," answered Angela.

"Enums?" asked Derek.

Karen squinted in confusion as if wracking her brain.

"An enumerated type is basically a set of NAMED elements. You refer to an element in the set using its name, instead of some magic number. For example, in this case we could create an enumerated type for hair dyes. It would contain items like BLOND, DIRTY_BLOND, PLATINUM_BLOND, SUNSET_RED, and so forth. Then, to find the correct color, you give the name of the type."

"We tried that," said Karen. "Remember, the stock person could never remember how to spell 'blond'. The bottles were labeled 'blund' or 'bloond'. That is why we started using numbers."

"Enums give the best of both worlds," Angela assured her. "Like the numeric options, you have a limited set of options. And, like the free text labels, you have descriptive names. No more spelling errors. No more memorizing magic numbers."

Karen was silent for a moment. "What will it cost me?" she asked.

From outside they heard a loud, tearful scream. "Blue!!!"

Angela shrugged. "I guess that it will take longer to write the color code on the form, since the name will be longer than a number."

"BLUE!!!" came another scream.

"I think it might be worth it though," Angela added.

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

Thank you to David Karl for recommending the topic of enumerated types!

Want to learn more about practical programming tips? Read about the importance of: variable initialization, unit testing, source control, comments, or data validation.

Classes, Inheritance, and the Three Little Pigs

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 can 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.

Once upon a time, three little pigs decided to leave home and venture out into the world. They traveled together for a few days until they came upon a charming village nestled within a large forest. Immediately taken with the beauty of the village, the pigs decided to settle there.

Each pig found an open plot of land and began setting up his new home. The first order of business was to build a house. The pigs, knowledgable in both architecture and object oriented programming, each created houses based on the common House class. The House class specified the basic attributes, such as NumberOfWindows, and functionality, such as HeatHouse, that people had come to expect in a house. However, each pig chose a unique subclass to suit his own needs.

The youngest pig decided create a house from the StrawHouse subclass. Many people have argued that this was done out of laziness, as the Build operation for StrawHouse houses requires little work. However, the truth is that the pig had always marveled at the concept of thatched roofs, and the possibility of creating an entire thatched house was exciting.

The middle pig decided to create a house from the WoodHouse subclass. Again the reason went beyond the cost of the Build operation. The second pig preferred the rustic look of wooden houses. Moreover, wooden houses had a nice HangPictureWithNail function that appealed to the pig.

The oldest pig was obsessed with safety. He built his house from the SecureBrickHouse subclass, paying a large upfront cost. He slept better at night knowing that his house provided unique functionality of LatchDeadbolt.

Then, one night, a big bad wolf wandered into the village. He spotted the first pig's house and hungrily eyed its inhabitant. He walked up to the straw house's door and pounded. Of course, knocking on the door was a function that could be applied to any house subclass.

"Little pig, let me in. Or I will huff and puff and blow your house in." threatened the wolf.

"Not by the hair on my chinny chin chin." responded the pig. Despite his bold words, he was worried. He knew that his house had a very poor response to WithstandWind. He very much doubted that his house could handle the breadth of a asthmatic turtle, let alone the wolf.

Fortunately for the pig, the wolf was unaware that houses in the StrawHouse class lacked a LockDoor function. That oversight gave the pig some time. As he heard the wolf begin to huff, the little pig made a small opening in the back of the house and ran for it.

The wolf was in the middle of his first puff when he saw the pig running. He grinned wickedly and gave chase.

The little pig reached his brother's wooden house mere seconds before the wolf. He slammed the door behind him and flipped the lock. His brother looked up from a newspaper.

"Wolf… huff… puff…" was all the first pig could get out between his own heavy breadths. It had been a long run uphill.

Outside the wolf surveyed the house. The construction of this house was more solid, but he was confident that he could still blow it down. And now there were two tasty pigs inside.

"Little pigs, let me in. Or I will huff and puff and blow your house in." threatened the wolf.

"Not by the hair on our chinny chin chins." responded both pigs in unison. Then they looked at each other and darted toward the back of the house. They knew that the house did not stand a chance.

The wolf, seeing the pigs darting out of the house, again gave chase. This time the two little pigs headed to the house of their older brother. It was a long run, but they knew his SecureBrickHouse could withstand a lot of huffing and puffing.

They made it to their brother's house before the wolf. Their brother was in his yard, digging a deep moat. Although he knew that a moat was unnecessary in this neighborhood, it would help him sleep better at night.

"Brother… wolf… huffing…" the two new arrivals panted.

The brother looked up and saw the approaching wolf. The three little pigs dashed into the house, threw the deadbolt, and closed the windows.

"I told you that the cost of the SecureBrickHouse would pay off," started the oldest pig in a lecturing tone. In his view, nobody ever paid enough attention to safety.

"Sure," responded the middle pig. "It is great for cases like this. But your house has a terrible implementation of RetainHeat. Do you remember how cold you were last winter? You had to borrow two quilts."

"And the way sound echoes in here is annoying," added the youngest pig. "Have you ever considered putting up some drywall?"

Outside the wolf reissued his threat. He received no answer. The occupants of the house were too busy arguing the relative merits of the different types of houses.

"At least we can all now agree that building a House was a better idea than building a ApartmentBuilding, right?" offered the oldest pig with a quick glance toward the middle brother. "I could never deal with tenants complaints all day. We got the base class correct."

The other brothers nodded in agreement.

Outside they could hear the faint sounds of rushing wind and a hyperventilating wolf.

"Could we create a new SecureWoodHouse?" asked the middle brother. He liked the warm feeling of wood paneling.

The other two pigs paused in deep thought. "Would we derive it from the WoodHouse?" asked the oldest brother.

"Of course," responded the middle brother, "But we could change the implementation of some of the key functions to make it more suitable to this kind of attack. Maybe add some support beams along the walls. And a LatchDeadbolt function, of course."

"Interesting…" said the oldest brother as he thought over the proposal. "What other functions are you thinking about? How about ShutterWindows?"

Outside the wolf had huffed and puffed until he had passed out.

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

Interested in learning more about object oriented programming? Read about it Marcus's visit to a cheese factory (Objects, Classes, and Inheritance).

Interested in computational takes on other classic fairy tales? Read Binary Searching for Cinderella or Goldilocks and the Boolean Bears.

On a random note, this is the 75th actual story on Computational Fairy Tales. Have a favorite story or found one that works? Have a request? Let me know at computationaltales@gmail.com. For updates follow @CompFairyTales on twitter.

Using Binary to Warn of Snow Beasts

Binary is a number system where each digit can only take one of two values: zero or one. Binary is used within computers, because it allows the computer to encode information in a series of switches that are either on (1) or off (0). Each digit of binary represents a power of two. The first (right-most) digit represents the 1's place, the second digit represents the 2's place, the third represents the 4's place, and so forth. For example, the binary number 10110 = 1*2^4 + 0*2^3 + 1*2^2 + 1*2^1 + 0*2^0 = 22 in decimal.

The outpost of Iceton stood on the northern edge of the kingdom. It was little more than a scrawny barracks surrounded by a short fence and miles of tundra. Snow fell during most of the year, except in the winter months when it was too cold for snow. Few soldiers were stationed there by choice.

Despite the outpost's persistent recruiting problems, it was absolutely vital to the safety of the kingdom. North of Iceton roamed dangerous snow beasts. The beasts resembled elephant-sized polar bears with sharp antlers. They had nasty tempers and a particular fondness for attacking the kingdom's outposts. Iceton watched for these incoming threats and warned the cities to the south.

Since few pigeon messengers could survive Iceton's wintery conditions, giant fires signaled any impending danger. A fire atop one of Iceton's large signal towers indicated an incoming snow beast. The lack of a fire indicated the comparative safety of frostbite, hypothermia, and tundra goblins. Iceton's neighbor to the south, Garroow, watched for signals of trouble from Iceton and relayed the warning further south.

One day, a Garroow guard noticed a troubling sight: two fires burning on the Iceton signal tower. Being that Garrow's entire platoon was new to the outpost, no one knew what two fires meant. After much discussion, Garroow's commander dispatched a rider to investigate. The unlucky soldier, Mavis Yates, arrived at Iceton a few hours later.

"What news do you bring us from Garroow?" asked Iceton's commander with a note of worry.

"I came to investigate the fires," answered Mavis. "What do they mean?"

Commander Dorn looked confused. "They mean the same thing they always have -- snow beasts are heading toward Garroow."

"Why are there two of them?" asked Mavis.

"There are two snow beasts," answered the commander as though the answer was obvious; which, in retrospect, it was.

Moreover, this confirmation was certainly not worth a two hour trek through the tundra. Mavis, desperately wishing to avoid any future journeys to Iceton, decided to clarify. "And three fires would mean three snow beasts?"

"Well…" stalled the commander, "Three or more. We only have space for three signal fires. If you see three fires, you will have to come investigation. There could be five snow beasts heading in your direction."

Mavis had no intention of repeating this journey. Especially not if there were three or more snow beasts heading toward her.

"Oh, no." Mavis protested. "There has to be a better way."

Commander Dorn shook his head. "I assure you that this is how we have communicated for the last ten years. It is quite effective. We only see packs of more than two snow beasts a few times a year."

Mavis shivered involuntarily. "We can do better with three fires. Why not use binary?"

"Binary?" asked the commander.

"Binary," confirmed Mavis. "Each signal fire can indicate a power of two."

"Power of two?

"From East to West they will represent powers of 0, 1, and 2. That is 2^0=1, then 2^1=2, and then 2^2=4. We can encode a lot more information that way."

"That will only tell you that there are 1, 2, or 4 snow beasts coming. How does that help?" protested the commander.

"You add the digits that have fires," explained Mavis. "Let's say the first and last fires are lit. That means there are 1 + 4 = 5 snow beasts."

Mavis walked to the wall, grabbed her hunting knife, and began to carve the following code into the wall:

NO-FIRE, NO-FIRE, NO-FIRE = 0 snow beasts

NO-FIRE, NO-FIRE, FIRE = 1 snow beasts

NO-FIRE, FIRE, NO-FIRE = 2 snow beasts

NO-FIRE, FIRE, FIRE = 3 snow beasts

FIRE, NO-FIRE, NO-FIRE = 4 snow beasts

FIRE, NO-FIRE, FIRE = 5 snow beasts

FIRE, FIRE, NO-FIRE = 6 snow beasts

FIRE, FIRE, FIRE = 7 snow beasts

She stepped back and examined her work.

"Binary," she stated.

The commander stared at the code. "I think it will work," he remarked finally.

"What happens if there are eight snow beasts?" asked one of the commander's aids. "Should someone from Garroow come and investigate?"

"I do not think it is worth worrying about that," the commander answered without looking away from the wall. Mavis smiled. She had found a way to avoid future treks altogether.

"After six, it does not matter much," continued the commander. "When there are that many, they skip Iceton and head straight for Garroow. It is not worth their trouble here. And all that Garroow can do is warn the other cities and flee south."

Mavis's smile vanished. "Wait… what?" she asked.

"Oh… right… you are from Garroow." responded the commander. "Umm.. Good luck with that."

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

To learn more about binary, also read Unhappy Magic Flowers and Binary. Or read about Ann's visit to Garroow in The Important of Variable Names.

The Ant and the Grasshopper: A Fable of Algorithms

An algorithm is a set of specific steps or instructions for solving a problem.

One summer day a grasshopper came upon an ant who was collecting grain. The grasshopper watched as the ant struggled to remove a kernel from a fallen stalk. After a few minutes, the grasshopper spoke.

"Little ant, what are you doing?" the grasshopper asked.

"Collecting food for the winter," responded the ant in a weary voice. He was exhausted from a day of hard labor.

"But it is the middle of the summer," said the grasshopper. "Winter is not for months, and the food is plentiful. Why do you spend your day like this?"

The ant paused for a moment while he thought. "It is the algorithm that we use," he finally replied.

"Algorithm?" asked the grasshopper.

"A set of steps or instructions for accomplishing a task," explained the ant. "Like when a carpenter builds a chair, he uses an algorithm that includes measuring, cutting, smoothing, and hammering."

"What task does your algorithm solve?" asked the grasshopper. "Does it solve the problem of having too much time during the summer?" He chuckled out loud at his own joke.

"It accomplishes the task of keeping the colony healthy all year round. Everyday we have a set of tasks that we perform. During the summer we spend the mornings collecting food, the afternoons digging tunnels, and the nights sleeping. It might not sound like much, but it ensures that we have food during the cold of the winter."

"That sounds like a simple algorithm," remarked the grasshopper.

"Algorithms can be simple or complex," explained the ant. "They can even include steps that require other algorithms to solve. For example, when I collect food, I use a special food collection algorithm. It has five steps: 1) walk to the field, 2) search for a wheat stalk with grain on it, 3) remove a kernel of grain from the stalk, 4) carry the grain back to the ant hill, and 5) place the grain in the storage tunnel. I follow those exact steps to collect a giant pile of grain."

"That sounds boring," said grasshopper. "I do not use algorithms. I just do whatever I want, whenever I want. Complete freedom. In fact, I think I am going to climb to the top of the wheat stalk and sing for a while. I bet your algorithm does not let you do that."

The ant shrugged in response. He had his algorithm, and thus his next steps. It had worked for his colony for hundreds of years. While the grasshopper jumped away singing, the ant returned to his task.

Epiloge:

Six months later, a harsh winter engulfed the land. The grasshopper scavenged the, now bare, wheat field for food. There was not a single kernel to be found.

At the same time, the ant was safe and warm in his colony's tunnels. He was hard at work following his winter day algorithm, which consisted of: digging tunnels, eating, and relaxing. He greatly preferred the winter algorithm to the summer one. As he worked on extended the eastern food tunnel, he paused and thought back to the grasshopper. He wondered if the grasshopper was still spending his days singing in the wheat fields or whether he had learned the value of a good algorithm.

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

To learn more about the computational ingenuity of ants read: The Tortoise, the Hare, and 50000 Ants.

Or see the full list of stories here.