Due: Tuesday October 28 (at the beginning of class 10:0am).

Problems:

1. 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?

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