The x_y notation means that y is the index of x. Sum(S) denotes the sum of the elements in S.

1.
a) A good witness will be a subset whose sum is t. We can encode it by giving the indeces of the elements which are in the subset, in a form a_1,a_2,...,a_k.
b) If the answer is True then there exists such a subset which means that there exists a good witness. 
On the other hand, if the answer is False, then there can not exist such an index set.
c) Algorithm: Input: S,t, a_1,a_2,...,a_k.
   1) check that ai is in {1,2,...,n} for all i  [it will give k steps]
   2) Check that ai is different from aj for all i,j pairs [it will give at most k^2 steps]
   3) Check thet the sum of x_(a_1) + x_(a_2) + ... + x_(a_k) is equal to t. [k steps]
d)This way the algorithm is polynomial (3k^2 is an upper bound for the running time)

2.
Partition (input: S) < Subsetsum (input: S, t)
The reduction:
f: S ---> S, Sum(S)/2

If the answer is true for the partition problem => there exists a partition of S into disjoint sets S_1 and S_2 where Sum(S_1)=Sum(S_2)=> Sum(S_1)=Sum(S)/2 => there exists a subset of S whose sum is equal to Sum(S)/2 => The answer is true for the subset sum problem (on the input S, Sum(S)/2)

If the answer is true for the subset sum problem (on the input S, Sum(S)/2) => there exists a subset S_1 of S so that Sum(S_1)=Sum(S)/2 => Let S_2 denote S-S_1 (the set of numbers in S which is not in S_1). Sum(S_2) must be equal to Sum(S)/2 => Sum(S_1)=Sum(S_2) => the answer is true for the partition problem (on the input S)

3.
From E
                E             level 0

      /  /  |  |  |  \  \
      A  B  C  D  F  H  I     level 1
                 /\
                 G J          level 2

From J
           J        level 0
        /  |  \
       F   G   I    level 1
   / / | \
   B C E H          level 2    
 / |
 A D                level 3


4.
   b--a--d--f
   |  |
   e  c

Decisions: ab-OK, ad-OK, df-OK, ac-OK, af-NO, bf-NO, cf-NO, bc-NO, be-OK
We have 5 edges in a graph on 6 nodes so we can stop. We have a spanning tree of value 13. 

5. 
  s a b c d e f t
s 0 7 2 0 8 0 0 0
a 0 0 4 0 0 0 5 0
b 0 0 0 4 0 0 0 0
c 0 0 0 0 0 0 0 6
d 0 0 0 1 0 5 0 0
e 0 0 0 0 0 0 4 3
f 0 0 0 0 0 0 0 8
t 0 0 0 0 0 0 0 0

I will write down the table again ater each step.
Path 1.: SABCT, 4
  s a b c d e f t
s 0 3 2 0 8 0 0 0
a 4 0 0 0 0 0 5 0
b 0 4 0 0 0 0 0 0
c 0 0 4 0 0 0 0 2
d 0 0 0 1 0 5 0 0
e 0 0 0 0 0 0 4 3
f 0 0 0 0 0 0 0 8
t 0 0 0 4 0 0 0 0

Path 2.: SAFT, 3
  s a b c d e f t
s 0 0 2 0 8 0 0 0
a 7 0 0 0 0 0 2 0
b 0 4 0 0 0 0 0 0
c 0 0 4 0 0 0 0 2
d 0 0 0 1 0 5 0 0
e 0 0 0 0 0 0 4 3
f 0 3 0 0 0 0 0 5
t 0 0 0 4 0 0 3 0

Path 3.: SDET, 3
  s a b c d e f t
s 0 0 2 0 5 0 0 0
a 7 0 0 0 0 0 2 0
b 0 4 0 0 0 0 0 0
c 0 0 4 0 0 0 0 2
d 3 0 0 1 0 2 0 0
e 0 0 0 0 3 0 4 0
f 0 3 0 0 0 0 0 5
t 0 0 0 4 0 3 3 0

Path 4.: SDEFT, 2
  s a b c d e f t
s 0 0 2 0 3 0 0 0
a 7 0 0 0 0 0 2 0
b 0 4 0 0 0 0 0 0
c 0 0 4 0 0 0 0 2
d 5 0 0 1 0 0 0 0
e 0 0 0 0 5 0 2 0
f 0 3 0 0 0 2 0 3
t 0 0 0 4 0 3 5 0

Path 5.: SBAFT, 2
  s a b c d e f t
s 0 0 0 0 3 0 0 0
a 7 0 2 0 0 0 0 0
b 2 2 0 0 0 0 0 0
c 0 0 4 0 0 0 0 2
d 5 0 0 1 0 0 0 0
e 0 0 0 0 5 0 2 0
f 0 5 0 0 0 2 0 1
t 0 0 0 4 0 3 7 0

Path 6.: SDCT, 1
  s a b c d e f t
s 0 0 0 0 2 0 0 0
a 7 0 2 0 0 0 0 0
b 2 2 0 0 0 0 0 0
c 0 0 4 0 1 0 0 1
d 6 0 0 0 0 0 0 0
e 0 0 0 0 5 0 2 0
f 0 5 0 0 0 2 0 1
t 0 0 0 5 0 3 7 0

Last BFS: s-d ||
This way the cut is s,d||a,b,c,e,f,t
The flow value is 4+3+3+2+2+1=15
The cut value is 7(sa)+2(sb)+1(dc)+5(de)=15
The two value is equal, this means that we reached the maximum flow and the minimum cut.

6. The hungarian method can be used to solve the maximum assignment problem. The input is a G graph with weighted edges (G(V,E) and weight function w(e) for all e in E). The output of the algorithm is a maximum assignment M: 
A matching is a set of edges which have no common node.
M is maximum assignment if it is a matching, and for all machings M' the sum of the weights of the edges in M is greater than or equal to the sum of the weights of the edges in M'.