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.

Amoebas Having Boring Family Trees

Trees are computational data structures used for storing and searching data. Data is stored at tree nodes. Each node can also contain a link to zero or more "children" nodes. These links can be used in a search algorithm to traverse the tree. Correspondingly, each node may have up to one "parent" node. Only one node in the tree, the "root" node, does not have a parent node.

Abby's class project was due tomorrow morning, and she was still not sure what she was doing wrong. As she looked at her paper, panic began to set in.

The example family tree that her teacher had given her showed a clear network of nodes. There were levels for grandparents, parents, and siblings. But, Abby's tree did not look anything like that. Sometimes, being the only amoeba in her second grade class made life complicated.

Being an amoeba, Abby's family worked differently from those of her classmates. Instead of having two biological parents, she had exactly one. She was born through mitosis, when her parent had literally split in half to form her and her sister Venn. So, Abby's tree started at a single grandparent and branched out as it went down. Each parent could have exactly zero or two children, and each child had exactly one parent node. It was a perfect binary tree. Unfortunately, it looked nothing like what the teacher would be expecting.

On the plus side, Abby found it remarkably easy to trace her lineage back for centuries. Each amoeba on her family tree could have only one parent. Thus, she could follow her family all the way back to her great, great, great grandfather, "Sir Edward the Adventurous", who had been the first amoeba to colonize this particular petri dish. And starting at her great great grandfather, she could search down through the layers and find out how she was related to any other amoeba in the whole dish. But, none of that helped on this class project.

Abby carefully finished labeling her tree. She had one grandfather who had two children: her father and her aunt. Her father then had two children: her and Venn. And her aunt also had two children. All three generations formed only seven nodes on the tree.

Discouraged, Abby gave a bubbly sigh of despair as only amoebas can. She only hoped that her teacher would understand.

Epilogue: Abby actually received double credit for her assignment after she launched into a impromptu 30 minute monologue on the wonderful computational properties of her family tree. First, she described how she could determine the exact relationship to anyone in her family in O(log N) time regardless of the number of generations included. Then, seizing the moment of inspiration, she noted that her family tree was in fact a heap sorted by age. Each amoeba in the tree could have up to two children and the ages of both children were strictly less than that of their parent. Her descriptions were so inspiring that the entire class gave her a standing ovation.

.

Binary Search Trees and Speck the Spider

Binary search trees (BST) organize data to allow efficient searches by value. Data is stored in tree nodes. Each tree node also maintains pointers at most two children nodes: a left child and right child. The tree maintains the property that at each node values in the left subtree are less than the value of the current node. In contrast, values in the right subtree are greater than (or equal to) the values in the current node. This structure allows an efficient search by walking down the tree and branching in the direction of the value for which you are looking. A balanced binary search tree allows O(log N) search.

Speck was a spider. As such, he lived a typical spider lifestyle. He built webs, ate flies, and enjoyed discussing the weather with his neighbors. In fact, for those who had never been to visit his web, he seemed like a perfectly normal spider.

However, the truth was, Speck was not a typical spider. He was obsessive about his food choices and demanded a level of variety that was unheard of for other arachnids. Speck insisted on keeping a supply of at least 25 different types of bugs in his web.

Speck also insisted on absolute organization in his food supply. What good was 25 varieties of bugs, if he could not quickly find the one that he wanted? While most spiders kept their bugs distributed randomly throughout their webs, that prospect seemed absurd to Speck. He loathed such disorganization. Instead, like any rational chef, Speck organized his food choices in alphabetical order.

The result of these preferences was a new type of web design that Speck developed through long days of trial and error. He called it a binary search web. The web consisted of nodes, clusters of webbing that stored his bugs, and strings of web between the nodes. The whole thing was organized vertically. At the top was a single "root" node attached to an old storm gutter. Each node in the web could have at most two "children" nodes below them. These nodes were attached securely to their parent node above using a strong strand of webbing. As a result, the web branched out wider as it progressed downwards, taking on a vaguely triangular shape.

