Part I
1.
(a) suppose A = [1, 10, 3 …..3, 3] B = [2, 3, 3,…..3, 3]
C = [3, 3, 3,…..3, 3] P = 1000
In week 0, we will choose A, in week b
we still choose A, because choose B, C will plus P which is too high, after wards, the cost all same for A,B,C, we still choose A.
So the result of this greedy algorithm is we choose
A for all 52 weeks, but the obvious optimal solution is that we should choose B for all 52 weeks.
(b)
function p1(A, B, C, P)
# copy A,B,C to cost array create 2d array: cost[3][52] cost[0] = A
cost[1] = B
cost[2] = C
# op[i][j] will store the optimal cost
# of the first j+1 weeks when we select company i # for week j
create 2d array: op[3][52]
# compute week 0 for i in 0…3
op[i][0] = cost[i]
# compute week from 1 to 51 for j in 1…52
for i in 0…3
op[i][j] = inf
for j in 0…3
t = op[i-1][j]
if j != i:
t += P
if t < op[i][j]: op[i][j] = t
bestCost = min(op[0][51], op[1][51], op[2][51])
if bestCost == op[0][51] company = 0
elif bestCost == op[1][51] company = 1
else:
company = 2
create 1d array: schedule[52]
# construct the schedule week = 51
schedule[week] = company
while week >0
for j in 0…3
if j == company && op[week][company] == op[week-1][j]: break
if j != company && op[week][company] == op[week-1][j]+P: company = j
break week -= 1
schedule[week] = company
return schedule, bestCost
(c)
the generalization of above algorithm is easy, just replace 3 with W.
The op array will be W x 52, and when compute each element of it, we
select the min value of W numbers, so the worst running time of compute the optimal cost array is: O(W*52*W), which is O(W^2). The time to construct the schedule is O(52*W), so the overral worst running time is O(W^2).
2.
(a)
function p2(s)
n = len(s)
# op[j] will stores the best quality # for prefix of s that has length j
create array: op[n+1] op[0] = 0
for i in 1..n
op[i] = 0
for j in 0..i
word = s[j+1:i]
if wordQuality(word) + op[j] > op[i]
op[i] = wordQuality(word) + op[j]
best = op[n] create a list: res i=n
# construct the words list while i > 0
for j in 0..i
word = s[j+1:i]
if wordQuality(word) + op[j] == op[i] res.add(word)
i=j
return res, best
(b)
let op(i) represent the the best quality for prefix of s that has length i
op(0) = 0
op(i) = max(op(j) + wordQuality(s[j+1:i])) for j in 1..i
Assume last word of the optional segmentation is w, then if we remove w, the previous segmentation must be optimal for previous string, otherwise we can get better segmentation for the whole string. So we can try all different possible segmentation for the last word
and choose the best.
(c)
The outer loop is 1..n, the innter loop is 0..i, so the worst running time is O(n^2).
3.
a) The graph contains source s and sink t, every patient as vertex and every hospital as vertex. Add edge from s to every patient with capacity 1, add edge from every hospital to t with capacity hi(the maximum number it can take in). If patient u can go to hospital v, then add edge from u to v with capacity 1.
The max flow of this graph can be interpreted as follows:
If the flow from patient u to hospital v is 1, then we send patient u to hospital v. If the max flow of this graph is N, then we can satisfy all the constraints. otherwise, it is impossible to satisfy all the constraints.
b)
The maximum number of edges is N + N*H + H. Ford-Fulkerson: O(E*f) = O((N + N*H + H)*N) = O(N^2*H)
Push-Relabel: O(V^2*E) = O((N+H+2)^2*(N + N*H + H)) = O(N^3*H + N^2*H^2 + N*H^3) So the Ford-Fulkerson’s running time is most reasonable.
4.
First compute the expected number of times of each soldier.
If solider s appears in a list of length n, then the expected
number in this day is 1/n. Because linearity of expectation, add the expectation of each day is the final expectation.
Then construct the graph. The graph contains source s and sink t,
every day as vertex and every soldier as vertex.
Add edge from s to each day with capacity 1,
add edge from each soldier to t with capacity of the ceiling of expectation,
If the list of day d contains solder s, then add edge from d to s with capacity 1.
Now we can use Ford-Fulkerson algorithm to compute the max flow of this graph, if the flow from day i to soldier s is 1, then in day i, we choose soldier s to
carry the pack.
Part II 1.
Worst case is when we push an element bigger than all the elements in the list. We delete the N elements and then push the new element, so the time is ¦¨(N + 1), which is ¦¨(N).
Define the potential function P to be the number of elements in the list.
Note that P(0) = 0, because at start list is empty. P(i) >= P(0), because it is nonnegative number.Suppose the pushed number is bigger than k elements in the list.
amortisedCost=cost+P(i)-P(i-1)=(k+1) +(N-k+1)-(N)=2 whichisO(1). so the amortized cost is O(1).
2
a)
What happened during the spikes is that the capacity of the list is full, so it will allocate bigger memory, and copy the elements to the new allocated memory and thus spend much more time.
The x coordinate of next spike is about 1.5 times of the x coordinate of previous spike. The spent time of later spikes is bigger than previous spikes.
b)
Yes, the empirical roughly result match what theory would predict. The average time decrease in the start and then it stays about the same. The plot is high in the start, because at the start the reallocating memory happens more than later, as the call increase, the reallocating memory happens less, so the average time decrease in the start and then stays about the same.