Using Skiena's The Algorithm Design Manual
In The Algorithm Design Manual, Skiena outlines heuristics for solving problems involving algorithms contained in the book. The heuristic starts with modelling the problem by looking at the constraints and the needs of the software and the business. Once a model has been established, the portion of the book titled "The Hitchhiker's Guide to Algorithms" serves as a reference for commonly used algorithms. From there, a few key steps are broadly outlined in the book for implementing the algorithm chosen. It is beneficial to walk through the process of implementing an algorithm to get an idea of what it might look like to, for example, use the longest common subsequence (lcs) in Golang.
Skiena recommends that the Stony Brook Algorithm Repository be the first place to look for existing implementations of an algorithm in a specific language. Some of the resources provided are even rated by the quality of the implementation. The usefulness of the Repository is limited by the completeness of the references, for not every implementation of commonly used algorithms can be found in the Repository. Currently, the lcs algorithm in Go is not included in the Repository. While implementing the algorithm from either the descriptions, pseudo-code, or example from the book is a viable option at this juncture, it may be worthwhile to continue searching for an existing implementation elsewhere.
One existing implementation comes with benchmarks of alternative implementations of lcs. Lcs can be solved recursively, but as with any recursive code, as calls increase, the time taken increases significantly. Dynamic programming aims to reduce the upper limit of the time an algorithm takes by using more memory to store previously computed values, which implies the need for some logic for storing information and some logic for looking up information needed to solve a related problem. Dynamic programming also gives us a top-down approach and a bottom-up approach for replacing the recursive logic, and the benchmarks check for differences in performance. While the benchmarks provide some guarantee that the implementation works, they are not a substitute for tests.
When writing tests, it's important to check for possible edge cases. For an implementation that works most of the time, writing tests guarantees that the code behaves as expected, even when refactoring logic. In addition to writing tests, stepping through the code enhances an understanding of how the data-structure stores computed values. In Visual Studio Code, setting break-points at the outer for-loop will show how the stored values change on each iteration of the loop; however, this IDE does not display nested tables side-by-side. To imagine the table of values updating on each iteration, it's easiest to start with short strings as arguments when calling the LCS function.
From there, if necessary, gradually increase the lengths of the arguments until, by inductive reasoning, it's clear how the code works. In addition to the discussion of proofs Skiena asks the reader to convince themselves of certain ideas. Stepping through code exposes the concrete changes to the underlying data structures of an algorithm; consequently a better understanding of the algorithm itself is fostered.
After this research, developing an implementation for lcs in Go was the best choice. This particular repository of Go algorithms is linked to by the Stony Brook Algorithm Repository. Contributing to implementations of algorithms makes it easier for future developers who were in the same position before, and it's definitely worth considering.
Further reading: