这是美国的一个算法代写案例，主要与伪代码相关
Homework Instructions
1. For all algorithms that you are asked to \give” or \design”, you should
• Describe your algorithm clearly in English.
• Give pseudocode.
• Argue correctness; you may provide a formal proof or a convincing argument.
• Provide, with an explanation, the best (smallest) upper bound that you can for the running time.
All bounds should be worst-case bounds, unless explicitly stated otherwise.
You are also encouraged to analyze the space required by your algorithm. We will not remove marks
if you don’t, unless the problem explicitly asks you to analyze space complexity.
2. If you give a Dynamic Programming algorithm, the above requirements are modified as
follows:
(a) Clearly define the subproblems in English.
(b) Explain the recurrence in English. (This counts as a proof of correctness; feel free to give an
inductive proof of correctness too for practice but points will not be deducted if you don’t.) Then
give the recurrence in symbols.
(c) State boundary conditions.
(d) Analyze time.
(e) Analyze space.
(f) If you’re filling in a matrix, explain the order to fill in subproblems in English.
(g) Give pseudocode.
Homework Problems
1. (20 points) Design an efficient algorithm for the following task.
On input an undirected weighted graph G = (V; E; w) with positive edge weights, and a
specific vertex s 2 V , return a Boolean array unique[] of size n = jV j such that unique[i] = 1
if and only if there is a unique shortest s − i path.
2. (20 points) Suppose we introduce a further optimization criterion in our single-origin shortest
paths problem: We are now looking for the shortest s − i path with the fewest edges. We
define
minedges[i] = minimum number of edges in a shortest path from s to i
Give an efficient algorithm that, on input a directed weighted graph G = (V; E; w) with
positive edge weights, and an origin node s 2 V , computes minedges[i] for all i 2 V .
3. (30 points) You’re helping to organize a mini-triathlon event: each of n contestants must first
swim 20 laps of a pool, then bike 10 miles, then run 3 miles. The contestants must use the
pool one at a time|that is, as soon as the first person is out of the pool, a second contestant
can begin swimming the 20 laps|but many contestants may bike and run simultaneously.
For each contestant i, you know the expected swimming time si, expected biking time bi and
expected running time ri. Assume that all contestants need exactly their expected times
to finish the three parts of the triathlon. You are tasked with sequencing the starts of the
contestants so that the triathlon event ends as soon as possible.
More formally, a schedule for the triathlon is an order in which to sequence the starts of the
contestants. The completion time of a schedule is the earliest time at which all contestants
will be finished. Given n triples (si; bi; ri), design an efficient algorithm that produces the
schedule with the minimum completion time.