Go Go Gnome

the website of Sander Kooijmans

Posted: April 04, 2016

On Saturday April 16, 2016 I will give a presentation called "Dynamic Programming: The technique behind the diff tool explained" at NextBuild 2016 in my old home town Eindhoven.

On Wednesday June 29, 2016 I will give a workshop: "How invariants help writing loops" at the Clean Code Days 2016 in Munich. The next day I will give a presentation: "Let tests drive or let Dijkstra derive?" at the same conference.

Have you ever wondered how the diff tool in your favorite IDE determines so quickly the differences between two versions of a file? The technique used by the diff tool is called dynamic programming.

In this presentation Sander explains dynamic programming and for what type of problems you can apply this technique. One of these problems is determining the difference between two strings, which is the base of the diff tool.

Donâ€™t expect to see yet another framework to build an impressive user interface, but learn writing algorithms that produce business value for your clients.

This talk presents an old technique for writing correct code: invariants. Invariants can be used to prove the correctness of a loop after the loop has been written. They can also help writing a loop from scratch.

It turns out that algorithms like Binary Search and Quicksort can be written down easily when starting from invariants. Invariants are a tool every software craftsman should know.

After an explanation of invariants you will practice this technique in your favorite language.

Bring your own laptop with your favorite IDE to this workshop so you can practice this technique yourself. Not planning to bring your laptop to the workshop? Then bring paper and pen instead!

Test-Driven Development is presented as the one and only way to write code. Some people consider you not a professional software developer if you do not use it. Uncle Bob uses TDD to solve the Primes Kata with just three lines of code. These three lines were justified by only seven tests. However, tests have one big problem: tests can only prove the presence of bugs, not their absence. So how does TDD help you writing correct programs?

Prof. E.W. Dijkstra, winner of the Turing Award, developed a formal way of deriving and proving algorithms. Formal proofs are constructed with pre- or postconditions. Rules to prove the postcondition of a single assignment and a single if-statement are shown. Using an invariant and a bound function the postcondition of a while-loop can be proved. Using these simple rules a solution of the Primes Kata is derived.

The formal proof of the correctness for these three lines make one thing clear: seven tests are not sufficient to prove this algorithm!

Do not fear very detailed and formal mathematical proofs. The derivations are presented in a practical and informal way.