From: nullplan@gmx.net   
      
   Well, I know of the following story: I was tasked with writing a program   
   that would calculate some distance between strings (It wasn't   
   Levenshtein's, but I don't know which it was anymore). It was the exam   
   for a course at University, so there were many implementations already,   
   but me and a fellow student wrote our own versions (how many people   
   copied his is unknown to date, but doesn't really matter). To test our   
   implementations, we were given two strings, each 10000 bytes long (some   
   genome sequences of fungi or so...).   
      
   The algorithm consisted basically of creating a matrix with the same   
   dimensions of the two strings and then doing strange stuff to it. The   
   professor didn't just want the score to be put out, but also the   
   "alignment" that would be retrieved through backtracing (i.e. I had to   
   create _two_ matrices, one for the score and one for the way to get it).   
   This alignment would output a whole lot of strings, because for each   
   cell there would be up to three ways to get in, so the upper bound for   
   just the number of strings was in O(3^n). Exponential growth is a bitch,   
   I can tell since then: The output would have been something like 1.5TB   
   (unavailable to me). (And the upper bound for output string length was   
   the sum of the dimensions).   
      
   My implementation didn't use the STL, not even for output. I learned   
   programming with Pascal, later continued with C and stuck to it. The   
   professor demanded C++ to be used, so I basically wrote C code with   
   strange include directives (i.e. "" instead of "").   
   It would have done job, had there been enough space on disk. When I ran   
   the program with the test strings, output started approximately ten   
   seconds after launch and wouldn't stop for a while (which means that it   
   took ten seconds to fill those arrays). My machine is a Lenovo ThinkPad   
   T61 with an Intel Core 2 Duo at 2.1GHz and 2GB of RAM plus 2GB of swap.   
   Since I knew exactly where memory was allocated and how much, I could   
   estimate the memory usage of the program at 20kB for the output string   
   buffer and two times four times a hundred million bytes, so around 800MB   
   for that specific input.   
      
   My fellow did use the STL, heavily. He's one of the guys that, when   
   tasked with something unknown to them, starts writing the stuff anyway   
   and hopes Google will put him out of his miseries if he gets stuck   
   (instead of, as I'd do, read on how to do it first and write then). For   
   some reason he couldn't figure out, the program just started chugging up   
   memory until it was depleted, and swap space shortly afterwards, leading   
   to it being killed by kernel. It took approximately ten minutes to get   
   there, and it would output the score  and nothing else (presumably he   
   tried to form the entire output in one string, leading to trying to   
   accumulate 1.5TB in memory. I'd be happy to have that much in disc   
   space!). His machine is an Acer EEE PC with an Intel Atom (don't know   
   how fast, though I would guess it's 1GHz) and 1GB of RAM, supplemented   
   by 2GB of swap space.   
      
   Well, we both passed. I guess the professor didn't use that big an input   
   in the end.   
      
   CYA,   
   Markus   
      
      
   --   
         [ See http://www.gotw.ca/resources/clcm.htm for info about ]   
         [ comp.lang.c++.moderated.    First time posters: Do this! ]   
      
   --- SoupGate-Win32 v1.05   
    * Origin: you cannot sedate... all the things you hate (1:229/2)