Monday, December 26, 2011

The Tortoise, the Hare, and 50000 Ants

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

"I want a rematch," screamed the hare.

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

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

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

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

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

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

The hare scoffed.

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

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

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

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

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

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

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

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

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

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

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

"On your mark," announced the turtle.

"Get set."

The hare and 50,000 ants tensed.

"Go."

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

Still, the ants were finished in under a minute.

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

Then, the hare realized what had happened.

--------


Or see a full list of stories here.

Thursday, December 15, 2011

Goldilocks and the Two Boolean Bears

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

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

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

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

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

She tried the next bowl of porridge.

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

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

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

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

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

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

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

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

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

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

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

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

Tuesday, December 6, 2011

Binary Searching for Cinderella

Binary search is an algorithm for efficiently finding a target value within a sorted list. The algorithm maintains a shrinking search window. It narrows down that window by repeatedly ruling out half of the remaining search space. At each step, the algorithm checks the middle item in the current window and compares it with the target value. If the value in the middle is less than the target, you can rule out the lower half of the window. If the value is greater than the target, you can rule out the upper half. This process repeats until the target item is found or the window shrinks to a single (non-matching) item.

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

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

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

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

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

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

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

"I must be thorough," said the prince.

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

"Data? Time?" asked the prince.

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

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

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

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

"The search algorithm," said Alfred.

The prince continued to stare blankly back at Alfred.

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

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

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

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

"There are only three cases to consider:
1) If the glass slipper is smaller than the middle value, you only have to work on the 'smaller' half of the list. Move the 'end' finger to where the middle value is, because all of the entries after the middle are too large to match. The matching size will still be between your two fingers.
2) If the glass slipper is larger than the middle value, you only have to work on the 'larger' half of the list. Move the 'start' finger to where the middle value is, because all of the entries before the middle are too small to match. Again, the matching size will still be between your two fingers.
3) If the middle value matches the slipper's size, you are done. You found a match. Yay."

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

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

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

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

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

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

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

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

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

Alfred stifled back a thousand comments and smiled politely.

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

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

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

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

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

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