Part I
1)
Use greedy strategy with shortest job first. Sort the jobs with non-decreasing order in time. This can be done by merge sort algorithm in O(nlog(n)).
Proof.
Suppose ord is the ordering array.
Average = (t(ord(1)) + (t(ord(1)+t(ord(2)) + (t(ord(1))+t(ord(2))+t(ord(3)) + … + (t(ord(1)+t(ord(2))+…+t(ord(n)))/n.
Note that The t(ord(1)) appears in the most times, so t(ord(1)) should be the smallest.
Suppose the optimal solution is not non-decreasing order in time.
So there exists i < j with t(ord(i)) > t(ord(j)). If we exchange position of jobs in position i and j, because t(ord(i)) added more times than t(ord(j)), then the resulting average time is smaller which is a contradiction.
2) Use network flow.
Algorithm
Graph construction:
Every person i as vertex pi. Team A and B as vertex s and t which is source vertex and sink vertex respectively.
Add edge from s to each with c pi apacity uiA
Add edge from each pi to t with capacity uiB.
For every pair of people i and j, add edge from pi to pj and edge
from pj to pi both with capacity uij .
Result interpretation.
Use a maximum flow algorithm to compute the minimum cut, For each person i, if pi in the same set with s, then assign pi to team A, otherwise assign pi to team B.
The capacity of the minimum cut is the sum of all the unhappiness score.
Proof
The cut in the graph is a one to one mapping to the way to divide the people. Suppose the cut is (S,T), s in S and t in T. We assign people in S to team A and people in T to team B.
Next we prove that the capacity of the cut is equal to the sum of the unhappiness score.
If person i is in team A, we need to add uiB to unhappy score, we also need to capacity of edge (Pi, B) to the capacity of Min-cut.
If person i and j are in different team A and B, we need to add uij to to unhappy score, we also need to capacity of edge (Pi, Pj) to the capacity of Min-cut.
We see that the capacity of the cut is just the unhappiness score of corresponding division.
So the division of team corresponding to the minimum cut is the one that have minimum unhappy score.
Run Time
We can use relabel-to-front algorithm to compute the minimum cut. It is O(V3). Because we have N+2 vertices,
so the run time will be O(N3)
3)
Use dynamic programming, below is the pseudocode. Input: l[1…n] length of the n words
Output: bestMessyScore the minimum messiness score
segPoints list of position to segment the words to lines
create lengthSum[0…n] for i in 1…n
lengthSum[i] = l[i] + lengthSum[i-1]
create op[0…n] // op[i] will store minimum messiness score for {w1 …. wi} op[0] = 0
for i in 1…n
op[i] = inf // infinity for j in i-1…1
s = op[j-1]
// line length
len = i – j + (lengthSum[i] – lengthSum[j-1]) if len > W // line is too long
break if i != n
s += (W – len)^3 // not last line, add messy score if s < op[i]
op[i] = s // update the best
// now op[n] is the minimum messiness score
bestMessyScore = op[n]
// construct the segmentation
segPoints = list() i= n
while i > 0
for j in i-1…1
len = i – j + (lengthSum[i] – lengthSum[j-1])
if (i != n and op[i] == op[j-1] + (W – len)^3) or (i == n and op[i] == op[j-1])
segPoints.add(j) i = j-1
break
// now segPoints stores where we segment the words to lines
The dynamic programming uses following recursive relation
Op(i) = Min(op(j-1) + messscore(i,j)) for j in 1…i-1
Suppose the optional segmentation for {w1…wi}, and the last line is wj…wi
Then the segmentaion of w1…wj-1 must also be optimal segmentation for {w1…wj-1}.
Otherwise we can past a better segmentation and get smaller messiness score.
The runtime is O(n^2).
Part II
1)
7 6
5
4 3
246
1357
2 1
2)
3) 1
24
6 7
5
3
4) H.min
1234567
Part III
1)
It is not a reasonable argument. Because NP doesn’t indicate a problem is hard to solve. In fact, every problem that can be solved in polynomial time is also in NP. Only a subset of NP known as NP-complete currently have no known efficient algorithm to solve them in polynomial time. NP-complete may be a reasonable argument, but NP is not.
2) The reduction direction is wrong. The proof(b) is proving that 2-SAT reducible to 3-SAT. But We should prove 3-SAT is polynomial-time reducible to 2-SAT, not 2-SAT to 3-SAT. In fact, every language in NP can be polynomial-time reducible to 3-SAT.
3)
First this language is NP, because we can check a list of vertices whether a simple path of length at least k in polynomial time.
Second we can prove NP-complete Hamiltonian
Cycle is polynomial-time reducible to this language. Given a directed graph of n vertices, the graph has a Hamiltonian Cycle if and only if it has a simple cycle of at least n vertices.