SB CSE 675 Fall 2000 |
Program Transformation and Program Analysis
Annie Liu Solution 9 |
Handout S9
Dec. 6, 2000 |
Problem 1.
f(x) = if #{b:[a,b] in f|a=x}=1 then arb{b:[a,b] in f|a=x} else om endif = if exists [a,b] in f| a=x and not exists [a,c] in f| b!=c then b else om endif f{x} = {y: [u,y] in f| u = x} not = {y: [x,y] in f} = {y in range f| [x,y] in f} f[s] = + / {f{x}: x in s} where one could copy f{x} above in here = {y: [x,y] in f| x in s} = {y: x in s, y in f{x}}
Problem 2.
program cycle; read(e); s := domain e + range e; -- only domain e is necessary while exists x in s| e{x} * s = {} loop s less := x; -- repeatedly remove elem whose successors are not in s end loop; print(s); -- graph e contains a cycle iff s /= {} end;
Problem 3. change e[s]-s to w + e[s] - s
Bonus Problem.
4.1 */{s in pow({x}+range e)|x in s and +/{+/neighbors(x,e)|x in s} subset s} 4.2 isconn(s) = forall x in nodes(s)| reach(x) = s 4.3 ispath(s) = isconn(s) and (#leaves(s)=2 and forall x in (nodes(s) - leaves(s))| #neighbors(x,s) = 2) 4.4 paths(x) = {s in pow(e)| ispath(s) and x in leaves(s)} 4. maxpaths(x) = {s in paths(x)| #s = max/{#q: q in paths(x)}} 5. furthest(x) = {y: s in maxpaths(x), y in leaves(s)| y /= x} 6. middle(s) = {x in nodes(s)| #(arb maxpaths(x)) = #s/2 + #s mod 2} tree center: middle(arb maxpaths(arb furthest(arb nodes(e))) this is in very-high-level SETL.