Fun With Boolean Statements

A single Boolean expression can often be specified in multiple ways. For example, the expression A AND B is equivalent to the expression NOT (NOT A OR NOT B). One way to test the equivalence of two Boolean expressions is to create a table of every possible combination of the input variables along with the resulting value of the expression. In the example above:

A | B | A AND B

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

F | F | F

T | F | F

F | T | F

T | T | T

And

A | B | NOT ((NOT A) OR (NOT B))

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

F | F | F

T | F | F

F | T | F

T | T | T

Of course, a Boolean expression with N different input variables has 2^N different input combinations. Thus these tables can grow quickly, and it is often preferable to simplify the expressions mathematically.

The children of Bool enjoyed playing a particularly creative (and admittedly annoying) game. They would ask travelers simple questions that were phrased as complex Boolean expressions. They would then watch the traveler struggle to figure out how to answer the question. Usually, some amount of laughter would follow. It was like Bool's own form of logic-based prank calling.

The rules of the game were quite simple:

1) Start with a Boolean expression that asked a reasonable question.*

2) Make that expression as long as possible without changing the meaning.

Of the two rules, the second one was the easiest to follow. Newcomers to the game would dutifully draw out the logic tables for both expressions in order to demonstrate their equivalence. Experience players would produce simple, yet beautiful, proofs using simplification rules.

The first graders in Bool tended to stick with questions using double, triple, and quadruple negatives:

"Are you NOT NOT NOT NOT staying at the inn?" = "Are you staying at the inn?"

Unfortunately, the first graders still almost always managed to confuse themselves. They often had to resort to standing in the middle of the street, counting the number of negatives on their fingers, before deciding whether or not they could laugh at the traveler's answer.

By the time the kids reached second grade, they were using more complex rules, such as:

A AND TRUE = A

B AND FALSE = FALSE

C OR TRUE = TRUE

D OR FALSE = D

This would lead to all sorts of new fun, such as: "(Are you NOT stupid) OR (is the sun hot)?" which was TRUE regardless of the intelligence of the person. However, after being asked that question by a second grader, most travelers tended to feel stupid.

Of all the kids in Bool, Chuck was the best at this game. In fact, he was something of a legend at his elementary school. He had once caused a merchant to sputter in confusion by asking: "Is it really false that you: do not carry chocolate or do not carry gum?" By the time that the merchant figured out that Chuck was asking if he carried both chocolate and gum, Chuck and his friends were already laughing hysterically in the road.

Chuck's personal favorite was De Morgan's law, which stated:

NOT (A AND B) = (NOT A) OR (NOT B)

NOT (A OR B) = (NOT A) AND (NOT B)

In fact, DeMorgan's law led to Chuck's first classic: "Are you NOT (smart OR funny)?" which meant "(Are you NOT smart?) AND (Are you NOT funny?)" Even when someone answered the question correctly, Chuck found their expression hilarious.

Chuck's ultimate masterpiece was a thirty-eight clause phrase that asked about the traveler's path to Bool. It included no less than three different applications of De Morgan's law.

Thus it was much to Chuck's dismay when Ann passed through the town of Bool. Chuck sprung the question on her as she was finally leaving the town. He held is breath as he finished, waiting for the confused look that would ultimately prove him the master of complexifying Boolean expressions. Instead, Ann looked back at him and answered simply: "Yes. That is TRUE."

She waited for a moment to see why he had asked her an odd question. Then, after realizing that there was no followup question, Ann turned and continued her journey.

Chuck was devastated. He immediately went home and started work on a new, 50-clause, expression.

* "Reasonable" was much debated term and often led to hour long arguments. This matter was usually decided by a vote of the kids standing nearby or, in the case of ties, by a game of rocks-paper-scissors.

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

For more Boolean fun, read about Ann's visit to the town of Bool.

Data Validation, Marcus, and the Cheese Minstrel: Part 1 of Marcus and the Cursed Cheese

Data validation is an important practice to ensure the security and robustness of a program. In short, data should be checked to confirm that it is valid (e.g., no null pointers), non-malicious (e.g., no escape characters in input strings), and of the expected form. Data input into the program should be validated to prevent invalid or malicious data from causing undesirable behavior. Even within the program, data coming into functions should often be validated to protect against accidentally passing a bad value.

