Category Archives: Me

Things to know about retirement, USA, married couples.


#1  Can one spouse can retire with the other spouse’s social security benefit?

Yes, a surviving spouse can choose to use their own Social Security Insurance* (SSI) benefit OR their deceased spouse’s SSI benefit – whichever is larger. But not both. SSI was created when a many (but not all) women’s jobs were in the home, and many (but not all) men’s jobs were outside the home. The spouse working outside had an employer and cash wages, the spouse keeping the home had neither.  So a non-working spouse who had no SSI benefits on their own could continue to collect the benefit their spouse had retired on, if the spouse died.

Here’s the clever bit: If both spouses had SSI benefits, each started drawing them when they retired. If one spouse died, the survivor could switch to whichever benefit amount was larger. Say, for example, Pat and Kim both worked and both earned maximum SSI benefits. If Pat starts drawing at age 62, the amount they get is substantially less (30% in my case) than if they hung on to “Full Retirement Age” – (66 2/3 years, in my case).  If Kim keeps working, or can otherwise hold-off starting SSI benefits, Kim’s monthly benefit will be larger, even if both have at least 40 quarters of paid employment and contributed the full amount required by law, every year. Thus, Pat and Kim have different monthly benefits from SSI and always will for the rest of their lives.

IF Kim dies before Pat, Pat can change to drawing Kim’s higher monthly benefit, but can’t keep their own benefit. Pat’s old benefit simply vanishes. If Pat doesn’t want Kim’s higher benefit, they keep their own and Kim’s vanishes. If Pat dies before Kim, Kim already has the larger benefit.

So the SSI monthly payment is a benefit for a living person, but it is not an asset which can be conveyed to a person that the original recipient chooses. This is a key difference between SSI, and employee pension plans, and 401Ks and the like. 401Ks, etc., etc., are assets. There are rules about how they are used, and rules about when and what taxes are paid on them. But they are as real as any other account at an investment firm.

 

#2 Is there a minimum amount you must withdraw from a 401K, every year?

Yes. Starting when you turn 70 1/2 years old. In one example I found, its 1/26 of the value of the account, a bit less than 4%. But it is complicated and Morgan Stanley’s retirement fund people say to come talk it through with them on the way to picking a number.

See topic 4, in:

http://fa.morganstanley.com/jteam/retirement_planning_mistakes.htm

There are retirement calculators that cover this as well, with their own lore, sacrifices and mod-cons:

http://www.choosetosave.org/ballpark/webapp/#/estimate

So if you’re 61 and haven’t retired yet, you don’t have to do anything. Yet. If you are working and can pack more money into the 401K, it’s probably wise to do so. If you wonder how much your 401K is worth to you as income, now, today, and you’re less than 70 and 1/2, its likely you can take out less than 4% each year. If you take out more than it makes every year, its a “decreasing asset” and you’ll have to judge your rate of consumption vs. expected lifespan. You can look up your life expectancy, for starters:

http://www.ssa.gov/planners/lifeexpectancy.html

If your 401K is with a different investment firm, they’re who you should speak with.

 

More as I get it. I’ve foot-noted “Insurance” below.

*”Insurance” as in “Social Security Insurance” is misleading.

Conventional insurance products are based on shared risk and supposedly conservative investments. Every week, month or year, you send in your pennies, along with everyone else. All the pennies get invested wisely enough to cover whatever payouts are made over the lifetime of the product. Automobile and home products typically last 1 year, “Term” life insurance lasts for a fixed period, ending at a birthdate or some other agreed point in the future. Payments can be spread out over the term the insurance covers, or be one-time at the beginning.

“Whole” life insurance stays in force as long as the insured person is alive and the regular payments are made. The payout becomes an asset for survivors.

SSI is none of these things. If you want to start a fight, call it a modified Ponzi scheme. The money it pays out comes directly from the regular contributions collected immediately before the payout. Sort of. There need not be a pooled asset which yields profits which support payments. The term of art for this is “Pay as you go”, which is more attractive than “Ponzi Scheme”.

The details, where the devils lurk, are that a pay as you go scheme such as SSI starts with lots of contributors and no recipients. So the first funds collected did, actually, go into some investment, likely US Treasury Bonds, the most boring, safe asset. You’ll note this has the effect of retirees-to-be investing in the National Debt. Then the Baby Boom arrives and goes to work and the number of workers contributing is vastly larger than number of recipients. So the surplus continues going into bonds where it props up the National Debt.  Hiring new devils every year.

