TDD like approach to Algorithmic problems

I one failed at an algorithmic test with Codility because I tried to find a better solution, and in the end I had nothing.

So it made me think if I could use an approach similar to TDD? I.e. If I can usually develop a solution gradually in similar fashion?

If I were writing a sorting algorithm I could move from a standard Bubblesort to a 2-way bubblesort, but then something more advanced like Quicksort would be a "quantum leap", but at least I would have testdata I can easily validate.

Other tips for such tests? One thing I would do the next time is to use more methods/functions than inner loops. For example, in sorting, you often need a swap. If it were a method I would just need to modify the calling code. I could even have more advanced solutions as derived classes.

With "Algorithmic" vs "normal" problems I mean problems where Time-complexity is important. So instead of passing more tests as in TDD, you would make it "behave better".

With "similar to TDD" I mean:

1. Write relatively automatic test to save time on manual tests pr increment.
2. Incremental development.
3. Regression testing, ability to detect if code breaks or at least if functionality changes between increments.

I think this should be quie easy to understand if you compare

1. Writing a shell-sort directly
2. Jumping from bubblesort to quicksort (Total rewrite)
3. Moving incrementally from a one-way bubble-sort to shell sort (If possible).
• What do you mean by "similar to TDD"? You can obviously trying to use TDD for developing a sorting function, and then use the unit tests to validate the function still works when you replace the sorting algorithm by a more efficient one, but it sounds like you have a different question in mind? Jan 10, 2017 at 12:03
– Olav
Jan 10, 2017 at 12:08
• Sure you can try to solve lots of problems with a working (but not very efficient) solution first, then improve it. This is in no way restricted to algorithmic or programming problems, and it has not much in common with TDD. Does this answer your question? Jan 10, 2017 at 12:14
• @DocBrown No - See Bubblesort/Quicksort example. TDD "works" well because an incremental approach works well for many types of problems. Algoritmic problems might be different.
– Olav
Jan 10, 2017 at 12:25
• So you meant "is is possible to solve algorithm design questions in an incremental manner" (just as TDD is an incremental approach), and not "by TDD", right? Please clarify. Jan 10, 2017 at 15:19

See also Ron Jeffries's attempt to create a Sudoku solver with TDD, which unfortunately didn't work.

Algorithm requires a significant understanding of algorithm design principles. With these principles it is indeed possible to proceed incrementally, with a plan, like Peter Norvig did.

In fact, for algorithms requiring non-trivial design effort, it is almost always that the effort is incremental in nature. But each "increment", which is tiny in the eyes of an algorithm designer, looks like a quantum leap (to borrow your phrase) to a person who hasn't had the same expertise or knowledge with this particular family of algorithms.

This is why a basic education in CS theory combined with lots of algorithm programming practice are equally important. Knowing that a particular "technique" (small building blocks of algorithms) exists is a long way toward making these incremental quantum leaps.

There are some important differences between incremental progress in algorithms and TDD, though.

One of the difference has been mentioned by JeffO: A test that verifies the correctness of the output data is separate from a test that asserts the performance between different implementation of the same algorithm (or different algorithms vying to give the same solution).

In TDD, one adds a new requirement in the form of a test, and this test shall initially not pass (red). Then the requirement is satisfied (green). Finally the code is refactored.

In algorithm development, the requirement usually doesn't change. The result correctness verification test is either written first, or shortly after a draft (highly confident but slow) implementation of the algorithm is completed. This data correctness test is seldom changed; one does not change it to fail (red) as part of the TDD rite.

However, in this aspect, data analysis is distinctly different from algorithm development, because data analysis requirements (both the input sets and the expected outcomes) are only defined loosely in human understanding. Thus the requirements change frequently on a technical level. This rapid change puts data analysis somewhere between algorithm development and general software application development - while still algorithm-heavy, the requirements are also changing "too fast" to the taste of any programmer.

If the requirement changes, it typically calls for a different algorithm.

In algorithm development, changing (tightening) the performance comparison test to fail (red) is silly - it does not give you any insight about potential changes to your algorithm that would improve performance.

Therefore, in algorithm development, both the correctness test and the performance test are not TDD tests. Instead, both are regression tests. Specifically, the correctness regression test prevents you from making changes to the algorithm that will break its correctness; the performance test prevents you from making changes to the algorithm that will make it run slower.

You can still incorporate TDD as a personal working style, except that the "red - green - refactor" ritual is not strictly necessary in nor particularly beneficial to the thought process of algorithm development.

I would argue that algorithm improvements actually result from making random (not necessary correct) permutations to the data flow diagrams of the current algorithm, or mixing and matching them between previously known implementations.

TDD is used when there are multiple requirements that can be added incrementally to your test set.

Alternatively, if your algorithm is data-driven, each piece of test data / test case can be added incrementally. TDD would also be useful. For this reason a "TDD-like" approach of "add new test data - improve code to make it handle this data correctly - refactor" will also work for open-ended data analytics work, in which the objectives of algorithms are described in human-centric words and its measure-of-success also judged in human defined terms.

It purports to teach a way to make it less overwhelming than trying to satisfy all (dozens or hundreds) of requirements in a single attempt. In other words, TDD is enabled when you can dictate that certain requirements or stretch-goals can be temporarily ignored while you are implementing some early drafts of your solution.