In order to maintain his organizational structure, Speck insisted that the bugs stored at each node obeyed a particular alphabetical ordering. Specifically, the bugs in all of the nodes down the left-hand path from a given node had to be BEFORE the current node's bug in alphabetical order. Similarly, all of the bugs in all of the nodes down the right-hand path from a given node had to be AFTER the current node's bug in alphabetical order. This way, Speck could quickly find any bug that he was looking for by simply descending the web.

For example, one morning Speck decided that he wanted a fly for breakfast. He started at the top of his web, where he slept, and examined the bug there. It was a lady bug. Since flies come before lady bugs, Speck sleepily walked down the thread on the left-hand side of the node. On his way he paused for a drink of dew that had collected during the night. At the next node, Speck found a beetle. Since flies come after beetles, Speck now chose the right-hand path. There he found the three day old fly. Speck happily ate his breakfast and then decided to take a mid-morning nap.

The advantage of the branching structure of the web is that, as long as he kept the structure well balanced, Speck could find any bug that he was looking for in O(log N) time. What this meant was that Speck could double his inventory of bugs while only adding one additional step to his search! Given that Speck only did his searches when he was very hungry, this efficiency was important. He had heard his friends claim that they just ate whatever bug was closest. Imagine that!

The web also leant itself to the addition and removal of bugs. Adding a new bug simply consisted of walking the bug down the web (while making the correct alphabetical branches) until he hit a dead end. Then he would add a new child node, with the new bug, to the correct side of the current node. Adding a new node just meant spinning some webs, and Speck enjoyed that part of being a spider a lot. As he saw it, making webs was definitely the best part of being a spider.

Sadly, despite the obvious advantages of the binary web structure, Speck never managed to encourage wide adoption. Instead, his friends stuck with the classic circular patterns, citing their ascetic value.

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

For more information on tree data structures, see why amoebas have boring family trees.

Stacks, Queues, Priority Queues, and the Prince's Complaint Line

Stacks and queues are very simple, yet fundamental, data structures in computer science. Simply put: they store data. You put a piece of data in the stack or queue, go about your business and later take that piece of data out. Where they differ is in how they order the data that is extracted. Stacks are last-in, first-out data structures that return the most recent data inserted. Queues are first-in, first-out data structures that return the least recent data inserted. And priority queues return the highest priority data inserted (accord to some priority value). Understanding these ordering effects is the key insight into understanding how these data structures can effectively be used.

Before he became king, Prince Fredrick had a tradition of hearing his future subjects' complaints every Tuesday in the great room. At 10 am the doors would open, and his loyal subjects would fill the room to raise their complaints. On days that he was feeling particularly generous, Prince Fredrick would even task his steward with addressing some of the complaints. However, on most days Fredrick felt that he had done his part by just listening and he would promptly forget everything that was said.

By 6 am every Tuesday a great crowd formed outside the doors to the Hall of Complaints. In fact, farmers with particularly pressing concerns camped out for days or weeks hoping to be near the front of the crowd and thus be selected to discuss their complaint. The fact that their complaint would likely be ignored did not dampen their resolve. They needed to be heard.

Fredrick never gave much thought to what happened before the doors opened. After all, he was the prince. Why should he care about what happened outside of his room?

Then, Rok the Dragon arrived. In early June the dragon started burning crop fields and eating the livestock -- typical dragon activities. However, Fredrick continued to use his system, selecting the subjects from the front of the room.

In late July, Fredrick finally selected a farmer who was there to talk about the dragon. "What is your complaint?" asked Fredrick.

"A dragon ate my farm." the farmer replied.

"A dragon?" Fredrick screamed. "We must act now before it destroys a second farm!"

Silence followed Prince Fredrick's proclamation.

"What is it?"

Fredrick

asked, but nobody responded. Fredrick singled out another farmer and directed the question at him.

"It is just... Well... The dragon has destroyed over twenty farms since it arrived here in June. My farm was actually destroyed six weeks ago."

"Then why am I only hearing about it now?" screamed the prince.

