Matching Nuts and Bolts Problem

Matching nuts and bolts problem can be stated as follows: “Given a collection of n nuts of distinct sizes and n bolts such that there is a one-to-one correspondence between the nuts and the bolts, find for each nut its corresponding bolt.” We can only compare nuts to bolts i.e., we can neither compare nuts to nuts nor bolts to bolts.

Continue reading

Advertisements

Segmented Least Squares Problem

The least squares problem is described as follows:

Line of Best Fit

Line of Best Fit

Given n points in the plane: (x1, y1), (x2, y2), …, (xn, yn), find a line y = ax + b that minimizes the sum of squared errors:

SSE = sum1 ≤ i ≤ n(yi – axi – b)2

Continue reading

Water Jug Problem

The Water Jug problem can be stated as follows: “Given two unmarked jugs having capacities ‘a’ and ‘b’ liters respectively and a target volume ‘t’ liters, find the moves that get exactly ‘t’ liters in any of the two jugs.”

Continue reading

Weighted Interval Scheduling Problem

Unlike the Interval Scheduling Problem where we sought to maximize the number of requests that could be accommodated simultaneously, in the Weighted Interval Scheduling Problem, each request i has an associated value or weight wi and the goal is to find the maximum-weight subset of compatible requests. It degenerates to the interval scheduling problem when wi = 1 ∀i.

Continue reading