Jeremy Kubica - Computational Fairy Tales

Copyright

Copyright 2012 Jeremy Kubica

All rights reserved.

Print version ISBN: 1477550291

Print version ISBN-13: 978-1477550298

Version 1.1, revised July 4, 2012

Cover design and art by Meagan OBrien

Interior design by Marjorie Carlson

Dedication

To my family

A Note to Readers

This book focuses on computational thinking. The stories are written to introduce and illustrate computational concepts. As such, they focus on high-level concepts, the motivation behind them, and their application in a non-computer domain. These stories are not meant as a substitute for a solid technical description of computer science. Instead, these stories are meant to be used like illustrations, supplementing the full concept.

The book covers a range of material, from introductory programming through more advanced algorithmic concepts. The stories are organized into sections by concept. Each section covers progressively more advanced concepts.

Finally, each story is meant to (approximately) stand alone. While most of the stories follow Anns quest to save the kingdom, there are multiple side stories that are disjoint from the main thread. All of these stories take place in the same kingdom.

Major Characters

Ann is the teenage daughter of King Fredrick and heir to the throne. She has been tasked by the prophets with rescuing the kingdom from the coming darkness. Unfortunately, the prophecy was very vague about the specific threat facing the kingdom.

King Fredrick is the king and Anns father. He is a wise, fair, and occasionally lazy ruler.

Marcus is a powerful wizard and staunch friend of the kings. He is a firm believer in the importance of the practical aspects of magic, such as testing and commenting.

Clare OConnell is the kingdoms brightest computational theorist. She spends her days working at the Bureau of Farm Animal Accounting: Large Mammal Division, where she has assembled a talented team of theorists.

Peter is an apprentice at the Library of Alexandria and an eager, though occasionally arrogant, student of computational ideas.

Sir Galwin is the kings trusted head knight. He has years of experience with difficult quests.

THE START OF A QUEST

The Darkness is Coming

The darkness is coming, stated the seer.

He was the fifteenth seer to stand in front of King Fredrick this week. Fifteen seersall with the same prophecy. Darkness. Chaos. Doom.

Granted, each seer brought his or her own twist to the prophecy. One spoke of ill winds and added a small shiver for effect. Another shouted loudly about the end of times until he was forcibly removed from the room. A third gave the prophecy as a malformed limerick, causing everyone in the room to wince at each attempted rhyme.

In contrast, this seer was much less dramatic; he was calm and to the point. Princess Ann liked that. She had never been a fan of unnecessary theatrics, especially in prophecies.

Of course, Ann didnt care for the message itself. Why did the kingdom have to be doomed? Things were going really well for her. Now some horrid darkness was going to consume the lands.

As her father began to cross-examine the seer, Ann idly wondered how many seers were left today. She tired of the constant proclamations of doom. Why not intersperse a minstrel or two? Anything to lighten the mood would be welcome.

Ann? asked King Fredrick in a loud voice. He stared at her. Ann realized that he was waiting for an answer, but she had no idea what the question had been. She had stopped paying attention after the initial prophecy.

Im sorry. What was the question? she asked.

Ann heard a few surprised gasps from the back of the room. Her father sighed and looked at her crossly.

Will you take on this quest? Will you go forth and save the kingdom? he asked.

Ann froze. What quest? Why her? And why was Sir Galwin, the lands most famous knight, glaring at her? He should be beaming at the mere mention of a quest. He loved quests.

What quest? Ann asked.

To travel forth and find a way to stop the darkness, responded her father. He spoke slowly, as though to ensure Ann was paying attention. It reminded Ann of how he ordered his breakfast in the morningher father left no room for misunderstanding in some aspects of life.

Ann rather liked the suggestion of a quest. She longed to travel the kingdom, but had never been allowed. With the summer holidays starting next week, this quest sounded like a wonderful opportunity. She might get to see the famed upside-down pyramids of South Patagonia or the great Library of Alexandria. Her father even supported it.

Sure. I can do that, she answered quickly.

It will be a long, lonely, and dangerous journey, her father added. But you must find a way to save the kingdom and hold back the darkness. The prophecies have said you must travel forth alone to find the answer.

Wait, what? Alone? sputtered Ann. They never assigned solitary quests to teenagers. Usually a first quest involved a whole platoon of veteran knights. She didnt know the first thing about questing.

Her father sighed again. Did you listen to any of the prophecy at all?

No, Ann admitted. I stopped listening when he reached the you-are-all-doomed part. Ive heard that a hundred times already. It gets boring.

Everyone in the room stared incredulously at her. She started to feel uncomfortable. She briefly wondered if she could somehow escape.

I see, her father began. In short, the seer said that you can save the lands. You need to go find a way to stop the darkness, or we are all doomed. Then he said something about Fortran being the one true language. Honestly, from that point on it was incoherent.

But alone? asked Ann.

Her father gave her a serious look. Alone.

Ann nodded numbly, and again wished that she could run out of the room.

After that, there might have been more said. There might have been cheers or mumbled messages of luck. Her father might have given words of encouragement. The seer might have provided more information. However, Ann didnt hear anything else. The entire room faded from her mind as her new responsibility dawned on her.

* * *

Computer science is inherently a way of thinking about problems. How can you route pieces of information across a distributed network that spans the globe? How can you render pictures that look more realistic? How can I get this stupid program to stop crashing?

The answers to these questions build on a set of core conceptsapproaches to solving fundamental problems in computer science. This book focuses on these core concepts, the problems they address, and how the concepts can be combined to solve even larger and more complex problems.

An Algorithm for Quests

An algorithm is a set of specific steps or instructions for solving a problem. For example, there are algorithms to sort numbers, compute mathematical results, and render images.

* * *

Ann started to panic as she packed for her quest. How was she going to find the answer and save the kingdom? She rarely traveled out of the capital city, and even then she had never gone beyond Millington. Now she had to search all the known lands for a way to save the kingdom. It quickly dawned on her that she had no idea what she was doing.

Her thoughts were interrupted by a sharp knock on the door. Sir Galwin stood rigidly at the entryway, looking mildly uncomfortable.

Sir Galwin, Ann greeted him cautiously. He had been sulking since Ann had received her quest, and she was afraid of setting him off again.