One wild-eyed argument against SSI is that NONE of the Treasury bonds will ever be sold, because actual tax dollars would have to pay them out. On the other hand, the Treasury pays bond dividends regularly, and returns the principle at the end of the bond’s life, to all the other bond holders inside and outside the USA. Does SSI surplus go into conventional “T-notes” similar to what anyone can buy, or are there conspiracy-special T-notes that pay no interest and don’t return the principle, because they exist only to suck up SSI surplus? I don’t know and I’m too busy to look it up, today.

A more plausible SSI disaster scenario is that the number of contributors won’t keep up with the number of recipients. This is the “SSI will go bankrupt” trope, and if nobody does anything about it, it will happen. Increasing the payments made by contributors or decreasing the benefits going to recipients seem like logical steps, but logic isn’t universally popular. It *could* happen. If nobody does anything about it.

So the payroll deduction is called “SSI” and it’s a gift to us from history, outdated and misleading marketing language. If we imagined we were as adult as other developed nations, we might make “SSI” part of taxes, in general, and make the payout an expense that must be paid, like our Congressperson’s retirement, medical and dental coverage.

Advertisements

A Software Tester’s journey from manual to political tester


I wrote this some years ago. I should simplify the context and incorporate what I reference from the OP and other responders, so that it stands alone. But this has  meaningful observations which took effort to reach, so I’m putting a copy up here to start with.

Wow, no exaggeration! I can see every event that befell poor Jim happening in the real world. HOWEVER, Jim’s a fortunate fellow, he has management attention at all! AND they look at results. AND there is a perception (no matter how shakily based) of overall product quality.

Jim was no worse than anyone else until he got automation started and mistook his personal satisfaction and enjoyment for the company’s obvious goal of shipping a stable or improving level of quality with fast turnaround on bugs and needed enhancements. This is engineering, not art. Its not self actualization, its a commercial business or a service enterprise which creates value.

All the way down this sad story, Jim accepts product failures, and testing failures. You Can Never Ignore Failures. Period. He should have turned political at that point and realized that Test, like anything, needs to be sold, shown to be valuable and productive, and needs allies. Therefore, tests need to actually be valuable and productive, and needs to make it easy for people to accept them, adopt them, and feel they are important support in their own success. Therefore he needed to measure success, as understood by his customers (developers, support, users) and maintain or improve its integrated value. Accepting failures leads to dead astronauts, wasted billions, wrongful convictions, Senate Select Committees, Frontline specials, sub-Redits, and worse.

Instead of seeing failures as a very, very, high priority, Jim turns into a man with a solution, wandering around, looking for a way to apply it. A tawdry tale, rendered no less tawdry by its oft retelling. Not insignificantly, Jim’s manager is clearly a weak and ineffective character who should have seen problems coming, or reacted when they appeared. Once Jim had made the case for automation, they might have hired someone who knew something about automation, or contracted with very carefully defined goals.

Jim might have split his team up front. He needed manual testers, who carried on the work that had been being done, with as much success as possible, and brain power applied to improve results and lower cost. A front line to hold success. Then a test automation group who focused on test automation with clear and obvious benefits

The automation environment needed to be something:

  • …anyone could run;
  • … which worked from a shippable product, as well as a release candidate or development build;
  • …which could be triggered directly from a product build, so the build group-and-release group ran it every time;
  • …which could be configured to run anything from a single, new, test to all existing tests
    • in a developer’s environment, before check-in, or
    • at any subsequent point, including on a previously shipped release with a support issue.

Setting up the test environment, creating a test to get the product to say “Hello world”, and recognizing that as a test pass ought to take no more than an hour longer than simply setting up the product. That assumption has to be proved every release or two with a calibrated innocent new-hire from somewhere.

Since all tests start by installing the product, license, etc, and starting it, the first thing to automate would be that. If there were changes in that functionality, over product history, the automation could start with the newest, but it had to support them all. Having this ‘smoke test’ be part of a full build would pay dividends to everyone, everywhere, and by designing with backward compatibility and future adaptability, thrash could be minimized, or at least recognized.

This would be a good time to look through the bugbase to determine where the most bugs were being found, where the most escapes were happening, and where the most critical bugs were coming from. Besides looking backward, a forward look at the product roadmap and with developers and management could highlight areas of future leverage

