Contents tagged with algorithm
-
Solving SPOJ 346. Bytelandian Gold Coins (COINS) with Dynamic Programming and F#
The Bytelandian Gold Coins problem, officially published in SPOJ, is centered around computing the maximum dollars that can be exchanged for a Bytelandian gold coin. In this post, we outline a solution to this problem with memoization and F#.
Interpretation
The problem definition enforces following rules to perform the exchange. Consider, a Bytelandian gold coin--
It can be exchanged to three other coins, i.e.,coins. Thus, coin
value in bytelandian gold coins.
Alternatively, Our objective is to derive an algorithm that maximizes the dollars exchanged from the gold coin -
Solving SPOJ 97. Party Schedule with Dynamic Programing and F#
The Party Schedule problem, published in SPOJ website, is about deriving an optimal set of parties that maximizes fun value, given a party budget:
and
where each party
have an entrance cost
, and is associated with a fun value
. In this post, we discuss how to solve this problem by first outlining an algorithm, and afterwards, by implementing that using F#. This problem is a special case of Knapsack problem. Main objective of this problem is to select a subset of parties that maximizes fun value, subject to the restriction that the budget must not exceed
have costs
such that
is as large as possible, and subject to the following restriction-- (read more)
-
Solving Subset Sum with Dynamic Programming and F#
The Subset Sum (Main72) problem, officially published in SPOJ, is about computing the sum of all integers that can be obtained from the summations over any subset of the given set (of integers). A naïve solution would be to derive all the subsets of the given set, which unfortunately would result in
time complexity, given that
is the number of elements in the set. This post outlines a more efficient (pseudo-polynomial) solution to this problem using Dynamic Programming and F#. Additionally, we post C# code of the solution...(read more)
-
Levenshtein Distance with F#
Definition. Edit Distance—a.k.a “Lavenshtein Distance”--is the minimum number of edit operations required to transform one word into another. The allowable edit operations are letter insertion, letter deletion and letter substitution ...(read more)
-
UVa 10706. Number Sequence with F#
This post describes an algorithm to solve UVa 10706: Number Sequence problem from UVa OJ. Before outlining the algorithm, we first give an overview of this problem in the next section... continue reading.
-
Collatz Problem a.k.a. 3n+1 Problem
This post focuses on Collatz problem, which is also known as, among others, the 3n+1 problem, and the Syracuse problem. Outline. We begin by introducing Collatz conjecture; afterwards, we presents an algorithm to solve the
problem (UVa 100 or SPOJ 4073) published in both UVa and SPOJ. The primary advantage of having it in SPOJ is that we can use F# to derive a simple and elegant solution; at the same time, we can verify it via SPOJ's online judge... continue reading.
