当前位置:天才代写 > 算法代写 > 数据结构和算法代考 Midterm代写

数据结构和算法代考 Midterm代写

2021-11-24 10:26 星期三 所属: 算法代写 浏览:30

数据结构和算法代考

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.

数据结构和算法代考
数据结构和算法代考

 

更多代写:计算机网课作业代写  环境学代考  会计essay代写   化学专业essay代写  化学工程论文代写  论文代写机构

合作平台:essay代写 论文代写 写手招聘 英国留学生代写

 

天才代写-代写联系方式