In parallel with automation, all of the above should be considered when selecting manual tests. Tests which never fail should be reduced relative to tests which find failures. Something that fails for diverse reasons may be a great canary in the coal mine, or might be a too fragile sponge that soaks up maintenance effort. In any event, continual improvement of the manual testing should run in parallel with introducing automation. After a small number of releases, the manual tests available should exceed the resources to run them. Selection of the ‘vital few’ should in intentional, not happenstance.

Most people can see the limitation of record and play back, so things should never stop there. The only tools worth looking at are tools that can be edited and rapidly expanded by iteration. Cut and paste is the lowest form of iteration and rapidly grows nightmares. Algorithmic test point generation is desirable, but data driven testing should get strong consideration. Algorithmic generation of literal tables which are then applied as tests separates the thing that needs to be done over and over, running the test, from the thing which is done less frequently, generating the test points.

In my life, I’ve seen a few of the failures in Jim’s story, but a lot of failures of usability by others, or by anyone, complete lack of testing in development plans. Test suites (with running tests) abandoned and no-longer run, until the next great hope get started. And far too little curiosity about which tests should be run, automatically or manually, to get the most bang for the buck.

Like I said, Jim is lucky!

View in discussion

Software Test Methods, Levels, quiz question answers


Quiz questions about software test. My answers are probably longer than was hoped for, but specific, and most important, true and demonstrable.

1) What is the difference between functional testing and system testing?

2) What are the different testing methodologies?

1) System test is the equivalent of actual customers/users using the product. Carried out as if in the real world, with a range of detailed configurations, simulation of typical users working in typical way. It is one level of abstraction above Functional testing. Functional Test verifies that the product will do functions which it is intended to do. Play, rewind, stop, pause, fast forward. +, -, x, /, =.  Functional Tests must be drawn from the Requirements documents. System Test checks that a product which meets those requirements can be operated in the real world to solve real problems. Put another way, System test proves that the requirements selected for the product are correct.

This makes one wonder why engineers don’t do system test on the requirements before creating the design and code… mostly because its hard to do, and they’re sure they understand what the requirements should be, I suppose. I’ve never seen it done in depth.

 

2) “the different testing methodologies” seems over-determined. The following are ‘some’ different testing methods. There may be others.

Perhaps the intent of the question is to expose a world divided into White Box and Black Box testing, which are different from each other. But there are other dichotomies, in addition to White Box and Black Box.

Software testing methods divide into two large classes, Static and Dynamic. Static testing looks at source code, dynamic testing requires executable programs and runs them. Another division is between Using a Tool that evaluates source code and and Checking Program Output. Within either set of large groups are smaller divisions, Black Box and White Box (and Clear Box and Gray Box) are all divisions of Dynamic or Checking Output methods.  Specific methods within the large groups include

  • running source code through a compiler
  • running a stress test that consumes all of a given resource on the host
  • running a tool that looks for memory allocation and access errors
  • doing a clean install on a customer-like system and then running customer-like activities and checking their output for correctness.

Orthagonal to all of the above, Manual Test and Automated Test are infastructure-based distinctions, Automated tests may be Black Box, Unit, running a tool, checking output, or any other methodology. Manual and Automated are meta-methods.

 

Static Software Test Methods: Similar to, but not exactly the same as Tool Using Methods, to find problems in software source code.

2.1) Compile successfully, no errors or warnings. This is the first step before inspection, since nothing is better or cheaper at finding compiler problems than the compiler.

2.2) Inspection and code review, to see if the code is written to the standards that the organization enforces. I like and use code reviews, the formal Fagan system, and less formal “extreme programming” techniques like having a second person review all diffs or do a walk through with two people at the workstation. They work. The standards inspected for are usually helpful in preventing bugs or making them visible. Just looking usually improves product quality – the Western Electric effect if nothing else.

There may be some insight into product requirements and how the code meets them in a review. But the reviewers would need to know the requirements and the design of the software in some detail. Its difficult enough to get the code itself to be read. In Engineering Paradise, I suppose the requirements are formally linked to design features, and features to data and code that operates on that data, to create the feature.

2.3) Static analysis. Besides passing compiler checks without errors or warnings, there are static analysis tools, “lint” for example, that can inspect code for consistency with best practices and deterministic operation. Coverity, and others, have commercial products that do static test on source code.

2.4) Linking, loading. The final static events are linking the code and libraries required to complete the application, and writing a usable file for the executable, which the loader will load.

Dynamic Software Test Methods:

2.5) Memory access / leakage software test. Rational/IBM’s Purify, like ValGrind and BoundsChecker, run an instrumented copy of the source code under test to see memory problems in a dynamic environment. Its run and the results should be checked and responded to before a large investment in further  Dynamic testing should happen.

2.6) Performance test. Measuring resources consumed, obviously time, possibly others, during repeatable, usually large-scale, operations, similar to System or Load tests. Generic data, from development testing, is necessary and may be shipped as an installation test to users. Proprietary data, under a NDA (non-disclosure agreement), may also be needed, for complex problems ans/or important customers. In normal operation, the actual outputs are not looked at, at most, spot-checked, and the tool(s) keeping track of resources are the basis of pass/fail.

2.7) Installation Test. Typically a subset of in-house performance tests, with optional, generic, data. The performance recorded is comparable between releases, instances, configurations, sites, customers, and the software maker’s own in-house performance tests. Customers can use Installation tests to verify their hardware/software environment, benchmark it, evaluate new purchases for their environment, etc.

 

Checking Program Output Methods:

After tool based dynamic testing, the rest of Dynamic software test is based on running the product with specific inputs and checking the outputs, in detail.

Checking can be done with with exit status, stack traces,”assert()”, exceptions, diffing large output files against ‘gold’ references, log searches, directory listings, searching for keywords in output streams indicating failure or incorrect operation, checking for expected output and no other, etc. No test failures are acceptable. Each test must be deterministic, sequence independant, and (ideally) can run automatically. No judgement required for results. All require running the program.

2.8) Unit tests of pieces of the a product, in isolation, with fake/simulated/mock resources. A great bottom-up tool for verifying software. At the unit test level is where knowledge of the code is most important to testing. It is white box/clear box, with full insight into the code under test. One explicit goal of unit test should be forcing all branches in the code to be executed. That can’t be done without allowing visibility into the code.

2.9) Integration Test. The next level above unit test, the tests of code which calls code which calls code… and the code above that! The point is that integration is where code from different groups, different companies, different points in time, certainly different engineers, comes together. Misunderstanding is always possible. Here’s one place it shows up. Visibility into the code is getting dimmer here. Some tests are more functional, if a subsystem contains complete, requirement-satisfying functions.

2.10) Functional Test. Verifying that the product will do functions which it is intended to do. Play, rewind, stop, pause, fast forward. +, -, x, /, =.  Tests here should be drawn from the Requirements documents. Things that should be tested here should start in the Requirements docs. Each requirement has to be demonstrated to have been met. Its black-box testing, run from the interface customers use, on a representative host, with no insight into the internals of the product. Unless the requirements specify low level actions.

Its not particularly combinatorial- a short program, a long program, 2+2, 1/-37. Pat head. Rub belly. Walk, Not all 3 at once.

If a word-processor has no stated limit for document size, you need to load or make a really big file, but, truly, that’s a bad spec. A practical limit of ‘n’ characters has to be agreed as the maximum size tested-to. Then you stop.

All these Tests should be drawn from the Requirements documents. Things that should be tested here should start in the Requirements docs.

All that Verification is good, but what about Validation?

Unit test,  Integration test, or Functional Test, is where Validation, proving correctness of the design, might happen. Validation test is where deep algorithms are fully exercised, broad ranges of input are fully exercised, Tests that include all possible numerals, all possible characters, all defined whitespace, read in or written out. Numbers from MinInt to MaxInt, 0 to MaxUnsigned, the full range of Unicode characters, etc., etc., are exercised.

(Errors in input numbers should be seen in System test anyway, but accepting a wide range goes here.) This is not always done very formally, because most modern code environments don’t need it. But someone ought to look at least once.

L10n (Localization) and I18n (Internationalization) that need to be selected at link time or run time can be checked here too.
This is also where path-length limits, IPv-6 addresses, etc. should be checked.

2.11) User interface test verifies the controls and indicators that users at various levels see, hear, touch, operate and respond to. This is separate from any actual work the program may do in response. This is a high-value target for automation, since it can be complex and tedious to do UI testing in great detail by hand.

2.12) System Test. Full up use of the system. Training, white-paper and demo/marketing examples. Real-world situations reproduced from bugs or solutions provided for customers. Unless requirements included complexity, this is where the complex tests start. Huge data. Complex operations.  The range of supported host configurations, min to max, gets tested here too.

