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.
The least squares problem is described as follows:
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
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.”
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.