The Curse of Excessive Commenting

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

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

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

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

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

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

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

"I am hitting it again." narrated Drex.

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

"I am hitting it again." narrated Drex.

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

"I am hitting it again." narrated Drex.

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

"I am hitting it again." narrated Drex.

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

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

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

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

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

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

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

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

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

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

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

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

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

Merge Sort and Lines of Kindergarteners

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

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

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

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

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

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

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

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

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

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

Class before sorting

First split

Those groups would then each split into two smaller groups.

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

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

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

Merge Step 1

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

Merge Step 2

And so forth.

Merge Step 3

Merge Step 4

Merge Step 5

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

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

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

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

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

Connected Components and the Birthday Sign

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

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

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

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

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

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

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

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

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

Remember for all the updates, follow CompFairyTales on twitter.