« VisualStuSyllabus for all sect | Main | One very Syllabus for all sect »

January 26, 2006

Homework Syllabus for all sect

The sixth homework assignment consists of the following problems on Minimal spanning trees and shortest paths:

Previous questions cancelled If you did them, turn them in for extra credit.

Question 1 Simulate each step of Dijkstra's algorithm, and turn in a table similar to the table in the middle of page 199, on the following directed graph consisting of 5 vertices labeled 1,2,3,4,5 and the following 5 edges

  • 1 to 2 is connected by an edge with cost 6
  • 1 to 3 is connected by an edge with cost 4
  • 2 to 4 is connected by an edge with cost 3
  • 1 to 4 is connected by an edge with cost 9
  • 1 to 5 is connected by an edge with cost 20
  • 4 to 5 is connected by an edge with cost 6

    Question 2 Implementing Dijkstra's algorithm requires finding the smallest element in a set (line 8 of pseudocode on page 199) and removing an element from a set (line 9). Discuss the datastructures and algorithms that you might use to implement these operations in the intelligent scissors project. In your discussion, address the efficiency implications of your decisions.


    Read "Everest: The West Ridge" by Hornbein (optional reading)

    Posted by ringger at January 26, 2006 02:09 PM

    Comments

    This site has great graphical and interactive demonstrations of Kruskal's, Prim's, and Dijkstra's algorithms.
    http://students.ceid.upatras.gr/~papagel/

    Posted by: WhiteThunder [TypeKey Profile Page] at January 26, 2006 10:14 AM

    I have deleted the questions out of the book on this homework. the homework now consists of just the last 2.

    Posted by: Mike Jones [TypeKey Profile Page] at January 26, 2006 02:12 PM

    Post a comment

    Thanks for signing in, . Now you can comment. (sign out)

    (If you haven't left a comment here before, you may need to be approved by the site owner before your comment will appear. Until then, it won't appear on the entry. Thanks for waiting.)


    Remember me?