It was by pure chance that the wizard Marcus ran into the Minstrel of Cheese. To be certain, the Minstrel of Cheese did not look like a typical minstrel. He was wearing a shabby, bland outfit that was covered with numerous patches. He was sitting against a large oak tree, and there was no sign of a musical instrument in the immediate proximity. In fact, the only object the minstrel appeared to have with him was a very large block of cheddar cheese.

"Excuse me." started Marcus. "I am trying to find my way to the Castle of Cheswick. Would you happen to know the way?"

"It is not a real castle, you know. It is a cheese factory." responded the minstrel.

"Yes. I am aware of its function." answered Marcus. "What I am not aware of is its location."

"Why do you want to go there?" inquired the minstrel.

"Is this a test?" asked Marcus. He was suddenly suspicious. In his experience, only trolls asked random travelers this many questions; and questions from trolls rarely ended well.

"No." answered the minstrel with a long sigh. "I am just curious. You see, I am the cheese minstrel. I am commissioned to tell stories about cheese. So I am naturally interested in anything to do with Cheswick Castle."

"A cheese minstrel?" asked Marcus in disbelief. "I have never heard of such a thing."

"We are not exactly the most highly regarded minstrels in our community." answered the minstrel. "We do not get to sing about knights, dragons, or epic tales. It is actually rather demoralizing. But that is what I get for partying during minstrel school. My mother always told me to take it more seriously, but I didn't listen. Now, I am working on a song about cheddar." the minstrel waved weakly in the direction of his large block of cheese.

"I see. I am sorry to hear that. But I really am in a hurry. Can you tell me where Castle Cheswick is?" Marcus prompted.

"Are you on an important mission?" asked the minstrel with a gleam in his eye. "There are not many important missions that involve cheese factories."

"Yes. I am." answered Marcus. "I believe that there is something foul going on at Castle Cheswick."

"Oh…" The Minstrel sounded disappointed. "That is probably just one of their new varieties. Some cheeses smell stronger than others."

"That is not what I meant. I recently received cursed cheese." explained Marcus.

"Cursed cheese?" asked the minstrel. "I am not familiar with that type."

"It is not a type of cheese. It is a cheese with a curse on it." replied Marcus. "A very particular type of curse that targets wizards with knowledge of computational spells. It is a subtle curse too -- easy to hide in something strong like bleu cheese."

"Then how did you find it?" asked the minstrel. From the minstrel's body language, it was obvious that this conversation was the most exciting thing to have happened to him in the last five years.

"I validate all my food, of course." stated Marcus. "Every good wizard should. Although, admittedly, too many get lazy."

"Validate?" asked the minstrel. "Do you mean you sniff it to make sure that it is not spoiled?"

"I am a little more thorough than that!" proclaimed Marcus. "It can be a big problem if the food that you get is not what you are expecting. You need to validate it. I have caught many problems in the past with my groceries, including:

- the wrong type of food (apple butter instead of peanut butter),

- food containers that are empty,

- expired food, and

- now, cursed food.

But this is the first time that I have seen a spell this well designed."

"So these problems were all intentional?" asked the minstrel in awe. "You must be very important to have so many people trying to mess with your food."

Marcus would assume that the topic of validating one's food would be standard knowledge for someone who spent his life sing epic songs about cheese. But the minstrel seemed to be hearing all of this for the first time.

"Of course it is not all intentional." answered Marcus. "The problems fall into a few categories. There are certainly cases where people do send malicious food, such as cheese with a hidden curse. But there are also other cases, such as getting the wrong food due to a miscommunication or an error on the grocery store's part."

"I remember this one time where I asked for a delivery of twenty loaves of rye bread. They gave me thirty loaves of whole-wheat. What a mix up!" Marcus chuckled.

The minstrel looked confused. "You just said that someone had cursed your cheese and now you are laughing about the wrong type of bread? That sounds like two different problems to me."

Marcus shrugged. "Two different problems, but the same point: you have to validate you input."

"And there is also the related problem of validating the inputs to recipes that have subcomponents." added Marcus. "Even though you have control of the inputs does not mean that you do not have to check them. For example, you always need to check that you made the pizza dough correctly before making the full pizza. I once had an apprentice that did not check her dough, and the entire pizza fell apart in the oven. It took her three hours to clean up the mess."

"And then there was incident with the undercooked pasta." continued Marcus.

