Skip to main content
Theoretical Computer Science

Return to Answer

replaced http://mathoverflow.net/ with https://mathoverflow.net/
Source Link
Community Bot
Community Bot
  • 1

Knapsack is pretty easy to grasp, especially for anyone who has had to deal with a small suitcase.. a nice example if they know dynamic programming.

Another fun (practically identical) one is Subset-sum, because it also has a nice physical interpretation: imagine the numbers being the distances of equal point-masses on an ideal (massless) ruler, with the fulcrum at the origin. Subset-sum says: does there exist a non-empty subset such that the ruler will remain balanced? (i.e., such that the center of gravity is the support point for the ruler?)

In both cases, it seems intuitive that naive strategies may force resorting to checking all subsets.

If they have more background, it's nice to grow problems by dropping constraints. For example, starting with a max flow problem, turning it into a linear program, and making it an integer program. (A great one of course is MAX-CUT, since to people with more background you can also bring up UGC; I touch some of this in an MO answer http://mathoverflow.net/questions/33036/is-quadratic-programming-still-np-hard-if-you-have-bounds-and-a-feasible-point/33048#33048https://mathoverflow.net/questions/33036/is-quadratic-programming-still-np-hard-if-you-have-bounds-and-a-feasible-point/33048#33048 .) Also there are neat things like problems seemingly similar which have vastly different complexity (Euler (edge) path is linear time, Hamiltonian (vertex) path is NP-complete).

Knapsack is pretty easy to grasp, especially for anyone who has had to deal with a small suitcase.. a nice example if they know dynamic programming.

Another fun (practically identical) one is Subset-sum, because it also has a nice physical interpretation: imagine the numbers being the distances of equal point-masses on an ideal (massless) ruler, with the fulcrum at the origin. Subset-sum says: does there exist a non-empty subset such that the ruler will remain balanced? (i.e., such that the center of gravity is the support point for the ruler?)

In both cases, it seems intuitive that naive strategies may force resorting to checking all subsets.

If they have more background, it's nice to grow problems by dropping constraints. For example, starting with a max flow problem, turning it into a linear program, and making it an integer program. (A great one of course is MAX-CUT, since to people with more background you can also bring up UGC; I touch some of this in an MO answer http://mathoverflow.net/questions/33036/is-quadratic-programming-still-np-hard-if-you-have-bounds-and-a-feasible-point/33048#33048 .) Also there are neat things like problems seemingly similar which have vastly different complexity (Euler (edge) path is linear time, Hamiltonian (vertex) path is NP-complete).

Knapsack is pretty easy to grasp, especially for anyone who has had to deal with a small suitcase.. a nice example if they know dynamic programming.

Another fun (practically identical) one is Subset-sum, because it also has a nice physical interpretation: imagine the numbers being the distances of equal point-masses on an ideal (massless) ruler, with the fulcrum at the origin. Subset-sum says: does there exist a non-empty subset such that the ruler will remain balanced? (i.e., such that the center of gravity is the support point for the ruler?)

In both cases, it seems intuitive that naive strategies may force resorting to checking all subsets.

If they have more background, it's nice to grow problems by dropping constraints. For example, starting with a max flow problem, turning it into a linear program, and making it an integer program. (A great one of course is MAX-CUT, since to people with more background you can also bring up UGC; I touch some of this in an MO answer https://mathoverflow.net/questions/33036/is-quadratic-programming-still-np-hard-if-you-have-bounds-and-a-feasible-point/33048#33048 .) Also there are neat things like problems seemingly similar which have vastly different complexity (Euler (edge) path is linear time, Hamiltonian (vertex) path is NP-complete).

Post Made Community Wiki
Source Link
matus
matus
  • 2.1k
  • 14
  • 14

Knapsack is pretty easy to grasp, especially for anyone who has had to deal with a small suitcase.. a nice example if they know dynamic programming.

Another fun (practically identical) one is Subset-sum, because it also has a nice physical interpretation: imagine the numbers being the distances of equal point-masses on an ideal (massless) ruler, with the fulcrum at the origin. Subset-sum says: does there exist a non-empty subset such that the ruler will remain balanced? (i.e., such that the center of gravity is the support point for the ruler?)

In both cases, it seems intuitive that naive strategies may force resorting to checking all subsets.

If they have more background, it's nice to grow problems by dropping constraints. For example, starting with a max flow problem, turning it into a linear program, and making it an integer program. (A great one of course is MAX-CUT, since to people with more background you can also bring up UGC; I touch some of this in an MO answer http://mathoverflow.net/questions/33036/is-quadratic-programming-still-np-hard-if-you-have-bounds-and-a-feasible-point/33048#33048 .) Also there are neat things like problems seemingly similar which have vastly different complexity (Euler (edge) path is linear time, Hamiltonian (vertex) path is NP-complete).