We’ll want to see all the error messages, created every possible way. We’ll want to have canned setups on file, just like a customer would, and we pour them into the product, run it, and collect the output. The set pass/fail on the output.

Somewhere between System Test and Acceptance test, the scale of pass/fail goes up another level of abstraction. Software test pass/fail results are one in the same with the product pass / fail. If data and setup are good, it should run and pass. Ship the result. If the data and/or setup have a problem, it should run and fail. The failure should propagate out to be stored in detail, but in the end this is a trinary result. Pass, Fail, Not Proven

2.13) Load test, Stress test.  Load tests go to the point that all of a resource is consumed, and adding  more activity produces no more output in real time. Resources include CPU, memory, local storage, networked storage, video memory, USB ports, maximum number of users, maximum number of jobs, maximum instances of product, etc. Stress test adds data, jobs, etc, clearly (110% or more) above load test maximum.

2.14) Stability test. Long term test. Stability test and long-term test are where a server or set of servers are started and left running, doing real work, for days, weeks, months. Some of the tests must repeat inputs and expect identical outputs each time.  Resource consumption should be checked. Its fair for the application or tool to have the node to itself, but adding other applications and unrelated users here and in the Load/Stress tests is meaningful, to avoid surprises from the field.

2.15) Acceptance test.  Customer sets-up their run-time world use of the system and uses it. Everything they would normally do. If its a repeat sale, they may just clone the previous installation. Run the previous and the new system, release, patch, etc, and compare output to installed software on machines that customer likes and trusts. If the product is a new one, acceptance means judging pass-fail from the output produced.

 

Many other kinds of test are mentioned in conversation and literature. A web search will turn up dozens. Regression test, stability test, in the sense that a new code branch is stable, sanity test and smoke test are all forms of testing but usually, in my experience, consist of subsets of the test levels/methods listed above.

A Smoke test (run the product, make sure it loads and runs, like a hardware smoke test where you apply power, turn it on and see if any smoke comes out…) can be made from the first steps of several different methods/levels named above. If the Smoke test is more than simply running the program once, then it should probably be some part of one of the other methods/levels. Or to put it another way, the work that goes into setting up the smoke test should be shared/captured. There might be a ..test/smoke/… directory, but the contents should be copied from somewhere else.

A Sanity test, a Stability test and Regression tests are successively larger swaths, at lower and lower levels, of the System, Performance, User Interface, Functional, etc. tests. They should be specified and are not embarrassing, but their content should be drawn from or reflected by those larger level-based tests. The should not be original and alone.

What do you think?

Image

Father’s day tides at Moss Beach:


Here’s the tide table for this coming weekend at Moss Beach, just north of Princeton By The Sea, at the north edge of Half Moon Bay. High tide, +6 feet, at Midnight between Friday and Saturday, 1:00am between Saturday and Sunday. Low, low, tides at 7:00am, -1.5 feet!! on Saturday, -1.25 feet, at 7:48am, Sunday.
So, by crackie, we’ll be there as early as we an on Sunday. Sunrise is before 6:00am, so no shortage of light. Do a web search and you’ll discover this place has the best tidepools that ever existed- perhaps 1/4 mile or more along the coast, as much as 200 yards off shore of the normal high tide mark. A huge shelf of very low quality rock, normally around or perhaps a bit below the 0 foot level, that will be a good foot above sea level on Sunday Morning.

Glad you asked: 1/32 model airplanes with working retractable landing gear. Working landing gear in general


Among the not so surprising list of searches that brought people to my blog, yesterdays list (below) included one dear indeed to my heart: “1/32 model airplanes with working retractable landing gear”

Ah yes, the great divide. Are we building scale models or toys? I come down firmly on the “toys” side, although many fine people I know personally are probably closer to scale modelers. I have to admit that almost any working feature of a model, particularly from a plastic kit, is going to compromise accuracy to some extent. Turning and propellers, wheels, maybe not so much. Opening doors, hatches? Mmmm, tricky. Retractable landing gear? Almost never truely ‘in scale’, but it HAS been done.

Personal experiences with working, retractable, landing gear:

1/32 Revell Supermarine Spitfire Mk I. Moving control surfaces and sliding canopy too.

1/32 Monogram North American P-51D Mustang. In “Phantom Mustang” or P-51 or F-51 form, this kit has retractable main gear and a tail wheel that are all actuated by turning a wheel on the belly. For the Phantom kit, an electric motor and gear train does the work. For the non-Phantom releases, the gear fixed to the plane becomes a knob to turn. Also comes with sliding canopy and bomb releases (again, under the belly for the controls in the pylon that the Phantom kit mounts on.)

