CSC 445 Homework 4 (version 1)
代写算法编程课业 This homework is due Thursday, November 12, at 2:00pm. Please upload a single PDF file containing your submission (ensuring scans of handwritten
This homework is due Thursday, November 12, at 2:00pm. Please upload a single PDF file containing your submission (ensuring scans of handwritten work are legible) on Gradescope by that time.
The questions are drawn from the material in class, and in Chapter 16 of the text, on greedy algorithms.
The homework is worth a total of 100 points. If point breakdowns are not given for each part of a problem, each part has equal weight. 代写算法编程课业
For questions that ask you to design a greedy algorithm, prove that your algorithm is correct using a greedy augmentation lemma of the following form:
Lemma
If a partial solution P is contained in an optimal solution, then the greedy augmentation of P is still contained in an optimal solution.
Prove the lemma using an exchange-style argument, where you transform the optimal solution so it contains the augmentation and then argue that the transformation does not worsen the solution value. Finally, prove correctness of your algorithm in a theorem that makes use of the lemma.
Remember to (a) start each problem on a new page, and (b) put your answers in the correct order. If you can’t solve a problem, state this, and write only what you know to be correct. Neatness and conciseness count.
(1) (Counterexamples to greedy procedures) (30 points) 代写算法编程课业
Prove that the following greedy procedures for the Activity Selection Problem are not correct. Each procedure considers the activities in a particular order, and selects an activity if it is compatible with those already chosen.
(a) The activities are considered in order of increasing duration.
(b) The activities are considered in order of increasing start-time.
(c) The activities are considered in order of increasing number of overlaps with the remaining compatible activities. (This is a dynamically-determined order.)
(Note: To prove an optimization procedure is not correct, it suffices to demonstrate a counterexample: namely, an instance of the problem that has a feasible solution that is better than the one the procedure outputs.)
(2) (Trip refueling) (30 points) 代写算法编程课业
Suppose you want to travel from city A to city B by car, following a fixed route. Your car can travel m miles on a full tank of gas, and you have a map of the n gas stations on the route between A and B that gives the number of miles between each station.
Design a greedy algorithm to find a way to get from A to B without running out of gas that minimizes the total number of refueling stops, in O(n) time. Prove that your algorithm finds an optimal sequence of stops.
(a) (40 points)
Design a greedy algorithm that, given the task durations t1, t2, . . ., tn, finds a schedule that minimizes the average completion-time. You may assume that once a task is started, it is run to completion. Your algorithm should take O(n log n) time.
Analyze the running time of your algorithm, and prove that it is correct using a lemma of the required form.
(b) (bonus) (20 points)
Suppose with each task we also have a release time ri , and that a task may not be started before its release time. Furthermore, tasks may be preempted, in that a scheduled task can be interrupted and later resumed, and this can happen repeatedly.
Design an algorithm that finds a schedule that minimizes the average completiontime in this new situation. Analyze its running time and prove that it is correct.
Note that Problem (3)(b) is a bonus question, and is not required.
更多代写：PYTHON作业代做 留学代考 英国Statistics统计学 Reflective Essay写作 Report代写论文范文 斯坦福本科申请代写
