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

CSC 477/677 Assignment 3

Due date: Thursday, March 8, 2012, 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 the teaching assistant on or before the due date (except for those problems you are not supposed to turn in).
  1. Use the Bellman-Ford algorithm to solve the single source shortest path problem for this graph of ten nodes.
    • The first line of the file contains n, the number of vertices of G. The names of the vertices are the integers from 1 to n.
      (Note that n = 10 in this example.)
    • Each remaining line of the graph is a list of integers separated by spaces, and represents the list of outneighbors of one vertex.
    • The first number in the line is the name of the vertex.
    • After that, there is a sequence of pairs, consisting of a vertex name and a weight.
    • For example, the third line of the file,
      8 5 3 7 3 4 -2
      indicates that there is an edge from 8 to 5 of weight 3, an edge from 8 to 7 of weight 3, an edge from 8 to 4 of weight -2, and no other edges from 8.
    • The source will be vertex 1.
  2. Walk through Dijkstra's algorithm to solve the single source shortest problem for the weighted directed graph given. The source is s.
    The graph in postscript format.
    The graph in portable document (pdf) format.
    You don't have to use up a ream of paper describing each iteration of the inner loop. Instead, you only need to write something when some value of the array d changes. I was able to do it on a single sheet of paper in 16 minutes.
  3. We say that a sequence of integers is nice if it is increasing and the difference between consecutive terms is either 5 or 6. For example, the sequence 0,5,11,17,22,27,33 is nice.
    Use dynamic programming to compute the number of nice sequences that start with 0 and end with 50.
    Hint: Don't attempt to solve this problem by listing all the sequences. Yes, it can be done. But that is a very inefficient way to do it, and it will be marked wrong, since that is not the method you are supposed to use.

Back to Course Page