Binomial coefficient

Compute the binomial coefficient

Catalan numbers

Compute the catalan numbers

Integer Knapsack

A knapsack has max capacity C and there are n items each with weight wi, and value vi. Maximize the value in the knapsack without exceeding its max capacity

Jump stairs

There ia stair with n steps. You can climb either one step or two steps at a time. How many different ways there are to climb the stair?

Edit distance

Compute the edit distance

Dice

Given a dice count how many ways to get sum s

Palindromes

Given a string find the minimum number of characters to be inserted for converting the string into a palindrome.

Bridge matching

N cities are on the northern bank of a river and n cities are on the southern bank. You can build a bridge only between cities with the same number

Sum subset

Given an array of integers of size n, partition it in such a way that the two subsets have equal sum s.

Partition set

Partition a multiset S of positive integers into two subsets S1 and S2, such that the sum of the numbers in S1 equals the sum of the numbers in S2

Segment partition

Given a segment of integer length n, cut into different integer parts in such a way to maximize the product of the lengths of all parts

Cutting a rod

Given a rod of length n and a vector of prices for different lengths, cut the rod for maximizing the gain

Max matrix 0/1

Given a matrix consisting only of 0 and 1 find the maximum size square submatrix with all 1.

Matrix parentization

Given a set of m matrices find the most efficient way of multiplying them

Max submatrix

Given a matrix of size n x n fine the maximum sum rectangle

BST and dynamic programming

Given a binary search tree, find the size of the largest independent set of nodes

Games of coins

A set of coins are aligned and two players can pick one coin from each side in turn. Maximize the value of the coins picked by the first player

Maximum value contiguous subsequence

Given an array of real numbers, find a contiguous subsequence with max sum S

Stock prices

Given an histogram array of unsigned integers encoding the price of a stock title during previous year, compute the area for the largest rectangle contained in this histogram

Ship battle

Given a matrix M and an array V match the array in the matrix

Scheduling

Given n jobs, each one with a processing time t1 a profidt p1 and a deadline di maximize the profit

Boolean parentesization

Given a boolean expression of AND, OR, XOR, TRUE, FALSE find the number of ways to parenthesize and evaluate to true

Balanced partition

Given an array of integers between 0 and M divide the integers into two sets such that the difference of their sum is minimized