CMPSC 465 Data Structures & Algorithms
Spring 2021 Paul Medvedev and Chunhao Wang Practice Midterm 2
Complete by: April 6th
Instructions as they will appear for real midterm:
• Please log into the regular lecture Zoom meeting.
• If you have a question during the exam, you may ask the Instructor privately via Zoom chat.
• Instructor will announce any major corrections vocally over Zoom.
• All clarifications and corrections will be placed in https://docs.google.com/document/ d/1q1tWHzuu0yj5c5uhz5sBHzRje7wrfKUUmxUVdqK-aEQ/edit?usp=sharing.
• Write your solutions by hand. Typed solutions will not be accepted. You may handwrite on a tablet as well.
• At2:20pm,youmustputyourpensdown.Youhaveuntil2:30touploadyoursolutionstoGradescope.
• You must use a scanning app and not just take pictures.
• You must use the template solution sheet provided before the exam on Canvas.
1. (10 pts.) Greedy Package Loading.
A courier company needs to load boxes b1,…,bn into as few trucks as possible. Boxes bi,…,bn arrive in order. Each box bi has weight wi and the each truck has a capacity W . There is also an ordering for the trucks. The constraint is that an earlier-arrived box cannot be loaded into a later truck, i.e., for bi,bj with i < j, it’s not allowed to load bi into the p-th track wile bj is loaded into the q-th truck where p > q (but they can be loaded into the same truck). Consider the simple greedy loading: load the boxes in the order and whenever the next box does not fit, load it to the next truck. Is this greedy algorithm optimal (i.e., uses as few trucks as possible)? If so, prove it. If not, give a set of boxes with specified weight that are packed in a non-optimal way.
(Hint: if you think this greedy approach is optimal, it suffices to show the following. If the greedy algorithm loads boxes b1,…,bj into first k trucks, and other solution loads b1,…,bj into the first k trucks, then i ≤ j. This implies the optimality of the greedy algorithm by setting k to be the number of trucks used by the greedy algorithm.)
2. (10 pts.) Revising MST.
Let G = (V, E ) be an undirected and connected graph and T be a minimum spanning tree of G. Now suppose theweightofanedgee=(u,v)justchangedfrom10to20,andewasinT. HowdoyoufindanewMST without running either Kruskal’s or Prim’s algorithm again? What is the running time of your method? If there’s nothing to do, explain the reason.
CMPSC 465, Spring 2021, Practice Midterm 2 1