TDD isn't a substitute for computer science. It is a psychological crutch that helps programmers overcome the shock of having to satisfy many requirements at once.

But if you already have one implementation that gives correct result, TDD would consider its goal accomplished and the code ready to be handed off (to refactoring, or to another programmer-user). In some sense, it encourages you not to prematurely optimize your code, by objectively giving you a signal that the code is "good enough" (to pass all correctness tests).

In TDD, there is a focus on "micro-requirements" (or hidden qualities) as well. For example, parameter validations, assertions, exception throwing and handling, etc. TDD helps assure the correctness of execution paths that aren't frequently exercised in the normal course of software execution.

Certain types of algorithm code contain these things as well; these are amenable to TDD. But because the general workflow of algorithm isn't TDD, such tests (on parameter validations, assertions, and exception throwing and handling) tend to be written after the implementation code has already been (at least partially) written.

• What do the first two quoted words in your post ("Uncle Bob") mean? Jan 10, 2017 at 20:17
• @RobertHarvey According to Uncle Bob, TDD can be used for algorithm discovery. According to another luminary, it doesn't work. I thought that both should be mentioned (i.e. anytime someone mentions one example, one is also obliged to mention the other example) so that people get balanced information about positive and negative examples. Jan 10, 2017 at 20:19
• OK. But you do understand my confusion? Your first paragraph appears to be quoting someone uttering the words "Uncle Bob." Who is saying that? Jan 10, 2017 at 20:29
• @RobertHarvey order complied. Jan 10, 2017 at 20:50

For your problem, you would have two tests:

1. A test to make sure the algorithm is still accurate. e.g. Is it sorted correctly?
2. Performance comparison test - has the performance improved. This can get tricky, so it helps to run the test on the same machine, same data and limit the use of any other resources. A dedicated machine helps.

What to test or full test coverage is debatable, but I think the complex parts of your application that need to be fine-tuned (get changed a lot) are perfect candidates for automated testing. These parts of the application are usually identified very early. Using a TDD approach with this piece would make sense.

Being able to solve complex problems shouldn't be hindered by a reluctance to try various approaches. Having an automated test should help in this area. At least you'll know you're not making it worse.

So instead of passing more tests as in TDD, you would make it "behave better".

Sort of.

You can test for run time and complexity. Runtime tests will need to be a little forgiving to allow for contention on system resources. But, in many languages, you can also override or inject methods and count actual function calls. And, if you're confident your current algorithm is suboptimal, you can introduce a test that simply demands that `sort()` invoke `compare()` fewer times than the naive implementation.

Or, you can compare `sort()` on two sets and ensure they scale in `compare()` calls by your target complexity (or thereabouts, if you expect some inconsistency).

And, if you can theoretically prove that a set of size `N` should require strictly no more than `N*log(N)` comparisons, it might be reasonable to restrict your already-working `sort()` to `N*log(N)` invocations of `compare()` ...

However ...

Meeting a performance or complexity requirement doesn't ensure that the underlying implementation is {AlgorithmX}. And, I'd argue that this is normally OK. It shouldn't matter what algorithm is used, provided you hit your implementation meets your requirements, including any important complexity, performance, or resource requirements.

But, if you want to ensure a particular algorithm is used, you'll need to be more tedious and get much more in depth. Things like..

• Ensuring that exactly the expected number of calls to `compare()` and `swap()` (or whatever) are made
• Wrapping all major functions/methods and ensuring, with a predictable data set, that the calls occur in exactly the expected order
• Examining working state after each of N steps to ensure it changed exactly as expected

But again, if you're trying to ensure that {AlgorithmX} is used in particular, there are probably features of {AlgorithmX} you care about that are more important to test than whether {AlgorithmX} was actually used in the end ...

Also bear in mind, TDD doesn't negate the necessity of researching, thinking, or planning in software development. It also doesn't negate the need for brainstorming and experimentation, even if you can't easily assert on your Googling and whiteboarding in your automated test suite.

• Excellent point regarding the possibility of asserting bounds on number of operations. I would argue that it's the power of (mocks, stubs and spies), something which can be used in TDD, which can also be used in other kinds of tests. Jan 10, 2017 at 20:53
• I don't see much point in writing tests before code in a test scenario. It is usually a last criteria after functional criteria are met. Sometimes you might do random numbers first and worst case after, but still writing test would take a long time compared to a some clever printouts. (With some statistics you could probably write some generic code, but not during a test) In the real world I think you would want to know if performance suddenly decreases in certain cases.
– Olav
Jan 10, 2017 at 21:41
• If you look at codility.com/programmers/task/stone_wall you would know if you have more than N complexity, except for special cases where you have to work over very longs spans for example.
– Olav
Jan 10, 2017 at 21:56
• @Olav "writing test would take a long time compared to a some clever printouts" ... to do once ... uhh .. maybe, but also very debatable. To do repeatedly at every build? ... Definitely not. Jan 17, 2017 at 14:59
• @Olav "In the real world I think you would want to know if performance suddenly decreases in certain cases." In live services, you'd use some like New Relic to monitor overall performance -- not just of certain methods. And ideally ,your tests will tell you when performance-critical modules and methods fail to meet expectations before you deploy. Jan 17, 2017 at 15:01