Assignment 8

The Assignment

Submission

• Turn in a hard copy in class.

Recommendations/Notes

Note that the questions are from the Exercises (not the Self-Test Exercises) section at the end of the chapter. You may want to do some of the Self-Test questions first and check your answers in the back of the book to make sure you understand the material.

In order to get extra credit for early submission on this one, you will need to get your homework to either Nickles or me before Tuesday. Turning it in Monday will get you 5% extra. You will probably need to turn it in by Friday to get the full 10%.

Remember, there will be no late submissions accepted for this assignment. You do not have the usual "2 days late/5 days late" options.

Hand-writing your answers is acceptable, as long as it is neat and readable.

For Question 20, have a look at Appendix D in the book if you're rusty on proof by induction. If you're still lost, just do your best. Try to state or explain as precisely as possible why the first vertex added to vertexSet will always be the closest vertex to the origin (shortest path in the graph from the origin). And then explain why each successively added vertex will always be the next shortest path from the origin.

Grading:

Out of 10 points:

1 point for each question.