"Noble sir, I have been lining up for six weeks to discuss the dragon. It is only today that you gave me an audience." answered the second farmer.

"How many others are here to talk about the dragon?" inquired the prince. Half the people in the room raised their hands. The prince screamed at everyone in general. Eventually he calmed down enough to send his best knights to run the dragon out of town.

"This will never happen again." the prince vowed. "From hence forth there will be a SYSTEM. Each person will write down their complaint and put it on top of a complaint stack. Each Tuesday from 10 am to 11 am I will take the top complaints off the stack and read them. This way I will always hear the most recent complaints."

Everyone in the room looked at each other. They gave a half-hearted cheer. "Yay."

For the next few months life returned to normal and the Royal Complaint Stack worked about as well as the unorganized mob of people in the complaint room. Then Rok returned. On Wednesday he ate one farm and took a week-long nap.

On the following Tuesday the prince read through the first ten complaints on the stack. All ten were about the refereeing at last Sunday's sporting event. The blue team had lost and its fans were unhappy. The prince had an easy solution and told the steward to bet against the blue team next week. Feeling like he had fulfilled his duty to the people, the prince decided to quit early and play some golf.

The prince found Rok sleeping on the golf course. The prince screamed when he saw the dragon. "What is it doing here? Why was I not told?" He threw his golf clubs at his caddy in frustration and stormed back to the castle.

He was still fuming when he got back to the castle. "I should have been told. Why did no one complain?"

"Your honor" started the steward very carefully. Fredrick picked up on his tone immediately.

"Where is the complaint stack?" he demanded. The steward brought in the stack of complaint papers. The prince started to leaf through them. The top eight were something about food poisoning from today's special at some local restaurant. Under those were more complaints about refereeing. Then he found it. Complaint number thirty one on the stack was about the dragon.

"Curses!" he yelled at the stack of papers.

"No more complaining about minor things when there are important problems!" the prince declared.

The steward sighed. "Sir, how will we tell? The people want to be able to complain about what is bothering them."

"Then there shall be a NEW SYSTEM." Everyone groaned quietly.

The prince retired to his study and began working on the new system. It had to let people voice their frustrations. It had to allow the prince to find the most important issues. More importantly, it could not take too much of his time; he really hated dealing with complaints. He spent three weeks in isolation working on his system.

The following Monday, he addressed his subjects. "I have devised a new system: a priority queue. Each of you shall write your complaints on a piece of paper. Every Monday night, the steward shall read each complaint and assign a priority from 0 to 10. We shall then deal with the highest priority complaints first." The prince paused and waited for the applause. A few subjects clapped lack-lusterly. The steward audibly groaned at his new task. He knew quite well that everyone was going to complain to him about the assigned priorities.

And so the kingdom adopted a priority based complaint system. Over time, the subjects embraced this system. The prince went on to become king and guide his kingdom through a period of unprecedented happiness and quick responses to dragons. Everyone in the kingdom was happy... except of course the steward.

Arrays, Linked Lists, and Zed's Coffee Shop

Arrays and linked lists are simple data structures that store multiple values in memory. Where these data structures differ is in how they store and allow access to the data. Arrays are like a set of bins with a fixed number of slots. Their structure makes it easy to read from or write to an arbitrary element in the array. In contrast, linked lists are easily extensible chains of data. However, you must scan to the correct location in the chain to read or modify a piece of data in that node.

One year after Zed opened his coffee shop, business was great. Zed had a devoted set of regulars who bought coffee every morning on their way to the castle. They were mostly bureaucrats, specializing in such jobs as counting the kingdom's cattle or copying maps. They loved their coffee.

Then, one day, a competitor opened shop across the street. Zed started losing business to MegaCup’s low prices and flashy signs. Zed knew he had to expand.

Looking over the books, Zed noticed that he sold a lot of coffee in the morning but almost none at night. None of his customers wanted to be jittery as they headed home and went to sleep. Zed needed a new product -- something he could sell at night.

