Which of the following problems exhibit optimal substructure? (That is, an optimal solution to a problem will contain an optimal solution to subproblems.)

Select all that apply.

1)	The shortest path problem: Finding the shortest path from point A to point B in a graph.

2)	The problem of packing a box full of material to maximize the total value of material in the box.

3)	The longest path problem: Finding the longest path (without any cycles) from point A to point B in a graph.

Which of the following problems have the property that they are composed of overlapping subproblems?

Select all that apply.

1)	Sorting an array.

2)	Searching for an element in an ordered list.