EECS3101 Design and Analysis of Algorithms - Summer 2022 Assignment 4 Connected Graph and Spanning Tree
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 submission 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.
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.
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)) . 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.
