Turnpike Problem (F#)

The Problem This is a problem for which no polynomial time solution exists, although a pseudo-polynomial (polynomial in the degree of the maximum element) does exist. In this paper, the algorithm proposed for the sum-function with full information is simple enough. For the original problem with the difference funcition, the algorithm is simple as well: … Continue reading Turnpike Problem (F#)

Decomposition Problem with F#, Dynamic Programming

As my former boss and mentor used to say, in order to understand recursion one must first understand recursion. This is funny, ha-ha, but if we tweak it slightly we get a really useful statement: in order to understand dynamic programming, one must first understand recursion. Here is an example. Sources Github: http://github.com/fierval/BioInfo Decomposition Problem … Continue reading Decomposition Problem with F#, Dynamic Programming

Motif Finding with Gibbs Sampling (F#)

The Problem "Motif finding is a problem of finding common substrings of specified length in a set of strings. In bioinformatics, this is useful for finding transcription binding sites" (recap here). The problem is succinctly stated on Rosalind. Given a set of strings DNA of size t, find "most common" substrings of length k. "Most common" means, that substrings … Continue reading Motif Finding with Gibbs Sampling (F#)

Modelling Stochastically Independent Processes with F# Computation Expressions: Part 2

Code for this entry: here. In this first part, we started shamelessly plagiarizing creatively reproducing a Clojure monad that does a great job describing stochastically independent processes. After a few trials I became convinced, that the approach in the blog post mentioned above was indeed optimal: a "natural" approach of modelling an event as a … Continue reading Modelling Stochastically Independent Processes with F# Computation Expressions: Part 2

Modelling Stochastically Independent Processes with F# Computation Expressions: Part 1

The idea for doing this is not new. There is an excellent series of posts closely tracing an article on applications of functional programming to probability. A colleague of mine has recently called my attention to his own post of two years ago, where he describes a monad that models stochastically independent events in Clojure. … Continue reading Modelling Stochastically Independent Processes with F# Computation Expressions: Part 1