1/32 Tamiya Mitsubishi A6M Riesen “type Zero” fighter. Tiny super-strong magnets are said to hold the moving pieces in place, and there’s a hidden socket for a crank to operate the gear… or so I have read.

1/32 Revell Grumman F4F-4 Wildcat. Not only retractable, the complex multi-link F3F and F4F setup that brought the wheels up to sit flush with the lower sides of the fuselage. I keep meaning to buy one of these and see how well it works…

1/32 planes that do NOT have working retractable landing gear:

1/32 Revell Hawker Hurricane I or “II” (its not a II and would take much effort- buy a 2 hand copy of the original Mk I kit if you want one of these…)

1/32 Revell Hawker/BAe Harrier / AV-8A. If I’d been in charge… but I wasn’t. Not retractible. The Airfix 1/24 kits has retractible gear, but other issues.

1/32 Revell Bristol Beaufighter. Alas, this would be a good place for a home-made setup, dead easy, but not the way they made the kit. Very much tooled to a price, with just about nothing in the fuselage (and no way to see it…) Still how cool is it to have this?!

Yesterday’s search terms.

x-4 bantam cockpit 2
light gull grey acrilico 2
islader 1/72 2
polly scale paints 2
tamiya u.s. interior green mix 2
thinning vallejo 26.526 1
mosquito de interior 1
how to dull the finish of a plastic model? 1
trislander 1
paint striper for plastic models 1
eclipse tptp vs netbeans profiler 1
water based model paint 1
bac 707 gray 1
hawk 75 cutaway 1
how long does it take to build plastic models 1
diluting water based paint for glaze 1
how to mix model paints 1
hobby shops in san francisco 1
“…the place god calls you to is the place where your deep gladness and the world’s deep hunger meet.” -frederick buechner 1
xf-56 1
tamiya spray paint solvents 1
future floor wax remover 1
building plastic model links 1
r/c car store in bay area 1
mosquito fuselage 1
elo easy lift off 1
sbd-5 camouflage 1
mosquito instrument panel 1
polly scale model railroads paints 1
airplanes painted black 1
who bought out hobby enterprises model airplane kits 1
deionized water acrylic paints 1
rc cars in bayarea 1
1/32 model airplanes with working retractable landing gear 1

Recursion III, using Java


Here’s a Java example of the classic recursion/tree/web traversal. Note that this uses an array of other nodes, not just Left and Right, so you can make n-link webs as well as proper trees using this example.

The method interMed() is used to avoid having to make the data structures static- there is much I have yet to learn about Java! But I can manage this, and that feels pretty good!

/*
recurse.java

Recursive tree/web traversal, in Java. No explicit pointers, so I state that
the array of pointers to nodes is an array of nodes, and treat it as such.
Is it really pointers if I believe it is but can't see them? Its like String
Theory...

Original 11:58am 4/21 Bill4

*/

import java.util.ArrayList;

public class recurse {

public class node { String name; ArrayList kids; };
public class leveledName { String name; int level; };

ArrayList nLs = new ArrayList ();

public void recur ( node n, int level ) {

// System.out.println( "recur " + n + " level " + level );
leveledName lN = new leveledName();
lN.name = n.name;
lN.level= level;
nLs.add( lN );

for ( int i = 0; i < n.kids.size(); i++ ) { // better way to do this?

recur( n.kids.get(i), level + 1 );

} // for int i...

} // recur function

public void interMed() {

node Q = new node(); Q.name = "Q";
Q.kids = new ArrayList ();
// System.out.println( Q );

node S = new node(); S.name = "S";
S.kids = new ArrayList ();
// System.out.println( S );

node T = new node(); T.name = "T";
T.kids = new ArrayList ();
// System.out.println( T );

node N = new node(); N.name = "N";
N.kids = new ArrayList (); N.kids.add(Q);
// System.out.println( N );

node P = new node(); P.name = "P";
P.kids = new ArrayList (); P.kids.add(S); P.kids.add(T);
// System.out.println( P );

node M = new node(); M.name="M";
M.kids = new ArrayList (); M.kids.add(N); M.kids.add(P);
// System.out.println( M );

recur( M, 0 );

int maxLevel = 0;
for ( int i = 0; i maxLevel) {
maxLevel = ((nLs.get(i)).level );
} // if ...
} // for ...

for (int j = maxLevel; j > -1; j-- ) {
// System.out.println( "j " + j );
for ( int i = 0; i < nLs.size(); i++ ) {
// System.out.println( "j " + j + " i " + i );
if ( j == (nLs.get(i)).level ) {
System.out.printf( "%s %d \n", (nLs.get(i)).name,
(nLs.get(i)).level );
}
} // for i...
} // for j...

} // fn interMed

