Too bad ... she had re-built the engine maybe 5000 miles ago,
so it was pretty reliable, but one of the motor mount bolts
to the crankcase had been repaired sometime or other with a helicoil,
and when it loosened and fell out, the engine oil followed. And guess
who was driving - the fellow who didn't know what that red light
on the dash meant.
So there she was, about 350 miles from home and well over 500 miles from the Junkyard, with a dead engine. What to do. What to do. AJ (always the Safety Officer) took charge of the operation.
Well, there was that 1600 engine for Stephanie-Meets-Dead-Bambi (the camo Baja with the underneath painted blood-red), but it wasn't a bus motor, and it was fresh re-built (which never gives AJ any confidence, although he knew who re-built this one, having done the job himself), and it would have to be delivered.
So AJ got out the old NEATO/LIMBO book and the Rand McNally and started calling folks.
The NEATO/LIMBO bunch compiled a list of names and phone numbers of VW folks sorted by state and municipality. There really weren't any listings within 100 miles of where Pam was, but he started calling anyway.
"Tennessee?" the one guy said, "I'm in South Carolina."
"Well, I'm in northeast Ohio," AJ replied, "Tennessee is your neck of the woods."
Generally people will be helpful so long as you don't ask them to do anything. So all AJ did was ask if maybe you knew anyone who might have a used engine they might want to sell. Two people did have old engines laying about but they both wanted a prohibitive amount of money.
But everyone had at least two other phone numbers for him to try. There were six listings in the NEATO/LIMBO book that AJ called. Each of those guys gave him two numbers (actually more, but things are simplified for clarity). Look at the binary tree that one gets under these conditions:
Here the first row indicates the original 6 phone numbers. The second generation yields 12 additional phone numbers, and carrying it through to a third generation yields 42. A fourth generation would yield a total of 90. A fifth gives 186.the book | +-----------+-----------+-----+-----+-----------+-----------+ | | | | | | 1 2 3 4 5 6 | | | | | | +--+--+ +--+--+ +--+--+ +--+--+ +--+--+ +--+--+ | | | | | | | | | | | | 7 8 9 10 11 12 13 14 15 16 17 18 | | | | | | | | | | | | +-+-+ +-+-+ +-+-+ +-+-+ +-+-+ +-+-+ +-+-+ +-+-+ +-+-+ +-+-+ +-+-+ +-+-+ | | | | | | | | | | | | | | | | | | | | | | | | 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42
I can hear you now .. "So what?". But here's the beauty of how networks work. These are not just 43 names out of the millions of people who live in the four-state area around the gas station where Pam was pulling the engine out of Sunny. These names had been selected according to criteria, specifically, location and possibility of used engines.
And AJ didn't get past the third call in the second generation (about the tenth overall call) before he got warm. Frank had turned him on to Vintage VW in Greenville, SC, who didn't have an engine but knew a distributor's rep who went to ALL the VW shops in the area, and that was Steve Munsey from Number One Parts, and as it turned out, he lives about 10 miles down the road from that very gas station where Sunny was sitting. Steve was on the road in Winston-Salem, but he gave AJ the number of Bill, his local hometown VW mechanic, and Bill didn't have a used engine ("Can't keep one around long"), but he put Pam in touch with his friend Ronnie, who had a old lower end that he donated and Pam transferred her top end and got back on the road.
Here's what Pam said, "We couldn't have broken down in a better place."
So now you know how networks work. Binary trees such as this one have a lot of applications aside from the current example, especially in the world of Computer Science. There are applications as diverse as quick, on-the-fly alphabetization and look-ahead chess playing, where the 1st generation consists of all my possible moves and the second generation consists of all your possible responses to each: a very big tree. There's considerable literature and research available dealing with trees, tree searches, recursion, and methods of optimization.
Some notes on the story:
1. When Pam started to put the replacement engine together, she called and
asked why the crankcase had no place for a dipstick. AJ consulted Jim of
Jim's Custom VW
who said that it was probably because
it was a Type III engine. The even more distinguishing part of that
engine block is the hole in the right rear sump where the oil fill/dipstick
attaches (much like a Type IV engine). It turned out that he was
exactly right.
This is also the reason why - when the engine was completely assembled - there was no oil pressure switch to run the red light on the dashboard. Type III engines had the switch in the oil cooler, and the Type III oil cooler was inappropriate for the engine that Pam was putting together. Slick, huh? The oil light didn't help much in the Pam's first engine, but driving without one always makes me nervous.
2. Here's how to use a tree to alphabetize a set of names. If we just had a list of N names and every time we got a new name searched down the list to see where the name should go, we would (on the average) search through N/2 names to locate the correct position. We would require the same number of accesses to retrieve the name. If there were 1,000,000 names, this would take an average of 500,000 accesses. Sort of like finding a name in the phone book by starting at the beginning and plowing through.
A better way to use the phone book would be to open it to the middle and see if the name we want comes before or after the open page. We can look at this approach as a network using the alphabetical nature of the phone book. If we build a binary tree where each node has a left link and a right link, then starting at the top we can use the rules:
This would give us a tree that might look like:
SEARCH: If the NEW NAME alphabetically precedes the NAME at the current link, then If there is a name at the left link of the current node then move to the left link and start SEARCH again. Otherwise insert the name at the left link of the current node Otherwise If the NEW NAME alphabetically follows the NAME at the current link, then If there is a name at the right link of the current node then move to the right link and start SEARCH again. Otherwise insert the name at the right link of the current node Otherwise the NEW NAME is already here at the current node
Note that to find any name among these, we only have to look at 3 nodes in the tree shown here, versus an average of 3.5 names in an alphabetical list. This advantage grows quickly as the number of nodes (N) increases. 1,000,000 names would require an about 15 accesses. Compare that with the half million for the list approach.
Nordhoff,Heinz | +------------+------------+ | | Muir,Saint Porsche,Ferdinand | | +-------+-------+ +-------+-------+ | | | | Hoover,Bob Mull,Perry Raab,Karl Stevens,Mark
Extra credit: Who are all those people anyway?
3. Perhaps the best game for heuristic research and optimization of large trees is the game of Go. Go has been dated as far back as 2300 BC in its present form, and Legge notes in his translation of the I Ching , that most ancient of books, that originally Go pieces were used in casting hexagrams instead of solid and broken lines.
The game is played with each player alternately placing a white or black stone on intersections of a 19X19 grid (391 possibilities). A complete tree would contain every possible sequence of moves. Thus, the first generation of the tree has 391 nodes and the second has 391x390, the third 391x390x389 and so on.
A complete tree would contain every possible sequence of moves. The idea, for any move, is to see how many of the subsequent branches end with a win. The best move is the one with the most winning leaves. But this is a tree so big as to be unmanageable. Strategies must be in place to prune whole branches of such a tree as early as possible.
Extra Credit: How many nodes in the complete Go tree? That would be 391 times 390 times 389 times 388 ... all the way down to ... 3 times 2 times 1. How big a number can your calculator handle? How about your computer?
Now you know about as much about trees and networks as I do. Here you thought you were just going to read a story, and instead I've made you learn things. Sorry. Won't happen again.
c 1996 Air Cooled Volkswagen Junkyard of Richfield, Ohio
"Where Advice Is Always Free" (216)659-3638
This story may be distributed only if it is not altered in any way
and is distributed freely without charge.