His supplier told him about a new type of coffee coming from the southern region of the kingdom: “Low Jitter Coffee”. Immediately, Zed knew this coffee would solve his evening sales slump. He ordered eight cases.

Zed needed a way to market his new coffee. The sign outside his store read “Coffee” and did not have room for anything else. After a week of intense thought, Zed ordered a new ArrayDesignBoard menu board for outside his shop. The board had four slots where you could slide in menu items to display. He slid in “Coffee” and “Low Jitter Coffee” tags.

The new coffee was a huge success. Zed's business doubled in a week. He added four baristas to the evening shift.

However, Zed’s competition soon caught on. A week later, Zed noticed a new shingle on MegaCup’s sign: “Low Jitter Coffee”. The war was on.

Then his supplier told him about another type of coffee. It was called “Double Bold Coffee”, and it was significantly stronger than the normal brew. A single cup could keep you awake all night. Zed ordered eight cases and a the new menu tag for the ArrayDesignBoard menu.

The coffee was a huge success. His morning crowd loved it. He also started attracting new customers from the castle’s night guards. They needed something strong to keep them awake during their watch.

Alas, it was not long before MegaCup added a new shingle to the end their sign.

The next time his supplier visited, Zed grilled him on the other types of coffee available. After obsessing over the supply lists, Zed decided to try a novel approach. He order one case each of ten different flavors. He put these flavors into a rotation, constantly offering new variety. This approach worked particularly well with Zed’s sign. Every time he switched a flavor, he would remove one tag and slide a new one in. Sometimes he changed the menu a few times in one day, such as replacing “Double Bold” with “Low Jitter” after noon.

MegaCup took a different approach. The manager quickly found that, while adding new shingles to the end of the list was easy, removing them was frustrating. In order to remove a shingle, he had to: unlink it from both the shingles above and below, then reattach the shingle below to the one above. It was a time consuming process. He decided to take advantage of the ability to easily expand offerings. He offered six different coffees on a semi-permanent basis. On rare occasions, he would grudgingly spend fifteen minutes to unlink a shingle on his sign and add a new one.

The two coffee shops operated in that mode for years. Zed’s coffee shop rotated through different options, and MegaCup offered a more constant, but larger, selection.

Both businesses thrived as the market for coffee grew. Eventually, Zed's Coffee House became one of the largest businesses in the kingdom with over a hundred different locations. Zed continued to expand aggressively until the great sugar famine hit. With business dropping due to the lack of sugar, Zed decided to leave the world of coffee and speculate in coconut sales.

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

Interested in learning more about linked lists? See why choose your own adventure stories should never be linked lists. Or, read about Ann's ocean voyage and her insights into linked lists.

Linked Lists, Kindergarten, and Ocean Voyages

Linked lists are simple data structures that store a list of items. Each node in the list consists of a few pieces of data: the information being stored at that node (or a pointer to it), a pointer to the next node in the list, and (optionally) a pointer to the previous node in the list. An algorithm can traverse the items in a list by simply following the pointer out of each node to the next. However, random access of nodes is not possible, unless additional pointers to the nodes are stored in an outside data structure. Linked lists support easy insertion and deletion of elements, by simply changing where appropriate nodes' pointers are pointing.

Ann had been excited about her ocean voyage to New Atlantis for approximately twenty minutes. She had stood at the ships railing, watching the shoreline move away and feeling the sea breeze on her face. The ship's sails had made a pleasant flapping noise as they caught the wind. It had been exhilarating. Then, much to her dismay, the ship had started a nauseating series of sways and lurches. That had been three days ago and the movement had not ceased for a moment.

Bundled up against the (now remarkably frigid) breeze, Ann sat on the ship's deck and watched the three ships following silently after them. The first was only four hundred meters behind, the second four hundred meters after that, and the third another four hundred. In addition, Ann knew there was another ship leading the way four hundred meters in front of them. Together the five ships made a convoy that stretched out in a mile-long line across the ocean.

