Instructors can find out how well students understand how to apply various algorithmic techniques to a computationally hard problem that appears to be just a variation of the shortest-path problem.
Read the following scenario and answer the question. Be certain to back up your decisions.
A shipping company has a variety of warehouses that it ships to. Since they have a lot of trucks moving about, they would like to avoid sending trucks on the longest possible routes from point A to point B. You are given a graph with edge weights corresponding to the distance between the warehouses (nodes).
How would you determine what the longest path is from warehouse A to warehouse B?
This problem is actually NP-Hard despite its overwhelming similarity to the shortest-path problem. This problem is good for introducing students to the hard to solve problems that abound in computer science.
Read through the applications and sort or mark them as "Good," "Acceptable," "Marginal," or "Wrong." Read through the piles again to make sure that you have not accidently misclassified a response. You might also want to sort the responses by the type of algorithms are used.
Choose three or four of the best examples from the "Good" pile. Emphasize understandability, but try to have a diversity of example domains. Also consider a few acceptable and marginal responses that highlight points you wish to discuss.
If you use an application in class as a bad or poor example, change the application just enough to disguise the example from the original authors.