Homework 5 Clarifications

Last updated Sat 2-16-2013

Problem 1

If you want, you can assume that you are talking about a directed graph. So most nodes only have a few edges starting at that node (low out-degree) but a few nodes have hundreds of thousands of edges starting at that node (high out-degree). (If you already answered the problem assuming it was an undirected graph that is also fine.)

Problem 2

We expect you to use the "optimized" topo sort algorithm that uses a queue for the vertices of indegree zero shown on Slide 25 and 26 here. Show the "in-degree" array as shown on slide 20, showing how the indegree of the vertices changes with each step. Also show the contents of the queue at each step.

Problem 4

• Part a - You must show the order that vertices were added to the known cloud - although you can do this in a simple list. Although the final table is all that is required, for potential partial credit I would recommend showing how your table changes over time by leaving lots of space and crossing things out as they change. Also be sure that you show the value of the path variable.
• Part b - Assume no negative weight edges or neg weight cycles.
• Part d - In addition to your example, don't forget to give a general explanation as to why this technique does not work.