Ann had found the arrangement of the convoy fascinating. When she had interrogated the captain to the convoy's linear arrangement, he had happily explained the line's functionality in exquisite detail. The convoy consisted of a chain of ships, navigating along the same route. The head ship led the convoy. Supposedly, this arrangement facilitated both navigation and safety.

Communication among the ships was also fascinating. Each ship had two crew members called pointers, whose job it was to communicate with the other ships. When someone on ship #2 wanted to pass a message to ship #5, the Pointer at the back of ship #2 would signal the message out to ship #3. Similarly, ship #3 would relay it to ship #4 and ship #4 to ship #5. It was a completely linear system, with the message passing through each ship on its way.

The whole arrangement reminded Ann of her days as a young kindergartener when the class would be forced to hold hands as they went on field trips. Each kid would maintain contact with exactly two classmates, assuring the full string of students stayed completely connected. The teachers would walk down the line carefully comparing the students to a list of names and ensuring that everyone was present.

But in Ann's mind, the best thing about the kindergarten lines were their ability to be dynamic. When one student had to visit the restroom, they would leave the line by simply making sure that the students on either side of them held hands with each other. This operation was usually marked with a careful shuffling of grips, but always resulted in the class maintaining its line (minus the kid running to the restroom). And, when the student returned, they would: pick a point to insert themselves in the line, break the line at that point, and make sure they reformed the connections by holding hands of the correct two people. This line concept had made such an impression, that Ann had spent years marveling at the power of pointers and dynamic data structures.

"Captain, do your convoys ever get additions or removals?" Ann asked one morning. "Or is the convoy fixed once it departs?"

"Of course the convoy changes." the captain answered. "In fact, later today we have three ships joining us from North Patagonia." He gestured vaguely toward the direction of North Patagonia as if to illustrate his point.

"Will they join the end of the line?" asked Ann, eager to understand the convoy's dynamics. It would make sense to simply append the new ships to the end of the line. That way only the first ship of the new arrivals and the last ship of the current convoy would need to connect. That is how they had merged lines in kindergarten.

"No, no." insisted the captain. "They will join between ships #4 and #5. Ship #5 is a special warship with extra rear facing cannons. It always has to be in the back. One by one the ships will insert themselves into the chain, coordinating through their pointers. Good sailors, those pointers."

"But how?" asked Ann. For the first time in days she had forgotten her sea sickness. She was distracted by the beauty of dynamic structures.

"All very simply, I assure you. The new ship, let's call it D, will pull up next to our head ship (A) and then slow down. It will slowly work its way down the convoy until it finds a location to be inserted: let's say after ship A. Then the D's pointer coordinates with B's pointer to say 'You are now behind us.' and ship B moves back to let D in. At the same time D's other pointer coordinates with ship A's pointer to say 'We are now behind you.' It is all very organized."

(Ship D joins convoy between ships A and B)

Ann was thrilled. When the ships arrived that afternoon, she watched their coordinated dance with glee. The simplicity of it amazed her. Inserting new ship into the line was only a matter of four pointers, two in each direction. In her excitement over the dynamic operations of the convoy, Ann even managed to forget about her seasickness.

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

Interested in learning more about linked lists? See why choose your own adventure stories should never be linked lists or how Zed used linked lists while expanding his coffee shop.

President of the Heap

Heaps are tree-based computational data structures with the property that a node's value is always greater than or equal to that of its children (a.k.a. the heap property). Heaps support efficient FindMax O(1), Insertion O(lg N), and DeleteMax O(lg N) operations. Heaps are commonly used to implement priority queues. Heaps can also be used to sort numbers via the heap-sort algorithm, which inserts all the numbers into the heap and repeatedly pops off the current max.

The sprawling kingdom of North Patagonia was known for its picturesque waterfalls, neatly manicured cricket pitches, and tasty beef stew. However, the kingdom also suffered from the (admittedly well-deserved) reputation of being a land of political disfunction. In particular, the average tenure of a ruler of North Patagonia was approximately twelve days.

