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.

# Monthly Archives: October 2013

# Segmented Least Squares Problem

The **least squares problem** is described as follows:

Given n points in the plane: (x_{1}, y_{1}), (x_{2}, y_{2}), …, (x_{n}, y_{n}), find a line y = ax + b that minimizes the sum of squared errors:

SSE = sum_{1 ≤ i ≤ n}(y_{i} – ax_{i} – b)^{2}

# 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.”*

# 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 w_{i} and the goal is to find the maximum-weight subset of compatible requests. It degenerates to the interval scheduling problem when w_{i} = 1 ∀i.