CMPSC 465 Data Structures & Algorithms
Spring 2021 Paul Medvedev and Chunhao Wang Midterm 2
Complete by: April 6th, 2:20 pm
Instructions:
• 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.
• At 2:20pm, you must put your pens down. 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 on Gradescope.
1. (10 pts.) Fully loading a knapsack
You have a backpack of capacity W ≥ 0, which is an integer. There are k categories of items. Each item in the i-th category has weight wi, which is also an integer. Assume there are unlimited items in each category. You need to put items in the backpack so that it is fully loaded, i.e., the total weight is exactly W . The goal is to use as few items as possible.
(a) Suppose there are 4 categories whose corresponding weights are w1 = 25, w2 = 10, w3 = 5, w4 = 1. Give a greedy algorithm to fully load the backpack with as few items as possible, and what is the runningtimeintermsofW? (Eitheradescriptionofthealgorithmorpseudocodewillbefine. You don’t need to prove the correctness.) Note that it’s always possible to fully load the backpack because there is a category of weight 1 and W is an integer.
(b) Greedy algorithm won’t always work. Give a set of categories with corresponding weights where the greedy algorithm fails. Your answer should contain the value of W, and a set of weights, and you should explain what the greedy solution is and what a better solution is. Note that your answer should have a category for weight 1, so that there is always a solution for every integer W .
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)justchangedfrom10to5,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, Midterm 2 1