"To the north." interrupted the minstrel.

"Huh?" asked Marcus. He had been enjoying explaining the concepts behind food validation.

"Cheswick castle is to the north." explained the minstrel. He paused for a moment. "Can I come with you?" he asked.

"Why on earth would you want to come with me?" asked Marcus. "Didn't I just mention the cursed cheese?"

"You are on an epic adventure to find out who placed a curse on your cheese. It is the opportunity of a lifetime for a cheese minstrel like myself."

"Well... Alright." agreed Marcus. It was not possible to argue with that logic. Where else was a cheese minstrel supposed to go?

The minstrel beamed as he collected his block of cheese and prepared to follow Marcus. Together the two of them set off toward Cheswick Castle.

To be continued in Part 2: Objects, Encapsulation, and Cheese Factories...

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

For more practical tips, also see: how Marcus teaches the Importance of Unit Testing Magic Spells, the problems that can arise from forgetting Variable Initialization in Busy Kitchens, or the Importance of Good Comments in Bread Recipes.

The Importance of Good Comments: A Tale of the Baker's Apprentice

Comments are additional text within code that provide explanation. Comments can greatly improve the readability of code by providing insight or summarization. For example, a clear comment before a large block of numeric statements might simply explain "Solve a*x^2 + b*x + c = 0 for x", allowing the user to understand exactly what the following block of code is meant to do.

As part of his world renowned teaching program, the famous baker Breadtista insisted that each apprentice thoroughly document his or her work. Thus, apprentices created a reference that would live beyond their apprenticeship. All recipes, tips, and tricks would be clearly documented. Breadista strongly believed that such a resource provided his apprentices with a significant advantage.

As Breadtista was fond of pointing out, the key to a great recipe was capturing the perfect amount of information. Where other bakers wrote recipe books filled with lists of bland instructions, such as: "Add two eggs and blend well", Breadtista insisted on commenting his recipes. These comments added context and explanation.
Here is an excerpt from Breadtista's famous eight-chili strawberry muffins:

