tag:blogger.com,1999:blog-72119483340626649632024-03-05T05:14:28.877-05:00Computational Fairy TalesComputer science concepts as told through fairy tales.<br>
By Jeremy KubicaJeremy Kubicahttp://www.blogger.com/profile/02057783753310151192noreply@blogger.comBlogger85125tag:blogger.com,1999:blog-7211948334062664963.post-13277619569004329612017-12-30T09:18:00.001-05:002017-12-30T09:18:46.911-05:00Singing with Loops<b>Loops are programming constructs for repeating a set of instructions until a given termination a criterion is met.</b><br />
<br />
Ann cheered at the sight of the brightly lit inn. A sign by the door read, “One night only! The world famous bard Larry de Loop!” After another full day of walking, she felt tired and seemed no closer to finishing her quest. But, at least, she’d found a place to rest. And some cheerful music might help take her mind off her quest.<br />
<br />
Ann chose a small table by the stage. After ordering a bowl of Surprise Stew, regrettably the only item on the menu, she settled in for the show.<br />
<br />
Though unable to play even a basic tune on his accordion, Larry de Loop was the most enthusiastic bard Ann had seen. He belted out three simple songs, then asked for requests.<br />
<br />
“The Ballad of Lady Algorithm,” called Ann, wanting to hear the tale of her favorite adventurer.<br />
<br />
Larry looked surprised. “I’m sorry miss. I only sing songs in loop form.”<br />
<br />
“Loop form?” Ann asked. “I’ve never heard of that style of music.”<br />
<br />
“It’s quite popular in the North. The songs have to use either FOR loops or WHILE loops. Loops are constructs for repeating things until some conditions are met.”<br />
<br />
“What?” asked Ann. Naturally she was familiar with the concept of loops. They were a basic building block of algorithms. She used loops in archery (<i>while</i> you have arrows, shoot at the target), cooking (stir <i>for</i> two minutes), counting coins (<i>for</i> each coin, add its value to the total), and even walking (<i>while</i> I’m not there yet, take another step). But she’d never heard of loop-based music.<br />
<br />
“I mostly sing in FOR loops,” explained Larry. “A FOR loop iterates over a set number of things. 99 Bottles of Beer on the Wall uses a FOR loop. FOR each number of bottles from 99 down to 1, sing a verse. Or perhaps you’ve heard of old McDonald’s Farm? FOR each animal on the farm, sing about the cute noises it makes. Or—“<br />
<br />
“Aren’t those songs all quite repetitive?” Ann interrupted. Of course, repetition was precisely the function of a loop.<br />
<br />
Larry smiled broadly. “That’s why I also use a WHILE loop. WHILE loops repeat a set of actions until a condition is met. In my case I always use the same loop: WHILE no one has thrown a tomato at me, keep singing. So once the first tomato is thrown, I know it's time to stop.”<br />
<div>
<br /></div>
<div class="blogger-post-footer">Copyright Jeremy Kubica 2011</div>Jeremy Kubicahttp://www.blogger.com/profile/02057783753310151192noreply@blogger.com0tag:blogger.com,1999:blog-7211948334062664963.post-58280424552670279482017-12-21T10:19:00.000-05:002017-12-21T10:22:39.864-05:00Variables, IF statements, and Magic Boots<div>
<b>A variable represents a location in the computer’s memory where you can store a single piece of data. You can use the variable’s name to look up, set, or modify the value stored in that location.</b></div>
<div>
<br /></div>
<div>
Ann jolted in surprise as a loud tone cut through the silence. She quickly tapped her boots together, resetting them before they could blare their pre-recorded message. She mumbled a few insults at her footwear. Did they have to alert her after every mile?</div>
<div>
<br /></div>
<div>
Ann realized this was the eighth warning chime today. Had she walked eight miles already? She’d been so lost in her thoughts, that she hadn’t been paying much attention to the journey itself. She was now three days into her quest to save the kingdom and she still had no idea what to do. Why couldn’t the seers have been more specific than, “There is a darkness coming. Princess Ann must travel forth alone to save the kingdom.” Maybe they could have told her what the darkness was or, at least, hinted at which direction to travel. Stupid vague prophecies.</div>
<div>
<br /></div>
<div>
Ann looked down at her boots and debated for the hundredth time whether they were worth the annoyance. The boots had been a birthday gift from Marcus, the royal wizard. They represented his first foray into variable magic—a form of magic that allowed an object to store a single piece of information. In this case, her boots’ variable (helpfully called dist) stored the distance she traveled. After each step, dist increased by the length of the step.</div>
<div>
<br /></div>
<div>
<span style="font-family: "courier new" , "courier" , monospace;">dist = dist + step_length</span></div>
<div>
<br /></div>
<div>
Initially the boots had provided wonderful entertainment. Ann measured everything. She measured the length and width of her room, the distance to the kitchen, the distance to all ten of the castle’s bathrooms, the circumference of the castle wall, and the diameter of Fido’s turtle pond (the boots were, of course, water proof). She’d even annoyed the castle architect by noting the courtyard was six inches shorter than advertised.</div>
<div>
<br /></div>
<div>
After every trip she’d read the variable’s value from her left heel. Then she’d click the heels together to set the distance back to zero.</div>
<div>
<br /></div>
<div>
<span style="font-family: "courier new" , "courier" , monospace;">IF heels clicked: set dist = 0</span></div>
<div>
<br /></div>
<div>
If she also used her watch to track the time, she could even compute her speed:</div>
<div>
<br /></div>
<div>
<span style="font-family: "courier new" , "courier" , monospace;">Average speed = dist / time</span></div>
<div>
<br /></div>
<div>
Variable magic provides such wonderful power.</div>
<div>
<br /></div>
<div>
Unfortunately, Marcus had gone overboard. In addition to the variable itself, he added his own IF-statement based enhancements. After walking a mile the boots would loudly recommend that she take a break:</div>
<div>
<br /></div>
<div>
<span style="font-family: "courier new" , "courier" , monospace;">IF dist > 1 mile: Alert the wearer to take a break</span></div>
<div>
<br /></div>
<div>
The message, which sounded like the castle herald with hiccups, grated on her nerves. Worse, Marcus hadn’t properly thought through the details of his IF statement. The statement only checked if dist was greater than a mile. So once she’d walked a mile, the boots would “helpfully” alert her to this fact after every single step. Ann quickly learned to reset the distance to zero the moment she heard the chime.</div>
<div>
<br /></div>
<div>
With a sigh, Ann decided to leave on the boots. While they were extremely annoying, at least they tracked useful information. Marcus had once confided that his original design enabled the boots to track their smelliness. She shuddered as she considered what that alert might say.<br />
<br />
-------------<br />
<br />
There are now <b>three</b> books out in the Computational Fairy Tales universe! See the <a href="http://computationaltales.blogspot.com/p/book.html">books page</a> for more information.</div>
<div class="blogger-post-footer">Copyright Jeremy Kubica 2011</div>Jeremy Kubicahttp://www.blogger.com/profile/02057783753310151192noreply@blogger.com0tag:blogger.com,1999:blog-7211948334062664963.post-936450035489181262015-10-04T16:56:00.000-04:002015-10-04T16:59:17.853-04:00Encodings for Tic-Tac-Toe<div style="background-color: white; color: #222222; font-family: arial, sans-serif;">
Peter hurried back to the Library of Alexandria, the message clutched tightly in his fist. He resisted the urge to study the parchment, reading it again wouldn’t help. The message was obviously some form of code, and he had memorized the whole thing in his first glance. The entire message read “23G.” Although he didn’t know what those few characters meant, Peter was certain they were important.</div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif;">
<br /></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif;">
“You received a message,” he called out the moment he entered the library. Half a dozen startled patrons glared at him from their tables. Flushing with embarrassment at his outburst, Peter quietly strode to the main circulation desk.</div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif;">
<br /></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif;">
“You have a message,” he whispered to the head librarian, holding out the parchment.</div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif;">
<br /></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif;">
The elder librarian took the message and read it carefully. After a moment he nodded a few times, saying only, “Interesting.”</div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif;">
<br /></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif;">
“What is it? It is it important?” Peter asked impatiently.</div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif;">
<br /></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif;">
The librarian looked surprised. “What gave you that impression?”</div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif;">
<br /></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif;">
“It’s a code, isn’t it?” answered Peter. “And it came through the wizard’s telegraph office, which must mean it’s important.”</div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif;">
<br /></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif;">
The librarian chuckled softly before explaining, “It’s a move in a game called Tic-Tac-Toe. I’ve been playing with the librarian from G’Raph. She’s quite skilled at strategy.”</div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif;">
<br /></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif;">
“What?”</div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif;">
<br /></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif;">
“Tic-Tac-Toe. It’s a simple game, but most enjoyable,” started the librarian. “It’s a two player game that is played on a three by three grid, where—”</div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif;">
<br /></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif;">
“I know what Tic-Tac-Toe is,” cut in Peter. “But how does ‘23G’ represent a move in Tic-Tac-Toe?”</div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif;">
<br /></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif;">
“Ah. I see where you’re confused. We had to invent an encoding scheme that allows us to play over pigeon message or magical telegraph. It’s really quite a simple scheme. The first number represents the row, the second number represents the column, and the last letter indicates who made the move. We need that last one so we can play different games against other librarians. I’m currently winning two of my three games.” As he spoke, he pulled a few pieces of parchment from under the desk. On the one labeled G’Raph, he carefully marked an X in the third column of the second row.</div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif;">
<br /></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif;">
“But why three letters? Why not just draw out the whole board and pass that back and forth?”</div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif;">
<br /></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif;">
The librarian smiled. “Our encoding makes for a convenient abstraction. We can send those letters by pigeon message, magical telegraph, or even by magical mirrors without needing to change the encoding. Each of those communication mediums uses its own underlying encoding to transmit letters. Pigeon messages rely on written letters, which are really just lines of ink on parchment. The magical telegraph uses a new form of dots and dashes to encode each letter. I have no idea what encoding the magical mirrors use. I think it has something to do with pastel colors. But it doesn’t matter. Regardless of the underlying encoding used to store and transmit the message, we only need to worry about encoding it as letters.”</div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif;">
<br /></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif;">
“You go through all of that for a game of tic-tac-toe?” asked Peter.</div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif;">
<br /></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif;">
“Tic-Tac-Toe is more than just a game,” said the librarian. “It is the ultimate test of strategy. It is a window into a person’s inner-most thinking.”</div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif;">
<br /></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif;">
Peter stared at him in disbelief.</div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif;">
<br /></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif;">
“Now if you’ll excuse me,” continued the librarian, “I have to plan my next move.”</div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif;">
<br /></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif;">
<br /></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif;">
Three days later Peter stumbled into the library, looking as though he hadn’t slept in about three days. He walked up to the main counter and stood there silently, beaming at the librarian.</div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif;">
<br /></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif;">
“Are you okay?” asked the librarian.</div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif;">
<br /></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif;">
“I did it!” Peter practically shouted with glee.</div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif;">
<br /></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif;">
“Did what?” asked the librarian, now thoroughly worried.</div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif;">
<br /></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif;">
Peter’s smile grew even wider. “I created a new encoding for the library!” He waited for the librarian’s gasp of excitement. When the librarian’s face remained blank, Peter added, “An encoding… like for your game of tic-tac-toe.”</div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif;">
<br /></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif;">
“I see. And what’s it for?” asked the librarian.</div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif;">
<br /></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif;">
“Books and scrolls!” Peter opened his arms expansively to indicate the contents of the library.</div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif;">
<br /></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif;">
The librarian considered this for a moment. Carefully he said, “We have an encoding system for books and scrolls. It’s called letters. You use them to form words and… you know, encode knowledge.”</div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif;">
<br /></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif;">
“No. I don’t mean for the content of the scrolls. I mean for the topics,” Peter explained. “I have developed a new system that gives each subject a unique code of three numbers in the range 0 to 255 that represent the category, subcategory, and specialization. So we can encode the contents of any scroll, book, or loose parchment with a three number code.”</div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif;">
<br /></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif;">
“Consider this scroll,” Peter continued, picking a scroll from the return bin. “The subject code is 192.168.1, which translates to the communication category (192), the networking subcategory (168), and the specialization of pigeon networks (1).</div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif;">
<br /></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif;">
“And, like your Tic-Tac-Toe encoding, the subject encoding can be transmitted easily. We can share the encoding with other libraries and use it to request resources. If I wanted a book on ancient history (category 0), of the kingdom (subcategory 0), and the development of new eating utensils (specialty 10), I could send a pigeon message to a library in G’Raph simply stating ‘Request: 0.0.10. Alexandria.’ You see?”</div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif;">
<br /></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif;">
The librarian thought about the scheme for a minute. “I suppose it could work,” he admitted. “But it’s no where near as exciting as exchanging moves in a game like Tic-Tac-Toe. Leave it to you to make encodings so… practical.”</div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif;">
<br /></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif;">
<span style="color: black; font-family: Arial, Helvetica, sans-serif;">--------------------------</span></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif;">
<span style="color: black; font-family: Arial, Helvetica, sans-serif;"><br /></span></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif;">
<span style="color: black; font-family: Arial, Helvetica, sans-serif;">Thank you to Caroline Meeks for suggesting the topic of encodings.</span></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif;">
<span style="color: black; font-family: Arial, Helvetica, sans-serif;"><br /></span></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif;">
<span style="color: black; font-family: Arial, Helvetica, sans-serif;">Interested in lower level codings? Learn about binary with <a href="http://computationaltales.blogspot.com/2011/06/unhappy-magic-flowers-and-binary.html">Unhappy Flowers and Binary</a> or <a href="http://computationaltales.blogspot.com/2012/01/using-binary-to-warn-of-snow-beasts.html">Using Binary to Warn of Snow Beasts</a>.</span></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif;">
<span style="color: black; font-family: Arial, Helvetica, sans-serif;"><br /></span></div>
<div class="blogger-post-footer">Copyright Jeremy Kubica 2011</div>Jeremy Kubicahttp://www.blogger.com/profile/02057783753310151192noreply@blogger.com0tag:blogger.com,1999:blog-7211948334062664963.post-59007654420751535502013-01-21T18:44:00.001-05:002013-01-24T22:41:59.418-05:00Best Practices of Spell Design<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiG2YsEn4S8XVvjWhT3chN7jmlMdtLAKkOfobqQybMKJ_rOmkwuhEjxzYOp1V-Iz6_6XKpF02Hrof8lpkBQzd71i1IM-doS0hjrS4SY93HSB3i7K3HKrGVi1xtultcue3rnR9yvkOb6-Zc/s1600/BestPractices.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiG2YsEn4S8XVvjWhT3chN7jmlMdtLAKkOfobqQybMKJ_rOmkwuhEjxzYOp1V-Iz6_6XKpF02Hrof8lpkBQzd71i1IM-doS0hjrS4SY93HSB3i7K3HKrGVi1xtultcue3rnR9yvkOb6-Zc/s1600/BestPractices.jpg" /></a></div>
<br />
<br />
<b>The <a href="http://computationaltales.blogspot.com/p/book.html#BestPractices">Best Practices of Spell Design book</a> is available! The second book in the Computational Fairy Tales universe introduces the programing and software engineering best practices.</b><br />
<br />
In all his years as a wizard, Marcus has never seen a spell cause this much damage. When Hannaldous's sloppy attempt at a shield spell accidentally curses the castle, the walls start crumbling at an alarming rate. Now Marcus and his apprentice Shelly must figure out how to repair the damage before the castle turns to dust. Along the way they will encounter gossiping worms, perfectionist bakers, opportunistic rabbits, and copious amounts of mold.<br />
<br />
The Best Practices of Spell Design introduces practical aspects of software development that are often learned through painful experience. Through Marcus and Shelly’s quest, the story encourages readers to think about how to write readable, well-tested and maintainable programs. Readers will discover the importance of comments in recipes, the value of testing potions, the dangers of poorly named ingredients, the wonders of code reviews in magic libraries, and the perils of premature optimization.<br />
<br />
For more information, including links to online stores, visit the <a href="http://computationaltales.blogspot.com/p/book.html#BestPractices">books page</a>. Or<br />
<br />
<ul>
<li><a href="http://www.amazon.com/Practices-Spell-Design-Jeremy-Kubica/dp/1481921916">Buy the print version at Amazon</a></li>
<li><a href="https://www.createspace.com/4122588">Buy the print version at Create Space</a></li>
<li><a href="http://www.amazon.com/Best-Practices-Spell-Design-ebook/dp/B00B5CVXSU">Buy on the Kindle</a></li>
<li><a href="http://www.lulu.com/shop/jeremy-kubica/best-practices-of-spell-design/ebook/product-20655921.html">Buy the ePub on Lulu</a></li>
</ul>
Nook, iBooks, and Google Play coming soon.<br />
<br />
<br />
<b>FAQs:</b><br />
<b>Q: Is this a print copy of your blog? Why should I buy the book?</b><br />
A: Best Practices of Spell Design consists of almost all new content. A few related blog posts have been included (after significant professional editing).<br />
<br />
<b>Q: Is the format of Best Practices in Spell Design the same as Computational Fairy Tales?</b><br />
A:The format is similar, but not identical. Instead of individual stories with introductory technical blurbs, Best Practices of Spell design is written as a novella. Each chapter of the story introduces, explains, or reinforces a concept.<br />
<br />
<b>Q: What is the target audience for this book?</b><br />
A: Best Practices of Spell Design is written for people who are just starting to program or have some programming experience. The book does not teach programming, but rather reinforces important programming best practices that are often learned through (painful) experience.<br />
<br />
Also see <a href="http://computationaltales.blogspot.com/2012/08/who-is-target-audience.html">Who is the Target Audience?</a> for more details on the audience for Computational Fairy Tales stories.<div class="blogger-post-footer">Copyright Jeremy Kubica 2011</div>Jeremy Kubicahttp://www.blogger.com/profile/02057783753310151192noreply@blogger.com3tag:blogger.com,1999:blog-7211948334062664963.post-61128936434482370562012-08-09T20:01:00.002-04:002012-08-09T20:05:27.607-04:00Who is the target audience?<div><span style="font-family:Georgia, serif;">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.</span></div><div><span style="font-family: Georgia, serif; "><br /></span></div><div><span style="font-family: Georgia, serif; ">To be honest, these are questions that I asked myself many times when I was starting.</span></div><div><span style="font-family:Georgia, serif;"><br /></span></div><div><span style="font-family:Georgia, serif;">Below I outline some of the thought process behind the stories, the book, and how they can be used.</span></div><div><span style="font-family:Georgia, serif;"><br /></span></div><div><span style="font-family:Georgia, serif;"><b>Computational Fairy Tales is not a textbook:</b></span></div><div><span style="font-family:Georgia, serif;">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.</span></div><div><span style="font-family:Georgia, serif;"><br /></span></div><div><span style="font-family:Georgia, serif;"><b>Motivating computational thinking:</b></span></div><div><span style="font-family:Georgia, serif;">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.</span></div><div><span style="font-family:Georgia, serif;"><br /></span></div><div><span style="font-family:Georgia, serif;"><b>Using Computational Fairy Tales in a class:</b></span></div><div><span style="font-family:Georgia, serif;">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:</span></div><div><ol><li><span style="font-family: Georgia, serif; ">Introduce the concept.</span></li><li><span style="font-family: Georgia, serif; ">Use the story to motivate it or put a new spin on it.</span></li><li><span style="font-family: Georgia, serif; ">Go into more details, possibly involving real code or formal proofs.</span></li><li><span style="font-family: Georgia, serif; ">Assign copious amounts of homework on the topic.</span></li></ol></div><div><span style="font-family:Georgia, serif;">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.</span></div><div><span style="font-family:Georgia, serif;"><br /></span></div><div><span style="font-family:Georgia, serif;"><b>Suggestions? Comments?</b></span></div><div><span style="font-family:Georgia, serif;">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.</span></div><div class="blogger-post-footer">Copyright Jeremy Kubica 2011</div>Jeremy Kubicahttp://www.blogger.com/profile/02057783753310151192noreply@blogger.com0tag:blogger.com,1999:blog-7211948334062664963.post-7925834142084973532012-06-26T20:19:00.010-04:002012-07-09T23:16:17.491-04:00Book (and FAQs)<span style="font-family: Georgia, serif; font-style: normal; font-variant: normal; line-height: normal; font-family:arial;font-size:130%;"><b>The Computational Fairy Tales book is available (in print and on the Kindle). More details can be found at <a href="http://computationaltales.blogspot.com/p/book.html">the book page</a>, including links to the various stores.</b></span><div style="font-weight: normal; font-size:100%;"><div style="text-align: -webkit-auto;"><span style="line-height: 18px;font-family:Georgia, serif;color:#222222;"><br /></span></div><div style="text-align: -webkit-auto;"><span style="font-family:Georgia, serif;color:#222222;"><span style="line-height: 18px;"><div>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.</div><div><br /></div><div><a href="http://computationaltales.blogspot.com/p/book.html">Go to the book page</a>.</div><div><br /></div><div>A few FAQs:</div><div><br /></div><div><b>Q: Is this a print copy of your blog? Why should I buy the book?</b></div><div>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.</div><div><br /></div><div><b>Q: What is the target audience for this book?</b></div><div>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.</div><div><br /></div><div><b>Q: My favorite story is not there! What's the deal?</b></div><div>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.</div><div><br /></div><div><b>Q: Does this mean that the online collection is going away?</b></div><div>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.</div></span></span></div><div style="font-family: Georgia, serif; font-size: 100%; font-style: normal; font-variant: normal; font-weight: normal; line-height: normal; "><div style="font-family: Georgia, serif; font-size: 100%; font-style: normal; font-variant: normal; font-weight: normal; line-height: normal; "><br /></div></div></div><div class="blogger-post-footer">Copyright Jeremy Kubica 2011</div>Jeremy Kubicahttp://www.blogger.com/profile/02057783753310151192noreply@blogger.com1tag:blogger.com,1999:blog-7211948334062664963.post-66224898613719432272012-05-10T19:56:00.001-04:002012-05-10T20:01:44.335-04:00The Importance of Design in Five Course Meals<br />
<span style="font-family: 'Courier New', Courier, monospace;"><b>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.</b></span><br />
<br />
<span style="font-family: Arial, Helvetica, sans-serif;">"I can fix this," Chef Pepperton said to himself as he rummaged through a box of fresh vegetables. "I just need some radishes."</span><br />
<br />
<span style="font-family: Arial, Helvetica, sans-serif;">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.</span><br />
<br />
<span style="font-family: Arial, Helvetica, sans-serif;">"Radishes?!?" screamed Chef Pepperton. "Do we have any radishes?"</span><br />
<br />
<span style="font-family: Arial, Helvetica, sans-serif;">One of the other chefs paused for a moment in thought. "No," he said.</span><br />
<br />
<span style="font-family: Arial, Helvetica, sans-serif;">Pepperton turned back to the box. "I can fix this," he mumbled. "Carrots. I can do it with carrots."</span><br />
<br />
<span style="font-family: Arial, Helvetica, sans-serif;">Then he loudly announced, "We are changing the menu to carrot ravioli. CARROT RAVIOLI."</span><br />
<br />
<span style="font-family: Arial, Helvetica, sans-serif;">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.</span><br />
<br />
<span style="font-family: Arial, Helvetica, sans-serif;">"How is the appetizer coming?" Pepperton asked.</span><br />
<br />
<span style="font-family: Arial, Helvetica, sans-serif;">"A little burnt, but we can peel off the worst bits," answered his assistant.</span><br />
<br />
<span style="font-family: Arial, Helvetica, sans-serif;">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.</span><br />
<br />
<span style="font-family: Arial, Helvetica, sans-serif;">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."</span><br />
<br />
<span style="font-family: Arial, Helvetica, sans-serif;">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."</span><br />
<br />
<span style="font-family: Arial, Helvetica, sans-serif;">"If we do ravioli, we need another burner," noted his assistant. "Something else will have to come off."</span><br />
<br />
<span style="font-family: Arial, Helvetica, sans-serif;">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.</span><br />
<br />
<span style="font-family: Arial, Helvetica, sans-serif;">"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."</span><br />
<br />
<span style="font-family: Arial, Helvetica, sans-serif;">"I need the fire for the salad," protested the assistant.</span><br />
<br />
<span style="font-family: Arial, Helvetica, sans-serif;">"Make it a cold salad," ordered Pepperton. "And where is the salt?"</span><br />
<br />
<span style="font-family: Arial, Helvetica, sans-serif;">"Over here," called the dessert chef.</span><br />
<br />
<span style="font-family: Arial, Helvetica, sans-serif;">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.</span><br />
<br />
<span style="font-family: Arial, Helvetica, sans-serif;">"And the radishes?" asked Pepperton.</span><br />
<br />
<span style="font-family: Arial, Helvetica, sans-serif;">"You switched to carrots," reminded the assistant.</span><br />
<br />
<span style="font-family: Arial, Helvetica, sans-serif;">"Hold on a second," said Pepperton. "I think I might need to write this down."</span><br />
<br />
<span style="font-family: Arial, Helvetica, sans-serif;">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.</span><br />
<br />
<span style="font-family: Arial, Helvetica, sans-serif;">He was halfway through finally writing down a menu when his assistant interrupted him. "Chef, your carrots are burning."</span><br />
<br />
<span style="font-family: Arial, Helvetica, sans-serif;">Pepperton groaned and crossed "Carrot Ravioli" off his menu.</span><br />
<br />
<span style="font-family: Arial, Helvetica, sans-serif;">--------------------------</span><br />
<br />
<span style="font-family: Arial, Helvetica, sans-serif;">Want to read more about programming and kitchens? See <a href="http://computationaltales.blogspot.com/2011/06/variable-initialization-in-busy.html">Variable Initialization in Busy Kitchens</a> or <a href="http://computationaltales.blogspot.com/2011/03/computer-memory-and-making-dinner.html">Computer Memory and Making Dinner</a>.</span><br />
<br />
<span style="font-family: Arial, Helvetica, sans-serif;"><u>Book update</u>: The second draft of the book is complete. It includes 30 revised stories and 15 new stories. Story list coming soon.</span><br />
<br />
<br /><div class="blogger-post-footer">Copyright Jeremy Kubica 2011</div>Jeremy Kubicahttp://www.blogger.com/profile/02057783753310151192noreply@blogger.com0tag:blogger.com,1999:blog-7211948334062664963.post-22923531348275922142012-02-26T12:47:00.007-05:002012-02-28T20:51:08.845-05:00Enums and Hair Colors<div><div><span><b>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).</b></span></div><div style="font-family: Georgia, serif; "><br /></div><div><span>"It is blue!" wailed a lady three chairs over.</span></div><div><span><br /></span></div><div><span>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.</span></div><div><span><br /></span></div><div><span>"I… I…" stammered Derek. He stood behind the blue-haired woman. His face registered a mixture of shock and fear.</span></div><div><span><br /></span></div><div><span>"It is supposed to be blond," screamed the lady. "But it is blue!"</span></div><div><span><br /></span></div><div><span>"I know," said Derek. "It is just that… I thought… Umm... let me go check something."</span></div><div><span><br /></span></div><div><span>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.</span></div><div><span><br /></span></div><div><span>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.</span></div><div><span><br /></span></div><div><span>"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?"</span></div><div><span><br /></span></div><div><span>"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."</span></div><div><span><br /></span></div><div><span>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."</span></div><div><span><br /></span></div><div><span>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."</span></div><div><span><br /></span></div><div><span>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?"</span></div><div><span><br /></span></div><div><span>Angela noticed the Karen had omitted the fact that the ideas also prevented errors. She decided not to press the point.</span></div><div><span><br /></span></div><div><span>"Enums," answered Angela.</span></div><div><span><br /></span></div><div><span>"Enums?" asked Derek.</span></div><div><span><br /></span></div><div><span>Karen squinted in confusion as if wracking her brain.</span></div><div><span><br /></span></div><div><span>"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."</span></div><div><span><br /></span></div><div><span>"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."</span></div><div><span><br /></span></div><div><span>"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."</span></div><div><span><br /></span></div><div><span>Karen was silent for a moment. "What will it cost me?" she asked.</span></div><div><span><br /></span></div><div><span>From outside they heard a loud, tearful scream. "Blue!!!"</span></div><div><span><br /></span></div><div><span>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."</span></div><div><span><br /></span></div><div><span>"BLUE!!!" came another scream.</span></div><div><span><br /></span></div><div><span>"I think it might be worth it though," Angela added.</span></div><div><span><br /></span></div><div><span>-------------------------------</span></div><div><br /></div><div>Thank you to David Karl for recommending the topic of enumerated types!</div><div><br /></div><div><span>Want to learn more about <a href="http://computationaltales.blogspot.com/search/label/Practical%20Programming">practical programming tips</a>? Read about the importance of: <a href="http://computationaltales.blogspot.com/2011/06/variable-initialization-in-busy.html">variable initialization,</a> <a href="http://computationaltales.blogspot.com/2011/05/importance-of-unit-testing-magical.html">unit testing</a>, <a href="http://computationaltales.blogspot.com/2011/09/version-control-in-magic-spell.html">source control</a>, <a href="http://computationaltales.blogspot.com/2011/08/importance-of-good-comments-tale-of.html">comments</a>, or <a href="http://computationaltales.blogspot.com/2011/08/data-validation-marcus-and-cheese.html">data validation</a>.</span></div><div style="font-family: Georgia, serif; "><br /></div></div><div><span><br /></span></div><div class="blogger-post-footer">Copyright Jeremy Kubica 2011</div>Jeremy Kubicahttp://www.blogger.com/profile/02057783753310151192noreply@blogger.com0tag:blogger.com,1999:blog-7211948334062664963.post-46493824379983015472012-01-29T13:00:00.001-05:002012-01-29T13:04:19.171-05:00Classes, Inheritance, and the Three Little Pigs<div><span ><b>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.</b></span></div><div><span ><br /></span></div><div><span >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.</span></div><div><span ><br /></span></div><div><span >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.</span></div><div><span ><br /></span></div><div><span >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.</span></div><div><span ><br /></span></div><div><span >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.</span></div><div><span ><br /></span></div><div><span >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.</span></div><div><span ><br /></span></div><div><span >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.</span></div><div><span ><br /></span></div><div><span >"Little pig, let me in. Or I will huff and puff and blow your house in." threatened the wolf.</span></div><div><span ><br /></span></div><div><span >"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.</span></div><div><span ><br /></span></div><div><span >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.</span></div><div><span ><br /></span></div><div><span >The wolf was in the middle of his first puff when he saw the pig running. He grinned wickedly and gave chase.</span></div><div><span ><br /></span></div><div><span >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.</span></div><div><span ><br /></span></div><div><span >"Wolf… huff… puff…" was all the first pig could get out between his own heavy breadths. It had been a long run uphill.</span></div><div><span ><br /></span></div><div><span >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.</span></div><div><span ><br /></span></div><div><span >"Little pigs, let me in. Or I will huff and puff and blow your house in." threatened the wolf.</span></div><div><span ><br /></span></div><div><span >"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.</span></div><div><span ><br /></span></div><div><span >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.</span></div><div><span ><br /></span></div><div><span >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.</span></div><div><span ><br /></span></div><div><span >"Brother… wolf… huffing…" the two new arrivals panted.</span></div><div><span ><br /></span></div><div><span >The brother looked up and saw the approaching wolf. The three little pigs dashed into the house, threw the deadbolt, and closed the windows.</span></div><div><span ><br /></span></div><div><span >"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.</span></div><div><span ><br /></span></div><div><span >"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."</span></div><div><span ><br /></span></div><div><span >"And the way sound echoes in here is annoying," added the youngest pig. "Have you ever considered putting up some drywall?"</span></div><div><span ><br /></span></div><div><span >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.</span></div><div><span ><br /></span></div><div><span >"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."</span></div><div><span ><br /></span></div><div><span >The other brothers nodded in agreement.</span></div><div><span ><br /></span></div><div><span >Outside they could hear the faint sounds of rushing wind and a hyperventilating wolf.</span></div><div><span ><br /></span></div><div><span >"Could we create a new SecureWoodHouse?" asked the middle brother. He liked the warm feeling of wood paneling.</span></div><div><span ><br /></span></div><div><span >The other two pigs paused in deep thought. "Would we derive it from the WoodHouse?" asked the oldest brother.</span></div><div><span ><br /></span></div><div><span >"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."</span></div><div><span ><br /></span></div><div><span >"Interesting…" said the oldest brother as he thought over the proposal. "What other functions are you thinking about? How about ShutterWindows?"</span></div><div><span ><br /></span></div><div><span >Outside the wolf had huffed and puffed until he had passed out.</span></div><div><span ><br /></span></div><div><span >--------------</span></div><div><span ><br /></span></div><div><span >Interested in learning more about object oriented programming? Read about it Marcus's visit to a cheese factory (<a href="http://computationaltales.blogspot.com/2011/09/objects-encapsulation-and-cheese.html">Objects</a>, <a href="http://computationaltales.blogspot.com/2011/09/classes-of-cheese-part-3-of-marcus-and.html">Classes</a>, and <a href="http://computationaltales.blogspot.com/2011/09/inheritance-in-cheeses-and-magic-spells.html">Inheritance</a>).</span></div><div><span ><br /></span></div><div><span >Interested in computational takes on other classic fairy tales? Read <a href="http://computationaltales.blogspot.com/2011/12/binary-searching-for-cinderella.html">Binary Searching for Cinderella</a> or <a href="http://computationaltales.blogspot.com/2011/12/goldilocks-and-two-boolean-bears.html">Goldilocks and the Boolean Bears</a>.</span></div><div><span ><br /></span></div><div><span >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.</span></div><div><br /></div><div class="blogger-post-footer">Copyright Jeremy Kubica 2011</div>Jeremy Kubicahttp://www.blogger.com/profile/02057783753310151192noreply@blogger.com0tag:blogger.com,1999:blog-7211948334062664963.post-1211818367228440092012-01-24T21:51:00.002-05:002012-01-24T21:54:47.762-05:00Using Binary to Warn of Snow Beasts<div><span ><b>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.</b></span></div><div><span ><br /></span></div><div><span >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.</span></div><div><span ><br /></span></div><div><span >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.</span></div><div><span ><br /></span></div><div><span >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.</span></div><div><span ><br /></span></div><div><span >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.</span></div><div><span ><br /></span></div><div><span >"What news do you bring us from Garroow?" asked Iceton's commander with a note of worry.</span></div><div><span ><br /></span></div><div><span >"I came to investigate the fires," answered Mavis. "What do they mean?"</span></div><div><span ><br /></span></div><div><span >Commander Dorn looked confused. "They mean the same thing they always have -- snow beasts are heading toward Garroow."</span></div><div><span ><br /></span></div><div><span >"Why are there two of them?" asked Mavis.</span></div><div><span ><br /></span></div><div><span >"There are two snow beasts," answered the commander as though the answer was obvious; which, in retrospect, it was.</span></div><div><span ><br /></span></div><div><span >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?"</span></div><div><span ><br /></span></div><div><span >"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."</span></div><div><span ><br /></span></div><div><span >Mavis had no intention of repeating this journey. Especially not if there were three or more snow beasts heading toward her.</span></div><div><span ><br /></span></div><div><span >"Oh, no." Mavis protested. "There has to be a better way."</span></div><div><span ><br /></span></div><div><span >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."</span></div><div><span ><br /></span></div><div><span >Mavis shivered involuntarily. "We can do better with three fires. Why not use binary?"</span></div><div><span ><br /></span></div><div><span >"Binary?" asked the commander.</span></div><div><span ><br /></span></div><div><span >"Binary," confirmed Mavis. "Each signal fire can indicate a power of two."</span></div><div><span ><br /></span></div><div><span >"Power of two?</span></div><div><span ><br /></span></div><div><span >"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."</span></div><div><span ><br /></span></div><div><span >"That will only tell you that there are 1, 2, or 4 snow beasts coming. How does that help?" protested the commander.</span></div><div><span ><br /></span></div><div><span >"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."</span></div><div><span ><br /></span></div><div><span >Mavis walked to the wall, grabbed her hunting knife, and began to carve the following code into the wall:</span></div><div><span >NO-FIRE, NO-FIRE, NO-FIRE = 0 snow beasts</span></div><div><span >NO-FIRE, NO-FIRE, FIRE = 1 snow beasts</span></div><div><span >NO-FIRE, FIRE, NO-FIRE = 2 snow beasts</span></div><div><span >NO-FIRE, FIRE, FIRE = 3 snow beasts</span></div><div><span >FIRE, NO-FIRE, NO-FIRE = 4 snow beasts</span></div><div><span >FIRE, NO-FIRE, FIRE = 5 snow beasts</span></div><div><span >FIRE, FIRE, NO-FIRE = 6 snow beasts</span></div><div><span >FIRE, FIRE, FIRE = 7 snow beasts</span></div><div><span >She stepped back and examined her work.</span></div><div><span ><br /></span></div><div><span >"Binary," she stated. </span></div><div><span ><br /></span></div><div><span >The commander stared at the code. "I think it will work," he remarked finally.</span></div><div><span ><br /></span></div><div><span >"What happens if there are eight snow beasts?" asked one of the commander's aids. "Should someone from Garroow come and investigate?"</span></div><div><span ><br /></span></div><div><span >"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.</span></div><div><span ><br /></span></div><div><span >"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."</span></div><div><span ><br /></span></div><div><span >Mavis's smile vanished. "Wait… what?" she asked.</span></div><div><span ><br /></span></div><div><span >"Oh… right… you are from Garroow." responded the commander. "Umm.. Good luck with that."</span></div><div><span ><br /></span></div><div><span >------------</span></div><div><span ><br /></span></div><div><span >To learn more about binary, also read <a href="http://computationaltales.blogspot.com/2011/06/unhappy-magic-flowers-and-binary.html">Unhappy Magic Flowers and Binary</a>. Or read about Ann's visit to Garroow in <a href="http://computationaltales.blogspot.com/2011/03/importance-of-variable-names.html">The Important of Variable Names</a>.</span></div><div><span ><br /></span></div><div class="blogger-post-footer">Copyright Jeremy Kubica 2011</div>Jeremy Kubicahttp://www.blogger.com/profile/02057783753310151192noreply@blogger.com0tag:blogger.com,1999:blog-7211948334062664963.post-29036428335213081512012-01-19T22:25:00.001-05:002012-01-19T22:27:17.384-05:00The Ant and the Grasshopper: A Fable of Algorithms<div><span ><b>An algorithm is a set of specific steps or instructions for solving a problem.</b></span></div><div><span ><br /></span></div><div><span >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.</span></div><div><span ><br /></span></div><div><span >"Little ant, what are you doing?" the grasshopper asked.</span></div><div><span ><br /></span></div><div><span >"Collecting food for the winter," responded the ant in a weary voice. He was exhausted from a day of hard labor.</span></div><div><span ><br /></span></div><div><span >"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?"</span></div><div><span ><br /></span></div><div><span >The ant paused for a moment while he thought. "It is the algorithm that we use," he finally replied.</span></div><div><span ><br /></span></div><div><span >"Algorithm?" asked the grasshopper.</span></div><div><span ><br /></span></div><div><span >"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."</span></div><div><span ><br /></span></div><div><span >"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.</span></div><div><span ><br /></span></div><div><span >"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."</span></div><div><span ><br /></span></div><div><span >"That sounds like a simple algorithm," remarked the grasshopper.</span></div><div><span ><br /></span></div><div><span >"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."</span></div><div><span ><br /></span></div><div><span >"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."</span></div><div><span ><br /></span></div><div><span >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.</span></div><div><span ><br /></span></div><div><span >Epiloge:</span></div><div><span >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. </span></div><div><span ><br /></span></div><div><span >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.</span></div><div><span ><br /></span></div><div><span >--------------------</span></div><div><span ><br /></span></div><div><span >To learn more about the computational ingenuity of ants read: <a href="http://computationaltales.blogspot.com/2011/12/tortoise-hare-and-50000-ants.html">The Tortoise, the Hare, and 50000 Ants</a>. </span></div><div><span ><br /></span></div><div><span >Or see the full list of stories <a href="http://computationaltales.blogspot.com/p/posts-by-topic.html">here</a>.</span></div><div><span ><br /></span></div><div class="blogger-post-footer">Copyright Jeremy Kubica 2011</div>Jeremy Kubicahttp://www.blogger.com/profile/02057783753310151192noreply@blogger.com2tag:blogger.com,1999:blog-7211948334062664963.post-85032995978626664642011-12-26T12:43:00.003-05:002011-12-28T12:23:46.545-05:00The Tortoise, the Hare, and 50000 Ants<div><span><b>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.</b></span></div><div><span><br /></span></div><div><span>"I want a rematch," screamed the hare.</span></div><div><span><br /></span></div><div><span>"Not today," answered the turtle, "I am still tired from our race. It would not be fair."</span></div><div><span><br /></span></div><div><span>"But… I should have won," argued the hare. "I want a rematch."</span></div><div><span><br /></span></div><div><span>"I will race you," said a tiny voice. The hare looked around, but could not find the speaker.</span></div><div><span><br /></span></div><div><span>"Down here," added the voice. The hare looked down and found an ant staring back at him.</span></div><div><span><br /></span></div><div><span>"You?" the hare asked suspiciously. "You are just an ant."</span></div><div><span><br /></span></div><div><span>"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."</span></div><div><span><br /></span></div><div><span>The hare scoffed.</span></div><div><span><br /></span></div><div><span>"Okay," replied the hare. "I will race you. Let's make it 5,000 meters. Can you even walk that far?"</span></div><div><span><br /></span></div><div><span>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."</span></div><div><span><br /></span></div><div><span>"Of course," replied the hare, "I am not afraid of a <i>thousand</i> ants."</span></div><div><span><br /></span></div><div><span>The turtle looked at the hare in surprise. Surely, the hare had learned the price of arrogance already.</span></div><div><span><br /></span></div><div><span>"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."</span></div><div><span><br /></span></div><div><span>"Yes," answered the hare. "That way I will not have to wait for days to see the look on your faces when you lose."</span></div><div><span><br /></span></div><div><span>The turtle's jaw dropped. "Really?" he asked. </span></div><div><span><br /></span></div><div><span>The hare did not respond. He busied himself with a short warm-up jog.</span></div><div><span><br /></span></div><div><span>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.</span></div><div><span><br /></span></div><div><span>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."</span></div><div><span><br /></span></div><div><span>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.</span></div><div><span><br /></span></div><div><span>"On your mark," announced the turtle. </span></div><div><span><br /></span></div><div><span>"Get set."</span></div><div><span><br /></span></div><div><span>The hare and 50,000 ants tensed.</span></div><div><span><br /></span></div><div><span>"Go."</span></div><div><span><br /></span></div><div><span>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.</span></div><div><span><br /></span></div><div><span>Still, the ants were finished in under a minute. </span></div><div><span><br /></span></div><div><span>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.</span></div><div><span><br /></span></div><div><span>Then, the hare realized what had happened.</span></div><div><span><br /></span></div><div><span>--------</span></div><div><span><br /></span></div><div><span>For other familiar tales, see <a href="http://computationaltales.blogspot.com/2011/12/binary-searching-for-cinderella.html">Binary Searching for Cinderella</a> or <a href="http://computationaltales.blogspot.com/2011/12/goldilocks-and-two-boolean-bears.html">Goldilocks and the Boolean Bears</a>.</span></div><div><span><br /></span></div><div><span>Or see a full list of stories <a href="http://computationaltales.blogspot.com/p/posts-by-topic.html">here</a>.</span></div><div><br /></div><div class="blogger-post-footer">Copyright Jeremy Kubica 2011</div>Jeremy Kubicahttp://www.blogger.com/profile/02057783753310151192noreply@blogger.com0tag:blogger.com,1999:blog-7211948334062664963.post-50301364409911316322011-12-15T22:04:00.002-05:002011-12-15T22:07:55.544-05:00Goldilocks and the Two Boolean Bears<div><span class="Apple-style-span" style="font-family:'courier new';font-size:100%;"><b>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.</b></span></div><div><span class="Apple-style-span" style="font-size:100%;"><br /></span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;">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.</span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;"><br /></span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;">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.</span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;"><br /></span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;">"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.</span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;"><br /></span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;">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."</span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;"><br /></span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;">She tried the next bowl of porridge.</span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;"><br /></span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;">"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.</span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;"><br /></span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;">"Who makes porridge that hot?" she moaned to no one in particular.</span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;"><br /></span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;">Traumatized, she looked for someplace to rest. In the living room, she found a single small chair.</span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;"><br /></span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;">"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."</span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;"><br /></span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;">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."</span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;"><br /></span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;">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.</span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;"><br /></span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;">"What is going on?" asked Goldilocks. "One bed is clearly comfortable. The other is not. Who makes a bed out of an iron plank?"</span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;"><br /></span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;">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.</span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;"><br /></span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;">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.</span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;"><br /></span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;">---------------------</span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;"><br /></span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;">For more about Boolean logic, see <a href="http://computationaltales.blogspot.com/2011/05/town-of-bool.html">Ann's visit to the city of Bool</a>.</span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;"><br /></span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;">For another take on familiar tale, see <a href="http://computationaltales.blogspot.com/2011/12/binary-searching-for-cinderella.html">Binary Searching for Cinderella</a>.</span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;"><br /></span></div><div class="blogger-post-footer">Copyright Jeremy Kubica 2011</div>Jeremy Kubicahttp://www.blogger.com/profile/02057783753310151192noreply@blogger.com1tag:blogger.com,1999:blog-7211948334062664963.post-48123355833814156252011-12-06T20:41:00.004-05:002011-12-06T21:50:19.650-05:00Binary Searching for Cinderella<div><span class="Apple-style-span" style="font-size:100%;"><b><span class="Apple-style-span" style="font-family:'courier new';">Binary search is an algorithm for efficiently finding a target value within a sorted list. The algorithm maintains a shrinking search window</span><span class="Apple-style-span" style=" ;font-family:'courier new';">. 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 </span><span class="Apple-style-span" style=" ;font-family:'courier new';">than the target</span><span class="Apple-style-span" style=" ;font-family:'courier new';">, 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.</span></b></span></div><div><span class="Apple-style-span" style="font-size:100%;"><br /></span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;">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.</span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;"><br /></span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;">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.</span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;"><br /></span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;">However, Alfred could NOT excuse his cousin's flawed strategies for finding the woman of his dreams.</span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;"><br /></span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;">"I shall go forth to every house and find the owner of the slipper," proclaimed Prince Charming.</span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;"><br /></span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;">"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."</span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;"><br /></span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;">"I must find my true love," protested the prince.</span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;"><br /></span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;">"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."</span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;"><br /></span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;">"I must be thorough," said the prince.</span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;"><br /></span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;">"You can still be thorough using a good algorithm," argued Alfred. "Trade data for time."</span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;"><br /></span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;">"Data? Time?" asked the prince.</span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;"><br /></span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;">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."</span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;"><br /></span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;">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."</span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;"><br /></span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;">"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."</span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;"><br /></span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;">"Binary search?" The prince's education had not required an algorithms class.</span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;"><br /></span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;">"The search algorithm," said Alfred.</span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;"><br /></span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;">The prince continued to stare blankly back at Alfred.</span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;"><br /></span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;">"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."</span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;"><br /></span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;">"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."</span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;"><br /></span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;">"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!"</span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;"><br /></span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;">"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.</span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;"><br /></span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;">"There are only three cases to consider:</span></div><div><span class="Apple-style-span" style="font-size:100%;"><span class="Apple-style-span" style="font-family:arial;">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. </span><span class="Apple-style-span" style=" ;font-family:arial;">The matching size will still be between your two fingers.</span></span></div><div><span class="Apple-style-span" style="font-size:100%;"><span class="Apple-style-span" style="font-family:arial;">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, </span><span class="Apple-style-span" style=" ;font-family:arial;"> </span><span class="Apple-style-span" style=" ;font-family:arial;">because all of the entries before the middle are too small to match. </span><span class="Apple-style-span" style="font-family:arial;">Again, the matching size will still be between your two fingers.</span></span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;">3) If the middle value matches the slipper's size, you are done. You found a match. Yay."</span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;"><br /></span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;">"Your method only eliminates half the list," objected the prince.</span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;"><br /></span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;">"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."</span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;"><br /></span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;">"When do I stop?" asked the prince. "When do I find my princess?"</span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;"><br /></span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;">"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."</span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;"><br /></span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;">"How will I know that there is nothing left to search?" asked the prince.</span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;"><br /></span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;">"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'."</span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;"><br /></span></div><div><span class="Apple-style-span" style="font-size:100%;"><span class="Apple-style-span" style="font-family:arial;">"That does not rhyme. It would sound better if it rhymed," observed the prince. "More importantly, w</span><span class="Apple-style-span" style=" ;font-family:arial;">hat if my princess's name gets skipped? Y</span><span class="Apple-style-span" style=" ;font-family:arial;">our algorithm involves big jumps early on. I am not sure that I could survive losing her."</span></span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;"><br /></span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;">"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."</span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;"><br /></span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;">The prince nodded solemnly. "I am sure that there will only be one match. My princess is perfectly unique."</span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;"><br /></span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;">Alfred stifled back a thousand comments and smiled politely.</span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;"><br /></span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;">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."</span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;"><br /></span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;">"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."</span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;"><br /></span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;">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."</span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;"><br /></span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;">Alfred sighed. He did not have an argument to counter that.</span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;"><br /></span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;">-------------------------</span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;"><br /></span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;">For more about binary search, see <a href="http://computationaltales.blogspot.com/2011/03/hunting-dragons-with-binary-search.html">Hunting Dragons with Binary Search</a>.</span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;"><br /></span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;">Also see my <a href="http://computationaltales.blogspot.com/2011/11/coming-soon-or-maybe-later.html">recent note on why updates will be less frequent for a while</a>.</span></div><div><br /></div><div class="blogger-post-footer">Copyright Jeremy Kubica 2011</div>Jeremy Kubicahttp://www.blogger.com/profile/02057783753310151192noreply@blogger.com1tag:blogger.com,1999:blog-7211948334062664963.post-17741315395455270852011-11-20T21:11:00.004-05:002011-11-22T22:07:30.271-05:00Coming 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.<div><br /></div><div>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.</div><div><br /></div><div>What to expect from the collection:</div><div><ul><li>A few new stories - Covering some earlier concepts and filling in the gaps.</li><li>More details of Ann's quest.</li><li>A reasonable ordering (both by concept and plot)</li><li>Extensive editing - At least 10% fewer gramatical errors!</li></ul></div><div>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. </div><div><br /></div><div>In the mean time, feel free to check out the current set of stories (around 70): <a href="http://computationaltales.blogspot.com/p/posts-by-topic.html">By Topic</a> or <a href="http://computationaltales.blogspot.com/p/stories-by-level.html">By Level</a>.</div><div><br /></div><div>Or to learn more about this blog, its goals, etc. at the <a href="http://computationaltales.blogspot.com/p/faq.html">FAQ</a>.</div><div class="blogger-post-footer">Copyright Jeremy Kubica 2011</div>Jeremy Kubicahttp://www.blogger.com/profile/02057783753310151192noreply@blogger.com0tag:blogger.com,1999:blog-7211948334062664963.post-32407866808368498492011-11-10T22:18:00.004-05:002017-12-21T10:24:11.242-05:00Names for Ingredients (and Variables)<div>
<span class="Apple-style-span"><b>The use of clear variable names can help make code more readable and reduce the likelihood of mistakes.</b></span></div>
<div>
<br /></div>
<div>
<span class="Apple-style-span">"Excuse me. I am looking for powdered rose petals." said Marcus. </span></div>
<div>
<span class="Apple-style-span"><br /></span></div>
<div>
<span class="Apple-style-span">"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.</span></div>
<div>
<span class="Apple-style-span"><br /></span></div>
<div>
<span class="Apple-style-span">Marcus glanced behind himself to confirm that he had already checked those shelves. Marcus turned back to the clerk.</span></div>
<div>
<span class="Apple-style-span"><br /></span></div>
<div>
<span class="Apple-style-span">"I did not see it there." responded Marcus. "In fact, I did not see any ingredients that I recognize. Everything seems to be encoded."</span></div>
<div>
<span class="Apple-style-span"><br /></span></div>
<div>
<span class="Apple-style-span">"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.</span></div>
<div>
<span class="Apple-style-span"><br /></span></div>
<div>
<span class="Apple-style-span">"That will be three copper pieces." said the clerk.</span></div>
<div>
<span class="Apple-style-span"><br /></span></div>
<div>
<span class="Apple-style-span">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.</span></div>
<div>
<span class="Apple-style-span"><br /></span></div>
<div>
<span class="Apple-style-span">"Are you sure this is powdered rose petals?" Marcus asked.</span></div>
<div>
<span class="Apple-style-span"><br /></span></div>
<div>
<span class="Apple-style-span">The clerk nodded. "Yes. This one clearly states 'RP3p', which means 'Rose Petals Powdered'."</span></div>
<div>
<span class="Apple-style-span"><br /></span></div>
<div>
<span class="Apple-style-span">"I see. You abbreviated it. RP for Rose petals and p for powdered. But why the 3?" asked Marcus.</span></div>
<div>
<span class="Apple-style-span"><br /></span></div>
<div>
<span class="Apple-style-span">"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.</span></div>
<div>
<span class="Apple-style-span"><br /></span></div>
<div>
<span class="Apple-style-span"><span class="Apple-style-span">"That is terribly confusing." </span><span class="Apple-style-span" style="font-family: "arial";">exclaimed Marcus. </span><span class="Apple-style-span" style="font-family: "arial";">"I have never heard of such a strange system."</span></span></div>
<div>
<span class="Apple-style-span"><br /></span></div>
<div>
<span class="Apple-style-span">A troubled look crossed the clerk's face. "It is my own scheme. It is more efficient." he explained.</span></div>
<div>
<span class="Apple-style-span"><br /></span></div>
<div>
<span class="Apple-style-span">"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."</span></div>
<div>
<span class="Apple-style-span"><br /></span></div>
<div>
<span class="Apple-style-span">"But the abbreviations all make sense." responded the clerk. "They are all quite simple actually. How else would you abbreviate 'Rose Petals'?"</span></div>
<div>
<span class="Apple-style-span"><br /></span></div>
<div>
<span class="Apple-style-span">"I would not!" answered Marcus. "I would label each ingredient clearly with its proper name."</span></div>
<div>
<span class="Apple-style-span"><br /></span></div>
<div>
<span class="Apple-style-span">"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."</span></div>
<div>
<span class="Apple-style-span"><br /></span></div>
<div>
<span class="Apple-style-span">"My word!" exclaimed Marcus. "You sell potions that use this idiotic encoding? Are you serious?"</span></div>
<div>
<span class="Apple-style-span"><br /></span></div>
<div>
<span class="Apple-style-span">The clerk did not respond.</span></div>
<div>
<span class="Apple-style-span"><br /></span></div>
<div>
<span class="Apple-style-span">"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.</span></div>
<div>
<span class="Apple-style-span"><br /></span></div>
<div>
<span class="Apple-style-span">"But it is more efficient." protested the clerk.</span></div>
<div>
<span class="Apple-style-span"><br /></span></div>
<div>
<span class="Apple-style-span">"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."</span></div>
<div>
<span class="Apple-style-span"><br /></span></div>
<div>
<span class="Apple-style-span">"But it is shorter." tried the clerk.</span></div>
<div>
<span class="Apple-style-span"><br /></span></div>
<div>
<span class="Apple-style-span">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."</span></div>
<div>
<span class="Apple-style-span"><br /></span></div>
<div>
<span class="Apple-style-span">"You have?" asked the clerk.</span></div>
<div>
<span class="Apple-style-span"><br /></span></div>
<div>
<span class="Apple-style-span">"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."</span></div>
<div>
<span class="Apple-style-span"><br /></span></div>
<div>
<span class="Apple-style-span">The clerk did not seem to have an argument for that. "I guess that I could change them back." he said.</span></div>
<div>
<span class="Apple-style-span"><br /></span></div>
<div>
<span class="Apple-style-span">"Yes. You should." encouraged Marcus. "Now. Are you absolutely sure that this is the ingredient that I need?"</span></div>
<div>
<span class="Apple-style-span"><br /></span></div>
<div>
<span class="Apple-style-span">The clerk hesitated.</span></div>
<div>
<span class="Apple-style-span"><br /></span></div>
<div>
<span class="Apple-style-span">"I see." said Marcus. "I will be back some other time then."</span></div>
<div>
<span class="Apple-style-span"><br /></span></div>
<div>
<span class="Apple-style-span">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.</span></div>
<div>
<span class="Apple-style-span"><br /></span></div>
<div>
<span class="Apple-style-span">---------------------</span></div>
<div>
<span class="Apple-style-span"><br /></span></div>
<div>
<span class="Apple-style-span">Also see Ann's experience with names in <a href="http://computationaltales.blogspot.com/2011/03/importance-of-variable-names.html">The Importance of (Variable) Names</a>. </span></div>
<div>
<span class="Apple-style-span"><br /></span></div>
<div>
<span class="Apple-style-span">Or read more practical advice by Marcus in: <a href="http://computationaltales.blogspot.com/2011/05/importance-of-unit-testing-magical.html">The Importance of Unit Testing Magic Spells</a>; <a href="http://computationaltales.blogspot.com/2011/08/data-validation-marcus-and-cheese.html">Data Validation, Marcus, and the Minstrel of Cheese</a>, or <a href="http://computationaltales.blogspot.com/2011/09/version-control-in-magic-spell.html">Version Control in Magic Spell Development.</a></span></div>
<div class="blogger-post-footer">Copyright Jeremy Kubica 2011</div>Jeremy Kubicahttp://www.blogger.com/profile/02057783753310151192noreply@blogger.com0tag:blogger.com,1999:blog-7211948334062664963.post-1148365264955052682011-11-02T21:22:00.002-04:002011-11-02T21:27:57.147-04:00Recursion, Overhead, and Computational Graffiti<div><span class="Apple-style-span" ><b>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.</b></span></div><div><span class="Apple-style-span" ><br /></span></div><div><span class="Apple-style-span" >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.</span></div><div><span class="Apple-style-span" ><br /></span></div><div><span class="Apple-style-span" >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.</span></div><div><span class="Apple-style-span" ><br /></span></div><div><span class="Apple-style-span" >Then Ann saw a message that stopped her cold:</span></div><div><span class="Apple-style-span" >int RecursiveAdd(int n, int m) {</span></div><div><span class="Apple-style-span" > if (m == 0) return n; // base case</span></div><div><span class="Apple-style-span" > return RecursiveAdd(n, m-1) + 1;</span></div><div><span class="Apple-style-span" >}</span></div><div><span class="Apple-style-span" ><br /></span></div><div><span class="Apple-style-span" >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.</span></div><div><span class="Apple-style-span" ><br /></span></div><div><span class="Apple-style-span" >Tearing herself away from the disturbing image, she broke out in a full run. There was no time to lose.</span></div><div class="blogger-post-footer">Copyright Jeremy Kubica 2011</div>Jeremy Kubicahttp://www.blogger.com/profile/02057783753310151192noreply@blogger.com1tag:blogger.com,1999:blog-7211948334062664963.post-47610496532832641072011-10-25T22:27:00.004-04:002011-10-25T22:48:21.906-04:00The Curse of Excessive Commenting<div><span class="Apple-style-span"><b>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.</b></span></div><div><span class="Apple-style-span"><br /></span></div><div><span class="Apple-style-span">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.</span></div><div><span class="Apple-style-span"><br /></span></div><div><span class="Apple-style-span">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. </span></div><div><span class="Apple-style-span"><br /></span></div><div><span class="Apple-style-span">"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." </span></div><div><span class="Apple-style-span"><br /></span></div><div><span class="Apple-style-span">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.</span></div><div><span class="Apple-style-span"><br /></span></div><div><span class="Apple-style-span">"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."</span></div><div><span class="Apple-style-span"><br /></span></div><div><span class="Apple-style-span">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.</span></div><div><span class="Apple-style-span"><br /></span></div><div><span class="Apple-style-span">"I am hitting it again." narrated Drex.</span></div><div><span class="Apple-style-span"><br /></span></div><div><span class="Apple-style-span">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.</span></div><div><span class="Apple-style-span"><br /></span></div><div><span class="Apple-style-span">"I am hitting it again." narrated Drex.</span></div><div><span class="Apple-style-span"><br /></span></div><div><span class="Apple-style-span"><span class="Apple-style-span">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</span><span class="Apple-style-span" style="font-family: arial; "> sleep-deprived wizard at two in the morning.</span></span></div><div><span class="Apple-style-span"><br /></span></div><div><span class="Apple-style-span">"I am hitting it again." narrated Drex.</span></div><div><span class="Apple-style-span"><br /></span></div><div><span class="Apple-style-span">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.</span></div><div><span class="Apple-style-span"><br /></span></div><div><span class="Apple-style-span">"I am hitting it again." narrated Drex.</span></div><div><span class="Apple-style-span"><br /></span></div><div><span class="Apple-style-span">Unfortunately, Rachel did not know if she could last another four days.</span></div><div><span class="Apple-style-span"><br /></span></div><div>-----------------------------</div><div><br /></div><div>Also read about the <a href="http://computationaltales.blogspot.com/2011/08/importance-of-good-comments-tale-of.html">importance of good comments in baking</a>. Or read more about Drex in <a href="http://computationaltales.blogspot.com/2011/03/loops-and-making-horseshoe.html">Loops and Making Horseshoes</a>.</div><div class="blogger-post-footer">Copyright Jeremy Kubica 2011</div>Jeremy Kubicahttp://www.blogger.com/profile/02057783753310151192noreply@blogger.com0tag:blogger.com,1999:blog-7211948334062664963.post-69972234942529352232011-10-15T21:49:00.005-04:002011-12-04T22:20:08.367-05:00Sorting During the Flu Outbreak: The Reality of Sorting Small Sets<div><b><span class="Apple-style-span"><span class="Apple-style-span">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 </span><span class="Apple-style-span">almost</span><span class="Apple-style-span"> in the correct order.</span></span></b></div><div><span class="Apple-style-span"><br /></span></div><div><span class="Apple-style-span">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.</span></div><div><span class="Apple-style-span"><br /></span></div><div><span class="Apple-style-span">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.</span></div><div><span class="Apple-style-span"><br /></span></div><div><span class="Apple-style-span">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!</span></div><div><span class="Apple-style-span"><br /></span></div><div><span class="Apple-style-span">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.</span></div><div><span class="Apple-style-span"><br /></span></div><div><span class="Apple-style-span">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.</span></div><div><span class="Apple-style-span"><br /></span></div><div><span class="Apple-style-span">"No!'" wailed Mrs. Magee, but it was too late. The competition was over.</span></div><div><span class="Apple-style-span"><br /></span></div><div><span class="Apple-style-span">-------------------</span></div><div><span class="Apple-style-span"><br /></span></div><div><span class="Apple-style-span">Read about the skill of Mrs. Magee's class in <a href="http://computationaltales.blogspot.com/2011/10/merge-sort-and-lines-of-kindergarteners.html">Merge Sort and Lines of Kindergarteners</a>. Or read about other sorting algorithms in <a href="http://computationaltales.blogspot.com/2011/04/why-tailors-use-insertion-sort.html">Why Tailors Use Insertion Sort</a> or <a href="http://computationaltales.blogspot.com/2011/04/bullies-bubble-sort-and-soccer-tickets.html">Bullies, Bubble Sort, and Soccer Tickets</a>.</span></div><div><span class="Apple-style-span"><br /></span></div><div class="blogger-post-footer">Copyright Jeremy Kubica 2011</div>Jeremy Kubicahttp://www.blogger.com/profile/02057783753310151192noreply@blogger.com0tag:blogger.com,1999:blog-7211948334062664963.post-91115704765366238822011-10-08T21:21:00.011-04:002012-02-18T21:19:24.282-05:00Merge Sort and Lines of Kindergarteners<div><span class="Apple-style-span" style="font-family:'courier new';font-size:100%;"><b>Merge sort is a recursive, sorting algorithm based on two intuitive principles:</b></span></div><div><span class="Apple-style-span" style="font-family:'courier new';font-size:100%;"><b>1) It is easy to sort very short lists. In fact, it is trivial to sort lists containing only one item.</b></span></div><div><span class="Apple-style-span" style="font-family:'courier new';font-size:100%;"><b>2) It is easier to merge together two sorted lists than it is to sort a long list.</b></span></div><div><span class="Apple-style-span" style="font-family:'courier new';font-size:100%;"><b>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."</b></span></div><br /><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;">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.</span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;"><br /></span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;">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.</span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;"><br /></span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;">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.</span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;"><br /></span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;">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. </span></div><div><span class="Apple-style-span" style="font-family: arial; font-size: medium; "><br /></span></div><div><span class="Apple-style-span" style="font-family: arial; font-size: medium; ">Of course, there was also a strategy -- Merge Sort. </span><span class="Apple-style-span" style="font-family: arial; font-size: medium; ">It was her secret weapon, her key to winning.</span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;"><br /></span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;">At the command "LINE UP!" the class would split into two equally sized groups.</span></div><br /><div style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgHHwGi1I5uBp-SGlo_tA5YirWf9LNQu6uPFKLnMuFzog1Ehtflwgm-hz0oZskp9o9l1MbY-iMvDry_L3X3aZTtGrVymQXDi-SqUnzAM2iJi65745aL2GNFkivvCn6P9j3lDMqLog5EyC8/s1600/MergeSort1.jpg" onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}"><img style="cursor:pointer; cursor:hand;width: 400px; height: 114px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgHHwGi1I5uBp-SGlo_tA5YirWf9LNQu6uPFKLnMuFzog1Ehtflwgm-hz0oZskp9o9l1MbY-iMvDry_L3X3aZTtGrVymQXDi-SqUnzAM2iJi65745aL2GNFkivvCn6P9j3lDMqLog5EyC8/s400/MergeSort1.jpg" border="0" alt="" id="BLOGGER_PHOTO_ID_5661297017530148642" /></a></div><div style="text-align: center;"><span class="Apple-style-span" style="font-family:arial;font-size:85%;">Class before sorting</span></div><div style="text-align: center;"><br /></div><div style="text-align: center;"><img src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEi-MMxEoUHqkuDFiur8KnZyBqzN9SZDaeukkCEOY82zBBBrlZw7VE79UH0D1G8GH0bDwbyKDZZzgXUdqi1qrXKqfOUtGbpbQrmNxO5oJiD9aSNetP1GwtyMM2zMjRGwBHTiwM86OTvPIac/s400/MergeSort2.jpg" border="0" alt="" id="BLOGGER_PHOTO_ID_5661297110362251858" style="cursor: pointer; width: 400px; height: 113px; " /></div><div style="text-align: center;"><span class="Apple-style-span" style="font-size:85%;">First split</span></div><div style="text-align: center;"><span class="Apple-style-span" style="font-size:85%;"><br /></span></div><div style="text-align: left;"><div style="text-align: left; "><span class="Apple-style-span" style="font-size:100%;">Those groups would then each split into two smaller groups. </span></div></div><div style="text-align: center;"><br /></div><div style="text-align: center;"><img src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj3_my3rkBTxwyxXPOFldprT3f1HsW6YhibKnmSaSKFlbJqpT4uvJGsFiMn01uYzRq8rgUv2S0QEcjulTP4jIIgjwfOuoCHwjL9g2_PG9HjaEoQ5MFzf23J_A4iXNIeIWuXhuBmJtgH-zQ/s400/MergeSort3a.jpg" border="0" alt="" id="BLOGGER_PHOTO_ID_5661296931539407138" style="cursor: pointer; width: 220px; height: 150px; " /> <img src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhgqshPgpSLUHzdlGhmigZLVJsW5y3WEyBcxrZtm01vMNQEge5I3c_ATVOsmTb_jUe_vSLrDd72dZ0xzHN714YHzcdVJWu1trXkzYucIYz0Ej85vAVp3HGBk_qd9g4FjitPEplIuVA99UI/s400/MergeSort3b.jpg" border="0" alt="" id="BLOGGER_PHOTO_ID_5661297215121391026" style="cursor: pointer; width: 320px; height: 150px; " /></div><div style="text-align: center;"><span class="Apple-style-span" style="font-family:arial;"><br /></span></div><div style="text-align: left;"><div style="text-align: left;"><span class="Apple-style-span" style="font-family:arial;font-size:100%;">The splitting continued until each group had just a single person.</span></div><div style="text-align: left;"><span class="Apple-style-span" style="font-family:arial;font-size:100%;"><br /></span></div><div style="text-align: left;"><span class="Apple-style-span" style="font-family:arial;font-size:100%;">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.</span></div></div><div style="text-align: center;"><span class="Apple-style-span" style="font-family:arial;"><br /></span></div><div style="text-align: center;"><img src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhR3kjdVECfQLH0H_dhdG0L1AMawwbedxBLi732HL3dBRPOtcPYtZsSV0w4MR_lZJCptQWVz0ow3qLO6Ew5RB2POTprbmv7bEkwcuqxk9GxsQuolSj47W8polJtMzyy-mA-Eio4ysTNry4/s400/MergeSort4.jpg" border="0" alt="" id="BLOGGER_PHOTO_ID_5661298038366640898" style="cursor: pointer; width: 350px; height: 330px; " /></div><div style="text-align: center;"><br /></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;">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. </span><span class="Apple-style-span" style="font-family: arial; font-size: medium; ">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. </span></div><div><br /></div><div style="text-align: center;"><img src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgcrg-osaJCiufFR0szblml0peH-8-Uw0tDqneFVjFQbCev4OGYPZdPxwBG-VtJ6uw2LwjLUIDVIfUQmLOLfNkyN0lk17KoT01T0YK8EFaTtUnXgZ4dl3RCNlQeUIJ9KY0gxdQKRuk8Cxw/s400/MergeSort5a.jpg" border="0" alt="" id="BLOGGER_PHOTO_ID_5661298279980721954" style="cursor: pointer; width: 400px; height: 206px; " /></div><div style="text-align: center;"><span class="Apple-style-span" style="font-family:arial;font-size:85%;">Merge Step 1</span></div><div><span class="Apple-style-span" style="font-family:arial;"><br /></span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;">Now the second smallest still had to be one of the front two kids.</span></div><div><span class="Apple-style-span" style="font-family:arial;"><br /></span></div><div><div style="text-align: center;"><img src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg-zSP7KZN_9ZfiobfVXFET2qKFhdieJ_ze0nzRzKNIw1T6e5T5v3aQQKxDeNbIHxgJfaJjW_aE2Olqjfr0kCdDPD4qLqHpJJtjiQ08LHRS9kLCZOTkuu7l3h1ErOHD-NUMj1GdTXxzsyc/s400/MergeSort5b.jpg" border="0" alt="" id="BLOGGER_PHOTO_ID_5661298275914992770" style="cursor: pointer; width: 400px; height: 206px; " /></div><div style="text-align: center;"><span class="Apple-style-span" style="font-size:85%;">Merge Step 2</span></div><div style="text-align: center;"><br /></div><div style="text-align: left;"><span class="Apple-style-span" style="font-size:100%;">And so forth.</span></div><div style="text-align: center;"><br /></div><div style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhd304sJ00YhUR2KMieshapxq7MtaLBBfFSVDSS3cvsob66J8VY43p5P2rPIsfm4rKTaCAjc3i9R8ZcSsJMECY2AnWoz8uFGjkg7nRRdizcSWbxLlAeJQ8EeC2Okr_6F6FkeKonXQk3d-w/s1600/MergeSort5c.jpg" onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}"><img src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhd304sJ00YhUR2KMieshapxq7MtaLBBfFSVDSS3cvsob66J8VY43p5P2rPIsfm4rKTaCAjc3i9R8ZcSsJMECY2AnWoz8uFGjkg7nRRdizcSWbxLlAeJQ8EeC2Okr_6F6FkeKonXQk3d-w/s400/MergeSort5c.jpg" border="0" alt="" id="BLOGGER_PHOTO_ID_5661298276163806690" style="cursor: pointer; width: 400px; height: 206px; " /></a></div><div style="text-align: center;"><span class="Apple-style-span" style="font-size:85%;">Merge Step 3</span></div><div style="text-align: center;"><br /></div><div><div style="text-align: center;"><br /></div><div style="text-align: center;"><img src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjntzi0J57bw7u80eAv8_kcctLdsNX_7Pq4-JBLj8y4Pyk1wTnB8O5nVxIkERRVj2uNRckeUqVQ4zcl9eBXMYRoFSzZOlpzRU48wDgdjyROpyqUjYJ5h3nSp5EwuoGVNzuc4VpzbdH5BOY/s400/MergeSort5d.jpg" border="0" alt="" id="BLOGGER_PHOTO_ID_5661298269949802114" style="cursor: pointer; width: 400px; height: 206px; " /></div><div style="text-align: center;"><span class="Apple-style-span" style="font-size:85%;">Merge Step 4</span></div><div style="text-align: center;"><br /></div><div style="text-align: center;"><img src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhuFfr8MB2hNrqEHqpp_87tRJX7LiclfQSmCCqb72z7Y9CeZpTp5WGJQ3B8b5vA4cZ05HoH_kK0JvpoaCFtNa9YVR0Cv_vHFxEnIFg0YcFmAWQUR-gT8s3CZ5iVTHQxR2-mCemx4abljAQ/s400/MergeSort5e.jpg" border="0" alt="" id="BLOGGER_PHOTO_ID_5661298270390279826" style="cursor: pointer; width: 400px; height: 206px; " /></div></div><div style="text-align: center;"><span class="Apple-style-span" style="font-size:100%;">Merge Step 5</span></div><div><span class="Apple-style-span" style="font-size:100%;"><br /></span></div><div><div><span class="Apple-style-span" style="font-size:100%;"><br /></span></div><div><span class="Apple-style-span" style="font-size:100%;">The lines would quickly merge together, forming larger groups. This would continue until the entire class was in order.</span></div><div><span class="Apple-style-span" style="font-size:100%;"><br /></span></div><div><span class="Apple-style-span" style="font-size:100%;">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.</span></div><div><span class="Apple-style-span" style="font-size:100%;"><br /></span></div><div><span class="Apple-style-span" style="font-size:100%;"><i>To be continued in <a href="http://computationaltales.blogspot.com/2011/10/sorting-during-flu-outbreak-reality-of.html">Sorting During the Flu Outbreak: The Reality of Sorting Small Sets</a></i></span></div><div><span class="Apple-style-span" style="font-size:100%;"><br /></span></div><div><span class="Apple-style-span" style="font-size:100%;">---------------</span></div><div><span class="Apple-style-span" style="font-size:100%;"><br /></span></div><div><span class="Apple-style-span" style="font-size:100%;">To learn more about other sorting techniques see <a href="http://computationaltales.blogspot.com/2011/04/why-tailors-use-insertion-sort.html">Why Tailors Use Insertion Sort</a> or <a href="http://computationaltales.blogspot.com/2011/04/bullies-bubble-sort-and-soccer-tickets.html">Bullies, Bubble Sort, and Soccer Tickets</a>.</span></div></div></div><div class="blogger-post-footer">Copyright Jeremy Kubica 2011</div>Jeremy Kubicahttp://www.blogger.com/profile/02057783753310151192noreply@blogger.com0tag:blogger.com,1999:blog-7211948334062664963.post-62230891963268938242011-10-01T15:26:00.002-04:002011-10-01T15:35:24.900-04:00Connected Components and the Birthday Sign<div><div><span class="Apple-style-span" style="font-family:'courier new';"><b>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.</b></span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;"><br /></span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;">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.</span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;"><br /></span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;">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.</span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;"><br /></span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;">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.</span></div></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;"><br /></span></div><div style="text-align: center;"><span class="Apple-style-span" style="font-family:arial;font-size:100%;"><img style="cursor:pointer; cursor:hand;width: 400px; height: 295px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiFDLhgf-myYkRPXJdGH8_doEvfJXPZtDIGJqN1xp46Xj4kg-c6w2SsmreVXdnlp-N2VhV-oKNGzrPHXF_4ATI6YsAYcMyI91di5vcyRHdo4oYuvDygp44H1QQ3Ps2JMXVDG_O7LQjr7XQ/s400/HappyBirthday.jpg" border="0" alt="" id="BLOGGER_PHOTO_ID_5658607539017453858" /></span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;"><div><br /></div><div>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.</div><div><br /></div><div>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.</div><div><br /></div><div>----------------</div><div><br /></div><div>For more about graphs, read about <a href="http://computationaltales.blogspot.com/2011/07/city-of-graph-part-1-in-anns-visit-to.html">Ann's trip to the City of G'Raph</a>.</div><div><br /></div><div>NEW at Computation Fairy Tales: <a href="http://computationaltales.blogspot.com/p/stories-by-level.html">A list of stories index by level of CS background</a>. Feedback welcome.</div><div><br /></div><div>Remember for all the updates, follow <a href="http://twitter.com/#!/CompFairyTales">CompFairyTales</a> on twitter.</div><div><br /></div></span></div><div class="blogger-post-footer">Copyright Jeremy Kubica 2011</div>Jeremy Kubicahttp://www.blogger.com/profile/02057783753310151192noreply@blogger.com0tag:blogger.com,1999:blog-7211948334062664963.post-83943528202595093052011-09-26T22:21:00.004-04:002017-09-03T10:54:22.488-04:00The Marvelous IF-ELSE Life of the King's Turtle<div>
<span class="Apple-style-span"><b>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. </b></span></div>
<div>
<span class="Apple-style-span"><b><br /></b></span></div>
<div>
<span class="Apple-style-span">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.</span></div>
<div>
<span class="Apple-style-span"><br /></span></div>
<div>
<span class="Apple-style-span">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:</span></div>
<div>
<span class="Apple-style-span"><br /></span></div>
<div>
<span class="Apple-style-span"><b>IF</b> he is hungry</span></div>
<div>
<span class="Apple-style-span"> eat</span></div>
<div>
<span class="Apple-style-span"><br /></span></div>
<div>
<span class="Apple-style-span">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.</span></div>
<div>
<span class="Apple-style-span"><br /></span></div>
<div>
<span class="Apple-style-span">For some aspects of life, the IF statement could have two different actions depending on the condition. For example, when he was swimming:</span></div>
<div>
<span class="Apple-style-span"><br /></span></div>
<div>
<span class="Apple-style-span"><b>IF</b> the fountain is on</span></div>
<div>
<span class="Apple-style-span"> play in the fountain</span></div>
<div>
<span class="Apple-style-span"><b>ELSE</b></span></div>
<div>
<span class="Apple-style-span"> swim around the large rock</span></div>
<div>
<span class="Apple-style-span"><br /></span></div>
<div>
<span class="Apple-style-span">Obviously, Fido enjoyed the fountain more than the rock.</span></div>
<div>
<span class="Apple-style-span"><br /></span></div>
<div>
<span class="Apple-style-span">Sometimes the decisions would be complex enough to require a series of chained IF-ELSE statements:</span></div>
<div>
<span class="Apple-style-span"><br /></span></div>
<div>
<span class="Apple-style-span"><b>IF</b> it is sunny</span></div>
<div>
<span class="Apple-style-span"> sit in the grass</span></div>
<div>
<span class="Apple-style-span"><b>ELSE IF</b> it is warm</span></div>
<div>
<span class="Apple-style-span"> go swimming</span></div>
<div>
<span class="Apple-style-span"><b>ELSE</b></span></div>
<div>
<span class="Apple-style-span"> sleep</span></div>
<div>
<span class="Apple-style-span"><br /></span></div>
<div>
<span class="Apple-style-span">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.</span></div>
<div>
<span class="Apple-style-span"><br /></span></div>
<div>
<span class="Apple-style-span">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.</span></div>
<div>
<span class="Apple-style-span"><br /></span></div>
<div>
<span class="Apple-style-span">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:</span></div>
<div>
<span class="Apple-style-span"><br /></span></div>
<div>
<span class="Apple-style-span"><b>IF</b> he is closer to the right rock</span></div>
<div>
<span class="Apple-style-span"> swim around the right rock</span></div>
<div>
<span class="Apple-style-span"><b>ELSE</b></span></div>
<div>
<span class="Apple-style-span"> swim around the left rock</span></div>
<div>
<span class="Apple-style-span"><br /></span></div>
<div>
<span class="Apple-style-span">Thus order was restored to his life.</span></div>
<div>
<span class="Apple-style-span"><br /></span></div>
<div>
<span class="Apple-style-span">------------------------</span></div>
<div>
<span class="Apple-style-span"><br /></span></div>
<div>
<span class="Apple-style-span">For more discussion of IF-ELSE also see <a href="http://computationaltales.blogspot.com/2011/05/learning-if-else-hard-way.html">Learning IF-ELSE the Hard Way</a>.</span></div>
<div class="blogger-post-footer">Copyright Jeremy Kubica 2011</div>Jeremy Kubicahttp://www.blogger.com/profile/02057783753310151192noreply@blogger.com0tag:blogger.com,1999:blog-7211948334062664963.post-73377468664782420872011-09-22T22:29:00.002-04:002011-09-24T09:12:30.059-04:00Inheritance in Cheeses and Magic Spells: Part 4 of Marcus and the Cursed Cheese<div><span class="Apple-style-span" style="font-family:'courier new';font-size:100%;"><b>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].</b></span></div><div><span class="Apple-style-span" style="font-family:'courier new';font-size:100%;"><b><br /></b></span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;">"Can you tell me anything more about the visitor?" asked Marcus. He was very worried.</span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;"><br /></span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;">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."</span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;"><br /></span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;">"This is bad," stated Marcus.</span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;"><br /></span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;">"Why?" asked both the cheese minstrel and the foreman.</span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;"><br /></span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;">"The wizard that cursed my cheese did so without knowing what type of cheese it was." Marcus explained.</span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;"><br /></span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;">"So? Is there really a difference in cursing different types of cheese?" asked the cheese minstrel.</span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;"><br /></span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;">"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."</span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;"><br /></span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;">"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." </span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;"><br /></span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;">"Likely Patagonian Popper?" asked the cheese minstrel. Honestly, he was more interested in the cheese aspect of this story than in the magic spells. </span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;"><br /></span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;">"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."</span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;"><br /></span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;">"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.</span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;"><br /></span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;">"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?"</span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;"><br /></span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;">"Only Sam, the logistics manager." answered the foreman. "But he is having some personal issues at the moment."</span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;"><br /></span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;">"What sort of issues?" asked Marcus.</span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;"><br /></span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;">"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."</span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;"><br /></span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;">"The traveling salesman problem." Marcus whispered under his breadth. Then louder: "When did this start?"</span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;"><br /></span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;">The manager thought for a moment. "You know, it was right after that visitor."</span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;"><br /></span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;">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."</span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;"><br /></span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;">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.</span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;"><br /></span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;">------------------------------------------</span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;"><br /></span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;">See how the saga of the cursed cheese began with <a href="http://computationaltales.blogspot.com/2011/08/data-validation-marcus-and-cheese.html">Part 1: Data Validation, Marcus, and the Cheese Minstrel</a>. Or read about Ann's discover of the spell of Unnatural P=NP Obsession during <a href="http://computationaltales.blogspot.com/2011/07/city-of-graph-part-1-in-anns-visit-to.html">her trip to G'Raph</a>.</span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;"><br /></span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;">Or if you think the cheese minstrel has it bad, also check out the plight of the king's hedgehog walker in <a href="http://computationaltales.blogspot.com/2011/06/incident-at-north-gate-or-why-is-not.html">The Incident at the North Gate (or Why = is not ==)</a>.</span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;"><br /></span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;">Want more updates and commentary? Follow CompFairyTales on Twitter or follow the author (Jeremy Kubica) on Google+.</span></div><div class="blogger-post-footer">Copyright Jeremy Kubica 2011</div>Jeremy Kubicahttp://www.blogger.com/profile/02057783753310151192noreply@blogger.com0tag:blogger.com,1999:blog-7211948334062664963.post-65747325367259425502011-09-17T21:37:00.004-04:002011-09-17T21:45:27.109-04:00Classes of Cheese: Part 3 of Marcus and the Cursed Cheese<div><span class="Apple-style-span" style="font-family:'courier new';font-size:100%;"><b>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.</b></span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;"><br /></span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;">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.</span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;"><br /></span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;">"Pardon the mess," started the foreman. "We are in the middle of packing today's soft-cheese shipment."</span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;"><br /></span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;">"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.</span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;"><br /></span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;">"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.</span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;"><br /></span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;">"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.</span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;"><br /></span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;">"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."</span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;"><br /></span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;">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."</span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;"><br /></span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;">"Emit smell?" asked the cheese minstrel without looking up from his notepad.</span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;"><br /></span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;">"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."</span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;"><br /></span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;">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.</span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;"><br /></span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;">"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."</span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;"><br /></span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;">"Boxed or unboxed?" asked Marcus. "Was the cheese already packaged?"</span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;"><br /></span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;">"Uh..." the foreman seemed confused. "I think it was already in its boxes. Why?"</span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;"><br /></span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;">Marcus did not answer. His mind was racing. It was worse than he had thought.</span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;"><br /></span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;">To be continued in Part 4: Inheritance in Cheeses and Magic Spells...</span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;"><br /></span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;">-------------------------</span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;"><br /></span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;">See how the entire saga of the curse cheese began in <a href="http://computationaltales.blogspot.com/2011/08/data-validation-marcus-and-cheese.html">Part 1: Data Validation, Marcus, and the Minstrel of Cheese</a></span></div><div class="blogger-post-footer">Copyright Jeremy Kubica 2011</div>Jeremy Kubicahttp://www.blogger.com/profile/02057783753310151192noreply@blogger.com0tag:blogger.com,1999:blog-7211948334062664963.post-44565262449151650992011-09-11T21:33:00.005-04:002011-09-17T21:44:40.112-04:00Objects, Encapsulation, and Cheese Factories: Part 2 of Marcus and the Cursed Cheese<div><span class="Apple-style-span" style="font-family:'courier new';font-size:100%;"><b>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.</b></span></div><div><span class="Apple-style-span" style="font-family:'courier new';font-size:100%;"><b><br /></b></span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;">"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.</span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;"><br /></span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;">"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."</span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;"><br /></span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;">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.</span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;"><br /></span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;">"That is simply not possible." countered the foreman. "I would know!"</span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;"><br /></span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;">"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.</span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;"><br /></span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;">"Yes. How?" added Marcus. "I already told you that this particular curse only targets wizards."</span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;"><br /></span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;">"We have a very sophisticated cheese making process here. We use the latest cheese making objects. They are fully self-contained." explained the foreman.</span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;"><br /></span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;">"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.</span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;"><br /></span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;">"He means machines." explained Marcus. Then turning to the foreman, Marcus asked "Why do you call them objects?"</span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;"><br /></span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;">"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."</span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;"><br /></span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;">"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.</span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;"><br /></span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;">"Well..." The foreman thought for a while. "I think you are correct. But our machines are top of the line."</span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;"><br /></span></div><div><span class="Apple-style-span" style="font-size:100%;"><span class="Apple-style-span" style="font-family:arial;">"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 t</span><span class="Apple-style-span" style=" ;font-family:arial;">he 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."</span></span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;"><br /></span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;">"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."</span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;"><br /></span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;">"Yes. But do you test for curses targeting wizards?" pushed Marcus.</span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;"><br /></span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;">"Well... No." answered the foreman. He suddenly looked very worried.</span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;"><br /></span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;">"Tell me more about this visitor." commanded Marcus.</span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;"><br /></span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;">"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."</span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;"><br /></span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;">"Can I see the machine that this visitor was so obsessed with?"</span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;"><br /></span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;">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.</span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;"><br /></span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;">Unfortunately, a quick check of the machine revealed no signs of a curse causing subroutine.</span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;"><br /></span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;">"Did the visitor look at anything else?" inquired Marcus.</span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;"><br /></span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;">The foreman, now sufficiently panicked, nodded vigorously. "He wanted to see our shipping facility. He said something about wondering where all our cheese went."</span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;"><br /></span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;">Marcus was certain that in the shipping area, he would find both stacks of cheese and a list of wizards awaiting their shipments.</span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;"><br /></span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;"><i>To be continued in <a href="http://computationaltales.blogspot.com/2011/09/classes-of-cheese-part-3-of-marcus-and.html">Classes of Cheese: Part 3 of Marcus and the Cursed Cheese</a>...</i></span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;"><br /></span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;">--------------------</span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;"><br /></span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;">Read about how Marcus met the cheese minstrel in <a href="http://computationaltales.blogspot.com/2011/08/data-validation-marcus-and-cheese.html">Part 1: Data Validation, Marcus, and the Minstrel of Cheese</a>.</span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;"><br /></span></div><div><span class="Apple-style-span" style="font-family:arial;font-size:100%;">Or read about Marcus and the importance of unit testing in <a href="http://computationaltales.blogspot.com/2011/05/importance-of-unit-testing-magical.html">The Importance of Unit Testing Magical Spells</a> or good version control in <a href="http://computationaltales.blogspot.com/2011/09/version-control-in-magic-spell.html">Version Control in Magic Spell Development</a>.</span></div><div class="blogger-post-footer">Copyright Jeremy Kubica 2011</div>Jeremy Kubicahttp://www.blogger.com/profile/02057783753310151192noreply@blogger.com0