Due: Wednesday May 2 (at the beginning of class 12:00pm).

Problems:

1. For the function f(a,b,c,d,e,f) = adf + cdf + ef + abf + abd
   • Construct the ROBDD for f using the variable order a b c d e f.
   • Use the method in Stanion's paper to construct the BDD for the characteristic function which enumerates all the cuts in the ROBDD you obtained in part a).

2. Label the nodes in this figure using the method in the FlowMap paper assuming K=3. Then give the minimum depth 3-LUT mapping using maximum volume cuts as described in the FlowMap paper. (You probably want to save this figure and print it out several times.)

3. The locations of 10 pins of a net (5,0),(8,2),(12,5),(2,6),(7,7),(5,9),(0,10),(2,12),(7,12) and (9,10) are shown below.
   
   1. What is the half-perimeter for this net?
   2. What is the estimated wirelength from the RISA model?
   3. What is the cost of a minimum spanning tree assuming that every pair of points can be connected by an edge whose cost is the manhattan distance between that pair of points?
   4. For your Minimum Spanning Tree in the previous problem, what is the best wirelength you can obtain by overlapping the edges as much as possible and counting any overlap only once?
   5. What is the cost of a minimal single trunk Steiner Tree? Try both a horizontal trunk and a vertical trunk.
   6. Find a Steiner Tree of as little cost as you can. What is it's wirelength?

4. For the network shown below, calculate
   1. for each node, the longest path to it from any input
   2. for each node, the longest path from it to any output
   3. the length of the critical path (highlight the path)
   4. for each edge, the slack for that edge