CSE 101 Homework 1 Due Day 8 When presenting an algorithm make sure you have A clear pseudo code description of the algorithm A proof that it is correct loop invariants may help An analysis of its runtime stating the runtime isn t sufficient provide a proof or justification For full credit you need all three pieces Exercises Kleinberg refers to the class textbook Algorithm Design by Kleinberg and Tardos 1 For the following graph use Dykstra s algorithm to determine the distances from node 1 to each other node Show the distances in the order that Dykstra s algorithm determines them 10 pts 8 3 15 1 10 2 3 5 2 6 14 4 6 7 7 12 4 11 9 1 8 5 2 For the previous graph provide the edges added to the MST in order using Prim s algorithm starting with node 1 and Kruskal s algorithm 10 pts 3 Kleinberg Chapter 4 Exercise 2 10 pts 4 Kleinberg Chapter 4 Exercise 3 10 pts 5 Kleinberg Chapter 4 Exercise 12 20 pts 6 Kleinberg Chapter 4 Exercise 19 20 pts 7 Kleinberg Chapter 4 Exercise 21 20 pts 8 Kleinberg Chapter 4 Exercise 29 Extra credit 20 points 2
View Full Document
Unlocking...