Exercise 4.1 Consider the two-dimensional placement of mxn functional cells as an array of size m x n. All the cells have identical shape and size. Let the cells be numbered 1, 2, ...,mxn. Cell i is placed in row r; and column c; of the array. (1) Given two cells i and j, derive an expression for the Manhattan distance dij between the two cells in terms of ri, Ci, rj, and ej. (2) Let Wij be the number of wires between cells i and j. Derive an expres- sion for the total wirelength of the placement. (3) Verify your formula for Figure 4.2(b). Exercise 4.2 Given n modules to be placed in a single row show that there are unique placements of n modules. When n is large, show that the number of placements is exponential in n. Exercise 4.3 A 5-point net is shown in Figure 4.40. The cost of connecting one point to another is measured by the Manhattan distance between the two points. Construct a minimum spanning tree to join all the five points of the net. What is the cost of the minimum spanning tree? B E D Fig. 4.40 Net of Exercise 4.3