Problem Description The Horspool’s algorithm is an algorithm for finding a substring (called a pattern) inside of a string (called a text). The pattern length is m and the text length is n. Horspools is a simplification of the Boyer-Moore string search algorithm and requires taking up more space (memory) […]
Algorithms
4 posts
Problem Description Prim’s algorithm uses the greedy approach to connect n points in the cheapest possible way to make a path. The greedy approach suggests a “greedy” grab of the best alternative available in the hope that a sequence of optimal choices will yield an optimal solution to the whole […]
Problem Description Given n items of known weights (w1,….,wn) and values (v1,…,vn) and a knapsack of capacity W, find the most valuable subset of the items that fit into the knapsack. The 0-1 Knapsack Problem can be solved using the brute-force exhaustive search technique where you must find all 2n […]
Give change for amount (n) using the minimum number of coins of denominations (d1 < d2 < … < dm). There is also a greedy algorithm to solve this problem but this post is on the dynamic programming technique algorithm. In this problem, we assume that there is an unlimited […]