Unlike its neighbors, rulers in North Patagonia were never over-thrown; they were simply voted out office. In fact, North Patagonia's entire government voting structure was based on an idea that its founders had once observed on a reality television show. Instead of voting leaders into power, the citizens would simply maintain the right to vote the current ruler out of power at any time. When a leader was removed from power, they retired from politics and the next most-qualified candidate (as measured by the Standardized Ruling Qualification Test or SQRT) became the new leader. It was an orderly, although excessively dynamic, process.

Unfortunately, the preoccupation with SQRT scores had led to a rather strange power structure within the government. Each person in the government, including the president, could have up-to two people reporting to him or her. And, as expected, all of the officials insisted on getting exactly two people working for him or her. The only other constraint to this hierarchy was that a person's SQRT score must be higher than the scores of his or her underlings. Thus the entire government formed a binary tree structure with the hierarchy based on a single test score.

(The government hierarchy as organized by SQRT Score)

After a few hundred years, this structure had become so ingrained in the very functioning of government that the kingdom's chief architect redesigned the entire North Patagonian state house to reflect the hierarchy. The new state house was a single, unimaginably long, row of offices running across the capital city. At the western most end was office #0, the office of the president. To its east were offices number #1 and #2, the offices of two people reporting to the president. Following that were offices #3 and #4 (reporting to the person in office #1) and offices #5 and #6 (reporting to the person in office #2). This pattern repeated down the hall, with the person in office #N having employees in offices 2N+1 and 2N+2. Thus, as you got further down the hall, you were moving further down the bureaucratic ladder. In addition to organizing the physical offices such that their locations reflected the relative position of the official inside, the layout of the state house had the unexpected benefit of being ideal for hosting marathon office chair races down its hall.

(The Western side of the North Patagonian state house)

As one would expect, the entire functioning of the government hierarchy had evolved due to its advantages in the high-churn government of North Patagonia. In particular, the governmental structure provided orderly and efficient processes for three common scenarios:

1) Determining who was in charge (FindMax) - The current ruler is the person in government with the highest SQRT score. This naturally corresponds to the person at the top of the government hierarchy and the person in the western most office, #0.

2) Adding new officials (Insertion) - Each time a bright-eyed new bureaucrat took up the call of government, they would take the SQRT exam and be inserted into the correct level of the government. After the redesign of the state house, this process became exceedingly simple. The new official would move into the eastern-most unoccupied office (the empty office with the lowest number). They would then go pay a visit to their new boss. This visit had two goals. First, the new official would perform an official introduction. Second, the new official would, quite unsubtly, check their boss's SQRT score. If they then noticed they were mistakenly reporting to a boss with a lower SQRT score, they would point out this fact and immediate swap both roles and offices with their boss. The new boss would become the new subordinate and, grudgingly, move their office down the hall. As procedure dictated, the new official would then continue down the hall again to introduce him or herself to their new, new boss. This process of humiliating swaps continued until either the new official finally met a boss that had a higher SQRT score or they became the new president. As a result of this process the vital property of government was maintained: everybody was working for someone with a higher SQRT score.

3) Voting out the top official (DeleteMax) - When voters tired of the current president, they simply voted him or her out. This process was greatly simplified with the introduction of grocery store voter kiosks, where shoppers could simply log in and press the "impeach" button. The exiting president would give a speech on TV about what an honor it had been to serve the country and then would walk down the hall to notify his or her new replacement. By law the president would pick the replacement with highest SQRT score, which due to the structure of the government was already one of the two officials working for him or her. The new replacement would gleefully move into the president's office and then go down the hall to notify their replacement. Again a series of moves propagated down the hall with each official moving up notifying exactly one employee to take his or her place. And once again the vital hierarchy of the government remained unchanged.

North Patagonia continued to maintain this unique governmental structure for nearly four centuries, churning through thousands of presidents. The only period of relative stability was near the end when Robert the Uniquely Good at Filling In Test Bubbles managed to stay in power for over a hundred days. In addition to scoring well on the tests, Robert turned out to be a reasonably competent leader. Finally, tired of the lack of sufficient drama, the citizens eventually voted him out due to a poor showing of the North Patagonian cricket team.