[Cs5500] P3- Part 2

[Karl Lieberherr]

Hi Tuba and Ashish:

good idea to compare with MMG. Does this correspondence solve the puzzle?

MMG
Instance: double x
Solution: double y
InstanceSet: belongsTo [0,1]
quality: x*y+(1-x)*(1-y^2)

BFS
Instance: triple (Graph G, Node s, Node t)
Solution: Node v
InstanceSet: belongsTo if in G, dist(s,t)>|V|/2
quality: if v cuts all s-t paths then 1 else 0

ForAllExists seems the perfect fit?

-- Karl


On Sun, Oct 2, 2011 at 3:18 PM,  <tkoc at ccs.neu.edu> wrote:
>
>  Hi,
>
>  Regarding part 2 in project 3, in class we mentioned that G,s and t are instance and v is solution and claim is a boolean (true or false).
>  In this case, how can we make a claim without knowing the graph because graph is given with instance. I think the graph should be given first like the equation given in mmg playground.
>  On the other hand, graph can change. There isn`t a specific graph for this playground like we had in mmg.
>  Can someone clear this up for me?
>
>  Thanks,
>
>  Tuba
>