Project FAQ

You say that an insert fails (and must output 'F') if one attempts inserting an element which is already in the dictionary - but isn't that deviating from the traditional behavior of a dictionary?

Unfortunately, as it's the case for most other definitions and terminology, there isn't any one way of doing this. It's application-dependent which behavior is chosen as default. I would like you to follow my guidelines, but of course you can add an option to your program which will make it behave however you prefer.

Should the input be given on runtime or read from a text file?

This question may be due to limited familarity with linux. The project description says that the programs should read from stdin. In the linux world, this is the most flexible, since one can then provide data directly in the terminal window or redirect data from a file to the program or pipe the data into the program from some other application. For the same reasons, the program should write to stdout.

For scapegoat trees, should the alpha be given by the user every time?

For (my) testing, it is most convenient if can be provided on the command line (as an option), but I'll accept it being defined as a constant in the top of the source file.

Is it OK if I use Haskell?

Yes. Be extra careful, though, not to "cheat" by using (too) high-level constructions. If your starting point is the standard algebraic data type for a binary tree (in the case of scapegoat trees), it should give the same feel and implementation process. To argue that the asymptotic complexity is as it is supposed to be using a language such as Haskell, one typically has to be beyond novice level.

What do you mean by "variation in search complexity"?

When you search for some key 42, you may have to follow 10 pointers. However, if you search for 87, you may have to follow only 8 pointers. It varies depending on what the structure looks like. I suggest building a (large) structure, then perform many searches (10,000, for instance), and look at the histogram where the number of pointers followed (8 and 10, for example) are on the x-axis, and the number (out of these 10,000) of searches that used 8 (or 10) searches is the height of each block in the histogram. If it becomes too flat, one can accumulate to see the result better, i.e., instead of a block showing the number of searches following 8 pointers, say, it shows the number of searches following at most 8 pointers. One can iterate the entire process to reduce the dependency of how any one structure happened to be built.