Step 5: Cut the strawberries into cubes of 1cm per side. [This size allows the flavors to blend while preserving the fruit's texture.]

Step 6: Add the strawberries to the dough.

Step 7: Gently stir until the strawberries are mixed into the dough.

Since comments were not part of the instructions themselves, Breadtista clearly denoted his comments with braces [] to avoid confusing other bakers.

Further, Breadtista insisted that all comments provide meaningful information to the recipe itself. He hated recipe books by famous castle chefs that contained thirty page digressions of the author's lifelong quest for the perfect pancake. It was especially egregious if the recipe then produced chewy pancakes. Pancakes were not meant to be chewy, and comments were not meant to be life stories.

Despite his firm belief in the importance of good comments, Breadtista found it difficult to explain this philosophy to each new apprentice. Every year, he heard the same arguments:

• "Why should I comment? The only people reading this are bakers, and they should already know this."
• "I won't forget why I did that."
• "Isn't that step obvious?"

And every year, he repeated the same answers:

• “Just because it is obvious to you, does not mean that it will be obvious to others."
• "Just because it is obvious to you now, as you are writing the recipe, does not mean that you will remember it."
• "If it is so obvious, why did I have to draw you an example on the chalk board? Twice?"

Each year, after lecturing on the importance of clear comments, Breadtista would have at least one apprentice who took the idea too far. For example, one year he had an apprentice who wrote the following instructions for making simple bread:

Step 1: Measure out 1/4 of an ounce of yeast into a small bowl. [We put it into a bowl so that we can add water in step 2 to activate the yeast.]

Step 2: Add two table spoons of warm water to the bowl with the yeast. [We add the water to the bowl in order to activate the yeast.]

Step 3: Wait 5 minutes. [We wait 5 minutes in order to allow the yeast to activate in the water].

Breadtista never made it past step 85 in that recipe. He "accidentally" spilled a full pitcher of water over the apprentice's parchment so as to spare anyone else from reading it.

It took ten years of trial and error, but eventually Breadtista found the perfect way to reinforce the importance of GOOD comments. The first three weeks of each apprenticeship, Breadtista would make each new apprentice work from the worst notes of previous students. Although it meant that he would now hear cries of "WHO WROTE THIS?" and "BUT WHAT DOES IT MEAN?" from the kitchen, this process saved him from having to repeat the same reasoning over and over.

Nothing reinforces the concept of understandable, well documented recipes more than having to read other people recipes.

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

If you are interested in learning more about writing good code, check out: The Importance of (Variable) Names or The Importance of Unit Testing Magic Spells.

The Game of Hamiltonian Paths: Part 9 of Ann's Visit to G'Raph

A Hamiltonian path visits each node in a graph exactly one time. The problem of determining whether a graph has a Hamiltonian path is NP-Hard.

"Mister Mayor, I think that there is a wizard casting spells on the scholars of G'Raph," Ann repeated. "Everyone to whom the wizard has spoken became obsessed with finding a polynomial solution to a specific NP-hard problem. Have you heard any stories about a stranger in a dark cloak asking scholars NP-hard computational problems?"

The mayor looked confused. "NP-Hard? I am not exactly sure what that means, but I had a man in a dark cloak ask me a hard question once."

"You did?" asked Ann, Edgar, and Florence in unison. None of them could hide the shocked looks on their faces.

"Yes," answered the mayor. "It was about twenty years ago -- right after I left school. He had just come from the library. I think he stopped to talk to Geoffrey about some salesman problem. Geoffrey was my favorite teacher, you know. He would always have the easiest tests. Anyway, the man asked me if I could solve a game: Find a path through G'Raph such that I go through each island at most one time."

"The Hamiltonian Path problem," stated Ann. "It is also NP-hard."

"It is related Geoffrey's traveling salesman problem," added Florence.

"But why did the wizard ask you about Hamiltonian paths?" Ann asked, trying to phrase the question tactfully. From her limited time with the mayor, he had yet to strike her as one of G'Raph's great scholars.

The mayor shrugged. "I don't know, but it sounded like a fun game."

"It is a popular game in G'Raph," Edgar agreed. "We played Hamiltonian paths as kids. We would draw out different hopscotch graphs and have to traverse them in Hamiltonian paths. Of course you were not allowed to solve them ahead of time. You had to determine the Hamiltonian path as you were hopping. If you got stuck or stepped on the same node twice, you were out."

Ann looked skeptical. "You really played that as a kid? That was how you spent your childhood?" she asked.

Edgar smiled at the fond memory. "Those were good times,” he answered.

"What did you say to the wizard?" Ann asked the mayor. "You did not solve it, did you?"

The mayor smiled. "I sure did. I told the man in the cloak: 'That's easy. I would just build a few more bridges.' The man left shortly after that. I think he said something about my future as a politician."

"That is cheating," objected Edgar. "You cannot add bridges in a game of Hamiltonian paths!"

"Mister Mayor," interrupted Ann. "Do you know anyone else who met the wizard?"

The mayor thought for a moment. "Not here in G'Raph. But I had an intern that told me a story that sounded similar to what you are claiming. He had a good friend in the town of Bool who became obsessed with one of these hard problems. What did you call them? NT? ND?"

"NP," offered Ann.

"Sure. Sure. Anyway, my intern's friend had a fun little problem called 3-SAT or something like that. Sounded like the type of thing you would find in the Sunday paper."

"The town of Bool? Are you sure?" asked Ann.

The mayor nodded. "You always know a Boolean when you meet one," Ann could not agree more.

After a few more minutes of discussion, Ann decided that she was not going to find any more answers here. She knew that there was a wizard that was casting spells on computational scholars; now she had to figure out why.

For the first time in her quest, Ann knew where to go next. She needed to pay a visit to the one place where she might find more information about NP-hard problems -- the library of Alexandria.

Read Ann's visit to G'Raph from the beginning with Part 1: The City of G'Raph. Or read about Ann's first (and highly unpleasant) visit to the city of Bool.

Minimum Spanning Trees, Prim's Algorithm, and Bridge Upgrades: Part 8 of Ann's Visit to G'Raph

The minimum spanning tree of an undirected graph is the smallest set of edges such that all of the nodes are connected (if possible). Similarly, in a weighted graph, the minimum cost spanning tree is the set of edges with the minimum total weight such that they connect all of the nodes.

Ann went straight to city hall, where she hoped to find more information about the mysterious wizard. Florence and Edgar decided to join her. Or, more accurately, they decided to demonstrate how fast they could navigate G'Raph on their scooters. At least they left their map with Ann.

Ann found the mayor in his office, staring intently at a map of the G'Raph.

"Mayor, I have an important question for you," started Ann.

The mayor did not acknowledge her. He continued to stare at the map, mumbling to himself. Ann started to panic. Had the wizard been here?

After a moment, the mayor finally turned. "Edgar, this will never do. You need to redo it," he snapped.

"What?" asked Edgar. "That is exactly what you requested: the minimum weight spanning tree."

"The what?" asked the mayor with a confused look.

"Umm… I have an important question here," tried Ann, but nobody was paying attention.

"It is the set of bridges to upgrade," Florence explained to the mayor.

The mayor stood silently, not making the connection.



Florence continued. "You asked for the cheapest set of bridges to upgrade such that you could travel between any two islands by only crossing stone bridges. Since the price is determined by the length of the bridges, we found the shortest set of bridges."

"Why would you need to connect all the islands with stone bridges?" asked Ann, forgetting her original question for the moment.

"Nobody wants to be stuck at the dry cleaners after a dragon attack," offered Florence without additional explanation.

"We need a stone bridge between city hall and the library," said the mayor.

"That would add another 3 meters," countered Edgar. "It is cheaper to connect the inn and the dry cleaners." He pointed to the relevant bridges on the map to illustrate.

The mayor started to argue, but Ann cut him off.

"Interesting," interrupted Ann. "You found the set of bridges to replace that will connect all the islands together, while minimizing length. Did it take you long?"

"No," answered Florence. "I used Prim's algorithm.”

“Prim’s algorithm?” asked Ann.

“It is relatively simple algorithm,” said Florence. “You start with a random node, and add it to a new set of connected nodes. In this case, I 'randomly' chose the library.”

"Then you keep adding the closest node that is not already in the set. Here we first add the inn..."

"Then the brewery..."

"All very fascinating," interrupted the mayor. "But the library and city hall should have a new stone bridge between them."

"Edgar and Florence are correct," said Ann. "The lowest cost spanning tree does not have a new bridge there."

"But... I walk that way every day," said the mayor. "I am tired of the wobbly old bridge. We need something new."

Edgar, Florence, and Ann all looked at each other in silence. Edgar took a deep breath to start another algorithmic argument, but thought better of it. It was obvious that an algorithmic argument would not sway the mayor. Edgar decided to submit both prices and let the mayor choose.

Ann remembered why she had gone to the mayor's office in the first place.

"Mister Mayor, I think there is a wizard casting a spell on the scholars of G'Raph,” Ann blurted out. “I think the city and all of its scholars are in danger."

Behind Ann, Edgar and Florence gasped in unison.

To be continued in Part 9: The Game of Hamiltonian Paths.

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

Follow Ann's visit to G'Raph from the beginning with Part 1: The City of G'Raph.

Also check out the new illustrations in Bullies, Bubble Sort, and Soccer Tickets and Linked Lists, Kindergarten, and Ocean Voyages.

Panicked Depth First Search: Part 7 of Ann's Visit to G'Raph

Depth first search is a search algorithm that fully explores a single path before backtracking to test other paths. The algorithm operates in a recursive way, first exploring all of the options down one subpath before considering other subpaths. For example, on a graph the algorithm will explore the neighbors of a neighbor before returning to original node to test other direct neighbors. Unlike breadth first search, which uses a queue based approach to track unexplored states, depth first search uses an approach based on a stack.

Ann realized that she had made a critical mistake almost as soon as she left the library. In her rush to get to the school, she had neglected to bring a map with her. In any other town, this would not have been a major problem -- she would just run in the general direction of the school. But finding your way around in G'Raph was not that simple.

Ann stopped when she reached Thomas's farm. There were two paths in front of her, and she was not sure which way led to the school. She looked around for the farmer, but Thomas was not in his radish patch.

Making a quick decision, Ann chose the path out of Thomas's farm that was on her right. She ran over the bridge, and found herself at the local pottery kiln. An assortment of bowls were lined up outside the kiln. Judging from the quality of craftsmanship at least a few of the bowls must have been made by third graders at the school. Ann hoped that she was getting close.

Now Ann had another decision to make -- two new paths led away from the kiln. Again Ann chose the path to her right, and she ran over the bridge. This time the result was less promising. Ann had come to a dead end. She was on an island that appeared to be a mud quarry. There were no new bridges that might take her to the school.

Ann backtracked quickly, returning to the pottery kiln island.

She then ran down another bridge, arriving at a carrot farm. It was another dead end.

Ann backtracked to the pottery kiln again. This time there were no more paths to take, so she backtracked further. She returned to Thomas's farm. From the farm, she took the other bridge and arrived at another (smaller) radish farm. From the looks of it, this farm was decidedly less successful than Thomas's farm. Ann paused for the briefest moment to wonder what could cause the difference in radish growing performance between two almost indistinguishable islands of mud. Maybe it had something to do with crop rotation strategies.

Yet again, Ann was faced with a choice of bridges. She started with the path to her right. Much to her relief, this bridge led directly to the school.

Ann ran up to the school. Florence and Edgar were already there. Their scooters were parked nearby, and Edgar held a folded map of G'Raph in his hand. Ann cursed herself again for not having brought a map. She could have saved a lot of backtracking.

"You made it!" exclaimed Edgar. "I was afraid that you would get lost without a map."

"I did get lost." admitted Ann. "Or at least, I hit a few dead ends and had to backtrack."

"Ah… a depth first search." noted Florence. "Nice."

"Depth first search?" asked Ann. She was still a little out of breath from all the running.

"Depth first search is when you keep exploring along one path until you hit either a dead end or a node that you have seen before. Then you backtrack to the most recent decision point and try a different option. If there are no new options at that point, then you backtrack again." explained Edgar.

"Think about searching a binary tree." suggested Florence. "With depth first search, you keep exploring deeper and deeper until you come to a dead end."

"Or find what you are looking for." added Edgar.

"Yes. Good point." replied Florence. "You can also find what you are looking for. Edgar, remember that time we used depth first search on that choose your own adventure novel?"

"Fun times." answered Edgar.

Ann just nodded. She was too tired to appreciate the algorithmic beauty of her own frantic run. A map would have saved her from having to experience depth first search first hand.

The school's principal, having seen the group standing outside, came out to see what was going on.

"Have you seen a strange man in a dark cloak?" asked Ann without bothering to introduce herself.

"Umm… yes. Why do you ask?" asked the principal.

"Did he talk to anyone?" asked Ann, ignoring the principal's question.

"Yes. He talked with one of our star students, Elizabeth. He had some question about some sort of math problem." answered the principal. "I was there too, but honestly could not understand what he was talking about. Elizabeth seemed certain that she could figure it out though. She went right home to work on it. She is very bright, you know. Probably the best scholar that our school has ever taught. She will find the answer."

"Do you know what the question was?" asked Ann.

"It was something about islands and bridges. I think he called it 'vertex covering'. I had not heard of it before, but it sounded like fun."

Ann felt her stomach drop. She was familiar with the vertex covering problem from her own time in school. Like the traveling salesman problem, it was unknown whether the vertex covering problem had an efficient solution. The problem fell into a class of NP-hard problems.

Unless Ann missed her guess, Elizabeth had just fallen victim to the same spell as Geoffrey. G'Raph High School's star student was a risk of becoming unnaturally obsessed with a single NP-hard problem.

So far, the wizard had targeted two star scholars. Unfortunately, Ann had no idea why.

To be continued in Part 8: Minimum Spanning Trees, Prim's Algorithm, and Bridge Upgrades...

Follow Ann's visit to G'Raph from the beginning with Part 1: The City of G'Raph.

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

Find out more about breadth first search in: Breadth First Search and the Search for the Pig Thief.

Or find out about stacks and queues in: Stacks, Queues, Priority Queues, and the Prince's Complaint Line.

The Traveling Salesman's Problem: Part 6 of Ann's Visit to G'Raph

The traveling salesman problem is a route planning problem. The goal is to find the shortest path through a graph that visits each node exactly one time and returns to the starting node. The problem is also a classic example of a class of computational difficult problems, called NP-hard. There are no known efficient solutions (polynomial time) for solving NP-hard problems, and it has yet to be determined whether or not such a solution even exists.

Ann looked at the depressed scholar in the corner. "You have been working on the same problem for twenty-five years?" she asked.

"I am so close," he answered.

Behind her, Florence and Edgar had stopped arguing. They peeked their heads around the stack of books.

"Oh. I see you met Geoffrey," said Edgar. "Never mind him."

"I want to hear more about this problem," stated Ann. "What do you mean by shortest path?"

Geoffrey did not answer. He was hunched over his paper and mumbling to himself.

Ann turned back to Edgar and Florence. "You just told me about a shortest path algorithm,” she said.

"This is different," explained Florence. "The traveling salesman problem is a particularly difficult path planning problem. The goal is to find the shortest path through a graph that visits each node exactly once and returns to the starting node."

"Here are two example paths through G'Raph's school neighborhood," offered Edgar, drawing a crude sketch on a nearby blackboard.

Path 1

Path 2

"Both paths cross each node exactly once. Path 1 has a distance of 55 meters, and path 2 has a distance of 66 meters," he explained.

"That seems simple enough," commented Ann. "There is really no algorithm to solve it? Why not try all possible orderings of nodes? For each ordering, you could compute the total distance traveled if you visited the nodes in that order."

"There is no known efficient algorithm to solve it," explained Edgar. "No polynomial solution at least. The method you suggested would work, but it is factorial. You have to look at N! different orderings. For the 5 nodes in our simple example, there are 5! = 120 different permutations."

"Polynomial solution?" asked Ann.

"An algorithm where the running time scales polynomially with the size of the problem -- O(N^k) for some fixed value of k. For example linear algorithms O(N), quadratic algorithms O(N^2), and cubic algorithms O(N^3) are all polynomial. But the algorithm you suggested is O(N!); it scales as the factorial of N." Edgar explained.

Florence shrugged. "No one actually knows if there is an efficient solution or not. At least no one has found an efficient solution yet. There are good approximations and reasonable heuristics, of course, but no polynomial time algorithm."

"I played with it for a while," offered Edgar. "I never made much progress."

"Geoffrey has been working on it for twenty-five years?" asked Ann.

Both scholars nodded. "Ever since he met that man, Geoffrey has been unnaturally obsessed with this problem. He does not think about anything else. In the past, he would work on 3 or 4 different problems at the same time. It is as though he is under some sort of spell." Edgar explained.

Edgar's words sent a shiver through Ann. A vague memory floated through the back of her mind, but she was unable to latch onto it.

"Has anyone else met that man?" Ann asked.

Edgar shrugged. "I do not think so. Geoffrey said that he was probably a visiting salesman."

"He was selling questions," Geoffrey said quietly. Ann jumped at the sudden statement. Even though she had spoken to him only a minute ago, she had forgotten he was there.

"What did he look like?" asked Ann. The undefined memory continued nag at the back of her mind. She was miss a connection.

"Dark cloak and a large wooden staff that was covered with mathematical symbols," answered Geoffrey. "Never did see his face though."

"You only saw him that on time? Twenty-five years ago?" she confirmed. Why should an event from twenty-five years ago strike any memories with her?

"Three times," answered Geoffrey. "The first time was twenty-five years ago. Then, I saw him again ten years later. I was about to give up on the problem, but he found me and asked if I had solved it. That question rekindled the fire. I knew I could find a solution."

"And the third time?" asked Ann. She could feel a pit of fear building inside her, but she was not sure why.

"This morning," mumbled Geoffrey. "As I walked by the school, I saw him talking to some girl. He stopped for a moment and waved with his staff. I still have not found a solution yet, so I kept walking. I know I can find one. I am so close."

Ann did not wait for the rest of the story, she ran out the door and toward the school.

To be continued in Part 7: Panicked Depth First Search…

Follow Ann's Visit to G'Raph from the beginning with Part 1: The City of G'Raph.

A Disagreement Over Data Structures: Part 5 of Ann's Visit to the City of G'Raph

Graphs can be represented by a variety of data structures. Two common representations are: adjacency matrices and adjacency lists. Both data structures can handle directed, undirected, weighted, or unweighted edges. An adjacency matrix represents a graph as a matrix -- with one row and one column for each node. The matrix value of row i, column j is the weight of the edge from node i to node j (or 0/1 for unweighted graphs). An adjacency list maintains a separate list of neighbors for each node.

Ann had obviously touched upon a controversial question. Florence and Edgar stood on opposite sides of the room glaring at each other. The question had seemed innocent enough. "Do you always represent graphs with these illustrations?" Ann had asked.

Florence had quickly answered. "No. Those are only for illustration. Adjacency matrices work better."

And Edgar had snapped. "No. The correct answer is that adjacency lists are the preferred tools."

Then the glaring had begun.

"What are adjacency matrices and adjacency lists?" asked Ann, starting with the most basic question. Both scholars immediately rushed to explain their data structures. The resulting sound reminded Ann of two chipmunks fighting.

"One at a time, please." Ann pleaded. "Florence, why don't you start with adjacency matrices?"

Florence smiled. "They are very simple. Every row represents a node and every column represents a node. If there is an edge between two nodes, you put their weight in the corresponding element. So M[i][j] would store the weight of the edge from node i to node j. Here is an example of some of the islands of G'Raph."

"Adjacency matrices are wonderful." continued Florence. "See how it puts all of the information into a single convenient form. They are very simple representations. And you can perform a bunch of computations by just multiplying the matrices."

Ann nodded. It seemed sensible enough.

"Why aren't there ones along the diagonal? Obviously you can get from the library to the library." asked Ann.

"Depending on what you are trying to represent, self edges (or loops) can certainly make sense. In this case, I am only representing the existence of bridges. And there is no bridge from the library to the library." explained Florence.

"Okay. Now Edgar, can you tell me about adjacency lists?" asked Ann, turning to the other scholar.

"Certainly." started Edgar. "You start with a list of each node in the graph. Imagine a giant array or linked list with the name of each node in it. Then for each of those nodes, you keep a list of all the nodes to which it connects. For graphs with a few edges, it can use a lot less memory. You only store the edges that are there Here is an example."

Ann studied the example. "Both forms can represent the same graph exactly, correct?" asked Ann. Both scholars nodded,

"And both forms can do directed graphs as well?" asked Ann. Both scholars nodded.

"And they can both represent weighted edges?" asked Ann. Both scholars nodded.

"Then why are you fighting? It seems like they both do the same thing, but have different advantages. A matrix is simpler to specify, and a list can take less space. Is that really worth fighting over?" asked Ann. Both scholars nodded.

"Space matters!" cried Edgar. "Have you ever tried using your precious matrices to represent the entire pigeon network, Florence? There are thousands and thousands of nodes!"

"Simplicity matters too!" answered Florence "I can traverse my matrices with two fixed size FOR loops. You need to iterate over lists of different size. I have seen your implementations… they have POINTERS!"

"Better to have pointers than a row with ten thousand useless zeros!" responded Edgar.

The argument was getting heated. Ann backed away from the two scholars. She was afraid that one of them would eventually throw a coffee mug.

Then Ann heard a low sigh from the corner of the room. Turning away from the argument, Ann peaked around a very large stack of books. There, at a tiny desk in the corner, was the most depressed looking person that she had ever seen. He hunched over his desk, staring at a single sheet of paper on his desk and shaking his head.

"Hello?" Ann asked.

The man looked up at her blankly. "Both data structures are completely reasonable in their own way." he explained without bothering to introduce himself.

"I can see that." Ann confirmed. "I think they both have advantages and disadvantages."

The man just nodded. "I wish they would see that. They make such a terrible racket when they argue. I have important work to do, you know."

"I see. Can I ask what you are working on?" asked Ann.

"It is not done." he answered. "I have not figured it out yet."

"Oh. What is the problem, then?" Ann probed.

The man did not answer for a while. Behind her, Ann could hear Florence shouting something about invertability. Ann tried to ignore the argument.

Finally, the man gave Ann a sad look. "It is a really simple problem. I do not know why I have not been able to come up with a good solution. It really is quite simple. I just want an algorithm that will give me the shortest path through a graph such that the path visits each node exactly once."

Ann thought about this for a second. "Sounds like a good problem." she offered.

The man nodded. "I have been working at it for a while without any success. It all started a long time ago, when a man in a dark cloak first told me about the problem. I think he might have been a traveling salesman. I never did see his face though. He just told me that he had a problem that he needed the best scholar in G'Raph to solve. I was young and naive. I told him that I would have an efficient algorithm by the end of the week… that was twenty-five years ago."

To be continued in Part 6: The Traveling Salesman's Problem...

Follow Ann's visit to G'Raph from the beginning with Part 1: The City of G'Raph.

-------

To learn more about matrices see Users, Peanut Vendors, and Matrix Indices.

To learn more about linked lists and arrays see Arrays, Linked Lists, and Zed's Coffee Shop or Linked Lists, Kindergarten and Ocean Voyages.