Q1 A slicing floorplan is a decomposition of a rectangle with horizontal and vertical sides using horizontal and vertical cuts.(see fig 1) A slicing floorplan can be represented by a binary tree, called a slicing tree, whose internal nodes represent the cuts, and whose external nodes represent the basic rectangles into which the floorplan is decomposed by the cuts.(See fig. 2).The compaction problem is defined as follows. Assume that each basic rectangle of a slicing floorplan is assigned a minimum width w and a minimum height h. The compaction problem is to find the smallest possible height and width for each rectangle of the slicing floorplan that is compatible with the minimum dimensions of the basic rectangles.Namely this problem requires the assignment of values h(v) and w(v) to each node v of the slicing tree such that:

W(v)  =  w                 if v is an external node whose basic 
                           rectangle has minimum width w.

      =  max(W(w),W(z))    if v is an internal node associated with 
                           a horizontal cut with left child w and 
                           right child z.
  
      = W(w)+W(z)          if v is an internal node associated with 
                           a vertical cut with the left child w and 
                           right child z.

h(v)  =  h                 if v is an external node whose basic
                           rectangle has minimum height h.

      =  max(h(w),h(z))    if v is an internal node associated with
                           a horizontal cut with left child w and
                           right child z.
 
      = h(w)+h(z)          if v is an internal node associated with
                           a vertical cut with the left child w and
                           right child z.

Design a data structure for slicing floorplans that supports the operations.

1. Create a floorplan consisting of a single basic rectangle.
2. Decompose a basic rectangle by means of a horizontal cut.
3. Decompose a basic rectangle by means of a vertical cut.
4. Assign minimum height and width to a basic rectangle.
5. Draw the slicing tree associated with the floorplan.

Q2. Implement the tree traversal scheme which the UNIX uses while listing the files/directories by ls command. You must create your own data structure for directory and file creation. That means commands like touch, mkdir, rmdir and rm are to be also implemented.

Q3. Given a preorder and an inorder traversal of a binary tree, design an applet that shows the step by step creation of the tree. Your program should also give a suitable response if no valid tree can be constructed from the input. Provide a set of test cases with your code.

You may use the following input for testing:

        preorder: 3 2 1 5 4 8 7 6 9 10 13 12 11 14
        inorder : 1 2 4 5 3 6 7 9 8 10 11 12 14 13

How To Submit

You have to upload your solution files duly zipped on 202.141.81.74 latest by due date and time,however assignments will also be checked by the TAs during lab hours.

Please follow the instructions for uploading, mentioned on the site, while you are uploading the files.