CMPSC 465
Data Structures & Algorithms
Spring 2021
Practice Midterm 2
Complete by: April 6th
数据结构和算法代考 A courier company needs to load boxes b1, . . . , bn into as few trucks as possible. Boxes bi, . . . , bn arrive in order.
Instructions as they will appear for real midterm: 数据结构和算法代考
- Please log into the regular lecture Zoom meeting.
- Ifyou havea 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, you must put your pens You have until 2:30 to upload your solutions to Gradescope.
- 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, b j with i < j, it’s not allowed to load bi into the p-th track wile b j 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., usesas 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, . . . , b j into first k trucks, and other solution loads b1, . . . , b j 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 the weight of an edge e = (u, v) just changed from 10 to 20, and e was in T . How do you find a new MST 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.
