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.

Write at least two different versions for1.f(x)2.f{x}3.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

**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

**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.

We may compute the following three items, and, to compute item 4, a few things may help. 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!