SB CSE 675
Fall 2000
Program Transformation and Program Analysis
Annie Liu
Exercises 9
Handout E9
Nov. 28, 2000
Due Dec. 6

Programming with Sets and Maps. (Due at class time on Wednesday of next week.)

Note: A good thing about a SETL program is that, with a few lines, it runs, so you can test it easily.
(hints to homework and guide to SETL2 installation)

Problem 1. Maps.

Write the following operations on maps, as defined in class, using operations on sets and tuples, and using set formers, as provided in SETL.

    1. f(x)  2. f{x}  3. f[s]
Write at least two different versions for 3. This, among other reasons, helps justify introducing f[s].

Problem 2. Topological sort and cycle detection

Recall from class that the topological sort problem can be solved using the program below, which also detects whether cycles exist; and the set s at the end is actually the largest subset s of vertices each containing a predecessor belonging to s.

    program toposort ;
      read(e) ; 	-- e is predecessor relation for partial order

      t := [] ;	        -- t stores a linear order consistent with e
      s := domain e + range e ;	
      while exists x in s| e{x}*s = {} loop
        t with :=  x ;
        s less :=  x ;	-- repeatedly add a min elem to t & delete from s 
      end loop ;

      if s = {} then print(t) ; 
      else print("cycle detected in input graph") ;
      end if ;
    end;
Write a program in high-level SETL to compute the largest subset s of vertices each containing a successor belonging to s; suppose that e is a successor relation.

Problem 3. Graph reachability, with simplified initialization

Recall from class that the problem of graph reachability is to find all nodes reachable along paths in e from set w, and it can be written as the following SETL program except with e[s] replaced by appropriate code you defined in Problem 1.

    program reach ;
      read(e,w) ;

      s := w; 
      while exists x in e[s] - s loop s 
        with := x ;
      end loop ;

      print(s) ;
    end ;
We want to write a slightly different program for reach by changing initialization "s := w;" to the simpler statement "s :={};". How to change something in the while loop so that your program computes the same thing as program reach above? Note that efficient lower-level implementations derived from these two versions compute in the same way, but the modified version has much simpler initialization.

Bonus Problem (100%): Tree center problem solved differently--a lot more exercises

Recall from class that the topological sort problem can be solved using the program below:

    program treecenter ;
      read(e) ; 	-- tree e is a symmetric edge relation

      s := domain e;	-- S is the set of vertices
      while #s > 2 loop -- repeatedly remove leaves until 1 or 2 vertices remain
        s -:= { x in s| #(e{x}*s) = 1 } ;
      end loop ;

      print (s) ;	-- final value of s is the center
    end ;
This problem can be solved differently (though not as neat), as follows (proof omitted): Let x be any leaf (a node with only one adjacent node), let y be any leaf furthest away from x (in terms of number of edges), and let z be any leaf furthest away from y. The path P connecting z to y is a longest path in tree. If P has an odd num of nodes, then the center is middle node, o.w., the middle two.

Now, for a lot more exercises, let's program this. Suppose we've got the following basic definitions.

1. nodes of any edge subset s: nodes(s) = +/s
2. edges in s incident to node x: neighbors(x,s) = {y in s |x in y}
3. leaves of s: leaves(s) = {x in nodes(s) | #neighbors(x,s) = 1}
We may compute the following three items, 4. maxpath(x): longest paths in e from a node x;
5. furthest(x): nodes furthest from a given node x (hint: at the other end of a longest path)
6. middle(s): middle of a longest path s (hint: half way from an end)
and, to compute item 4, a few things may help. 4.1. reach(x) nodes reachable along paths in e from node x (similar to the one-line reach in class)
4.2. isconn(s): whether an edge set s is connected (if all nodes in s reach the same set of nodes)
4.3. ispath(s): whether an edge set s in e forms a path (if s is connected and is of a linear shape)
4.4. paths(x): paths in e from node x
With items 4-6 and 1, we can write a one-line description that takes edges e and returns the tree center. Write the definitions; each one should be short--fit on one line (hint: use only set formers (and quantified expressions for 4.1 and 4.2); no loops or assignments are needed). Not to worry most about running times; worry most about clarity.

These are very intensive exercises; imagine learning a new, one of the most advanced, language in one day!