首页 > > 详细

EECS3101 Summer 2022 Assignment 4

 EECS3101 Summer 2022 Assignment 4

Due: Aug 7th 23:59
General Instructions
Please read the following instructions carefully before starting the exercise. They
contain important information about general exercise expectations, exercise submis￾sion instructions, and reminders of course policies.
• Your problem set is graded on both correctness and clarity of communication.
Solutions which are technically correct but poorly written will not receive full
marks. Please read over your solutions carefully before submitting them.
• Each problem set must be completed individually
• Solutions must be typeset electronically, submitted as a PDF with the correct
filename ps4.pdf. Our recommendation goes for using LATEX and we recommend
Overleaf as a tool, but you may feel free to pick your own tool, or generate a
PDF using means such as Microsoft Word or other software.
• Submissions must be made before the due date and time on eclass. Late sub￾missions are not accepted.
1
Problem 1.
(40 Marks) (MST.) Prove that if all edge weights on a connected graph are
unique/distinct, then there exists a unique/distinct minimum spanning tree.
2
Problem 2.
(60 marks) (Kruskal/Dijkstra) Consider a graph, G = (V, E) and two weight
functions w1(e) and w2(e), where w1(e) = (w2(e))2
. You may assume all edge weights
are unique and positive.
(i) (40 Marks) Prove that under both weight functions, Kruskal’s algorithm will
return the same minimum spanning tree.
(ii) (20 Marks) Using a counterexample, disprove the following statement: Under
both weight functions, Dijkstra’s algorithm will return the same shortest path.
 
联系我们 - QQ: 99515681 微信:codinghelp
程序辅导网!