public static void main ( String args[] ) {

recurse r = new recurse();
r.interMed();

} // main

} // class recurse

Recursion, working it out in advance


In a recent pair of interviews, I was asked tree data structure questions, and I flubbed the first one. Hacking at a function that received a pointer to a node and that I needed to use as the launching point for recursion, not the recursive bit itself. Not pretty. NEXT time, I managed to gather up my wits, with a bit of help from my interviewer, Jim Gill, I managed to thread the needle and there it was, a recursive operation that worked. Sho-‘nuf!  That original is at the bottom of this post- a complete, working version, follows this introduction. Its about 180 lines, with a lot of white space.

And here’s the deal. You can’t make  a sensible recursive routine by simply getting the pointer and recalling that top level routine. YES recursion needs something that takes a pointer to node, and yes,  you call it with a child of the original node. But there’s more to it. A non-recursive superstructure which supports a recursive heart.

So here’s a complete, working, version, that compiles and runs using “gcc” on Mac OS 10.5.8. It takes a bit more than what I started with. “C” and other versions will follow, as separate postings.

Macintosh-6:interview Bill4$ cat recursion_v.cpp
/* recursion_v.cpp */
/* Follow-up to ___ recursion problem with Jim Gill, web prowling question at ____ */

/* input:
(M)
|   \
(N)  (P)
|  \    \
(Q) (S)  (T)
(3 level b tree, M has two children, N and P, and N has two children, Q and S.  P has one child – T.)

output:
Q, S, T, N, P, M

*/

#include <iostream>
#include <vector>

/* Structure in which the input data arrives: */

struct node {
std::vector <node*> children;  std::string name;
};

/* Structure the result vector (array) is built from: */
struct nameNLevel  {
std::string name;   int level;
};

/*
* Synopsis: void recur( node* n, int level, std::vector* nsNLs )
* args:
* node*    n     this node, which has a name, may have children
* int        level    number of steps down the tree
* std::vector    nsNLs   pointer to the vector of node-name, level structs we’ll want to report
* returns:
* no return value. Node name and level are put into the vector of nameLevel structs.
* Mar 27, 2011  Bill Abbott
*/

void recur( node* n, int level, std::vector <nameNLevel>* nsNLs ){

/* To collect additions, nsNLs vector must be passed as a pointer! */
/* Unlike an array in C, an std::vector isn’t passed as a pointer automatically! */
nameNLevel* nNL = new nameNLevel;
nNL->name = n->name;
nNL->level = level;
nsNLs->push_back( *nNL );

int vecIdx = nsNLs->size() – 1;

//    std::cout << nsNLs->size() << ”  ” << vecIdx << ”    “;
std::cout << (*nsNLs)[ vecIdx ].level << ”  “;
std::cout << (*nsNLs)[ vecIdx ].name << ”  “;
std::cout << (*nsNLs)[ vecIdx ].name.size() << ”  “;
std::cout << (*nsNLs)[ vecIdx ].name.c_str() << ”    “;

std::cout << (nsNLs->back()).name << ”  ” << (nsNLs->back()).level << ”  ” << n->name << ”  ” << level << ”  “;
std::cout << nsNLs->size() << ”  ” ;
std::cout << n->children.size() << ”  ” << (0 != n->children.size()) << “\n”;
if ( 0 != n->children.size()) {   /* there are children */
for (int childCount =0; childCount < ( n->children.size()); childCount++ ){
recur(  n->children[childCount], level+1, nsNLs ); /* recursive call- children & next level… */
} /* for int childCount… */
} /* if ( 0!=  */

} /* recur *

/*
* Synopsis: void passThrough( node* n )
* args:
* node*    n     this node, which has a name, may have children
* returns:
* no return value. creates and outputs vector of node names,
* “highest” level first, in ascending order of child vector contents..
* Mar 27, 2011  Bill Abbott
*/

void passThrough( node* n ) {
std::vector namesNLevels;
int level = 0;

recur( n, level, &namesNLevels );

std::cout<< namesNLevels.size()  << ”  ” << “\n”;

int maxLevel = 0;
for (int i=0; i < namesNLevels.size(); i++ ) {
std::cout<< maxLevel << ”  ” << i << “\n”;
if (namesNLevels[i].level > maxLevel) {
maxLevel = namesNLevels[i].level;
} /* if */
} /* for */

/* note: recursion isn’t getting the data in the order we want… */
/* so, order them before printing. */

for (level=maxLevel; level >= 0; level–){
for (int i=0; i < namesNLevels.size(); i++ ) {
if (namesNLevels[i].level == level){
std::cout << namesNLevels[i].name <<  ” “;
} /* if (namesNLevels…) */
} /* for i */
} /* for level */

printf( “\n”);

}

/*
* Synopsis: int main( int argc, char* argv[] )
* args:
* int        argc    count of command line arguments
* char*    argv[]    vector of zero-terminated arrays of char containing command line args
* returns:
* no return value. creates a tree of nodes, outputs vector of node names,
* “highest” level first, in ascending order of child vector contents..
* Mar 27, 2011  Bill Abbott
*/

int main( int argc, char* argv[] ) {

/* 3 level b tree:
* M has two children, N and P, and
*    N has two children, Q and S.
*        Q has no children
*        S has no children
*    P has one child – T.
*        T has no children
*/

node* T = new node;
T->children.clear();
T->name = “T”;

node* S = new node;
S->children.clear();
S->name = “S”;

node* Q = new node;
Q->children.clear();
Q->name = “Q”;

node* P = new node;
P->children.push_back(T);
P->name = “P”;

node* N = new node;
N->children.push_back(Q);
N->children.push_back(S);
N->name = “N”;

node* M = new node;
M->children.push_back(N);
M->children.push_back(P);
M->name = “M”;

passThrough( M );

return( 1 );

————- Example output, with my debug couts—————-

Macintosh-6:interview Bill4$ c++ recursion_v.cpp
Macintosh-6:interview Bill4$ a.out
0  M  1  M    M  0  M  0  1  2  1
1  N  1  N    N  1  N  1  2  2  1
2  Q  1  Q    Q  2  Q  2  3  0  0
2  S  1  S    S  2  S  2  4  0  0
1  P  1  P    P  1  P  1  5  1  1
2  T  1  T    T  2  T  2  6  0  0
6
0  0
0  1
1  2
2  3
2  4
2  5
Q S T N P M
Macintosh-6:interview Bill4$

————————– Here’s how this started:——————–

Ok- it was whiteboard code and didn’t compile. I’m working on that. Staring with std::vector blahblah  which seems like some really kewl Java/C++ library good stuff. What Kernighan and Ritchie were hoping for.

input:
(M)
|     \
(N) (P)
|     \    \
(Q) (S) (T)
(3 level b tree, M has two children, N and P, and N has two children, Q and S.  P has one child – T.

output:
Q, S, T, N, P, M

typedef struct node {
std::vector <node*> children;  std::string name;
}

typedef nameNLevel {
std::string name;   std::int level;
}

void passThrough( node* n ) {
std::Array namesNLevels;
int level = 0;

recur( n, level, namesNLevels );

int maxLevel = 0;

for (int i=0; i
if (namesNLevels[i].leve l> maxLevel) {
maxLevel = namesNLevels[i].level;
} /* if */
} /* for */

/* note: recursion isn’t getting the data in the order we want… */
/* so, order them before printing. */

for (level=0; level =<maxLevel; level++){
for (i=0; i<
if (atoi(namesNLevels[i].name) == level){  printf( “%s “, namesNLevels[i].name } /* longer but more robust */
} /* for i */
} /* for level */

printf( “\n”);

}

void recur( node* n, integer level, std::Array nsNLs ){
/* its an array, gets passes as a pointer anyhow */
nsNLs.pushback( new nameNLevel( n->name, level));

if ( 0 != n->children.count()) {   /* there are children */
for (int childCount =0; childCount < ( n->children.count()); childCount++ ){
recur(  n->children[childCount], level+1, nsNLs );
/* recursive call- children & next level… */
} /* for int childCount… */
} /* if ( 0!=  */

}

A nice page at IBM regarding recursion:

http://www.ibm.com/developerworks/linux/library/l-recurs.html#

Good stuff!