Posted by: Jesse | November 14, 2011

HW7 Grades

The stats for homework 7 are:

Mean: 79
Median: 85
Standard Deviation: 20

Q1 and Q2 were graded by Jiun-Jie and Q3 was graded by Jesse.

The solutions were generally pretty good for Q1 and Q2. There was however a fairly common approach to Q3 that is incorrect. Some of you added the absolute value of the most negative edge to all the edge weights to make them all positive, then applied Dijkstra’s algorithm. This is a clever idea as it maintains the order of all the edge weights, but it does not maintain the order of all path weights. Specifically, it will favor paths that have fewer edges. For example, a path containing 5 edges will increase in weight by the constant times 5, while a path of only 2 edges will increase by the constant times 2. This can change which path is the shortest and there are simple examples where it does.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Categories

%d bloggers like this: