University of Nevada Las Vegas
Howard R. Hughes College of Engineering
Department of Computer Science
My Home Page
Course Page

CSC 477/677 Assignment 7

Due date: Wednesday, October 30, 2013, 2:30 PM.

All assignments must be handwritten (not typed or printed from a computer file) in your own handwriting, on 8.5 by 11 inch paper, or on A4 paper. Write your name on each sheet, and do not fold the pages or crimp the corners. (You may use a paper clip or a staple.)
Turn the pages in to me or to the graduate assistant on or before the due date.

  1. The weighted directed graph shown here or here has negative weights, but no a negative cycle. Change the weights so that the answers to all shortest path problems are the same, but all the weights are non-negative.

  2. Give a dynamic programming solution to the ``box-stacking" problem (Problem 4) in the dynamic programming handout. What is the time complexity of your algorithm, in terms of n, the number of different kinds of boxes?

  3. Work the problem given in this handout.
    Here is the same handout in postscript format.

Back to Course Page