CSSAP 443: Homework Assignment #2

2D Search Structures

Dynamic Programming and

Greedy Algorithms

 

Assigning Date: May 28, 2003

Due Time: June 4, 2003 at 3:40pm

 

 

1.        (40%) Heard about your mp3 solution to the space-searching problem, your manager became very excited and decided you should be the chef architect in designing the brand new web-based searching system for locating regions on a map. In this system, a Tpolygon object represents each region. A map displays a large set of Tpolygon objects. Your job is to design a search structure that supports efficient selection of polygons based on the user’s input (either a point, or a T2dBound). Worried by your description of the quadtree structures, your manager decided your system should be based on uniform spatial structure. Being a junior software engineer working for you, I implemented the Tpolygon and related supporting classes as:

 

class Tpolygon {

                                                private:

//

// private implementation methods that you don’t care about …

//

public:

void         BoundingBox(T2dBound&);

                                                        // returns the 2d bounding box of this polygon

bool         IntersetcsBound(const T2dBound&);

                                                        // returns true if polygon intersects the input 2d bound

bool         ContainsPoint(const T2dPoint&);

                                                // returns true if polygon contains the 2d point.

                void         PrintPolygonID();

                                                // polygon has a unique id, this function prints out that id

                };

 

class TpolygonLink {

                public:

Tpolygon                                *fPolygon;

                        TpolygonLink         *fNext;

                };

 

class TpolygonList {

public:

fPolygonLink *fHead;

                                                // fHead points to a simple link list of TpolygonLink

                                                // last link in the list has its fNext points to null;

 

void Compute2DboundOfList(T2dBound &resultBound);

                                                        // Goes through each TpolygonLink in the link list compute

// the smallest 2d bounding box that contains all the

// polygons. The result 2d bound is returned in resultBound

 

                        TpolygonList* CreateNewList(T2dBound&);

                                                        // Goes through each TpolygonLink in the link list looking

// for polygons that intersects the input 2d bound. Returns a

// new TpolygonList that contains new TpolygonLink

                               // pointing to Tpolygons that intersects the input 2d bound.

                                                        // The polygon list pointed to by fHead is not changed.

};

where 

 

class T2dBound{

public:

                double fMinX, fMaxX;

                        double fMinY, fMaxY;

 

                        // Constructor
                                T2dBound(double xMin, double xMax, double yMin, double yMax) {

fMinX = xMin;

fMaxX = xMax;

fMinY = yMin;

fMaxY = yMax;
}

                };

 

Recognizing each spatial cell may contain more than one polygon, you have designed the, TstructureCell, and TuniformStructure classes to look like:

 

 

class TstructureCell {

                public:

                                 TpolygonList         *fPolygons;             // list of polygons inside this cell

 

                void                         SearchCell(const T2dBound&);

                        void                         SearchCell(const T2dPoint&);

                                                                        // for each polygon that is found, searchStructure

                                                                // will call the PrintPolygonID() method.

                };

 

                class TuniformStructure {

private:

TstructureCell         **fStruct;                // the structure

Int                           fXres, fYres;           // x and y resolution of the structure

T2dBound               fBound;                   // bound of all the polygons

public:

void                        BuildStruct( TpolygonList *allPolygons,

// All the polygons in the world

   int  resX,  int resY

// the structure will be resX by resY);

 

                        void                         SearchStructure(const T2dBound&);

                        void                         SearchStructure(const T2dPoint&);

                };

 

 

a.        (10%) Please show the implementation of TuniformStructure::BuildStruct().

 

b.       (20%) Please show the implementation of the two TuniformStructure::SearchStructure() and the two corresponding functions TstructureCell::SearchCell().

 

c.        (10%) Assuming there are n polygons, and the polygons are very small when comparing to the size of the map (can almost treat them as points), and that the polygons are uniformly distributed. What is the running time of your BuildStruct() implementation? What is the average running time of your SearchStructure(T2dPoint) implementation? Please express your answers in terms of n, resX, and resY.

 

 

2.         (10%).  Given below is the pseudo-code for merge, where two sorted sub-arrays are merged into one sorted array. (Winter 2001 Mid Term Exam Question)

 

void  merge(A, startIndex, midIndex, endIndex)

        // A                                          - is the integer array

        // startIndex ... midIndex         - is the first sorted sub-array

        // midIndex+1 … endIndex      - is the second sorted sub-array

{

index1 = startIndex;

index2 = midIndex+1;

index = 1;

 

while ( (index<=endIndex) && (index1<=midIndex) && (index2<=endIndex) )

      if (A[index1] <= A[index2])

                      tmpArray[index++] = A[index1++]

        else

                        tmpArray[index++] = A[index2++]

 

while ( index1<=midIndex )

tmpArray[index++] = A[index1++];

 

while ( index2<=endIndex )

tmpArray[index++] = A[index2++];

 

while ( index>=1 )

A[endIndex--] = tmpArray[--index]

}

 

 

(10%) As we have discussed in lectures, the left branch of a decision tree is the less-than-or-equal to branch and the right branch is the greater-than branch. Given an input array of A[a1  a2  a3  … an], please trace the left sub-tree of root-node for merge(A, 3, 4, 7). Show the content of the the A array at each leaf node of your decision tree. (From the root node, trace the entire left-sub tree including the right branches for children of the root node. However, you do not need to trace the right-sub tree of the root node).

 

 

 

3.        (40%) Longest Common Subsequences (LCS). Not convinced that a 2D array with bottom-up approach is necessary for solving the LCS with the following solution:



a.        (10%) You decided to program the above solution with the straightforward top-down recursive approach without memoization. Assuming two input strings, x[1..m] and y[1..n] show the pseudo code for your recursive top-down LCS(int i, int j, string x, string y).

 

b.       (20%) Show the trace of your recursive LCS(3, 3, x, y), given that there are no matching subsequences in the two input strings. From your trace, derive the worst-case runtime of your LCS(n, m, X, Y) implementation. Please express your answer in terms of n and m.

 

c.        (10%) Show the pseudo code of how you would take advantage of memoization with a 2D array and improve the runtime of your LCS() implementation to Θ(nm).

 

 

 

 

 

 

 

 

4.        (10%) For our solution to the matrix chain multiplication problem, if the input matrix Aj has dimension pj-1 rows by pj columns, given the input 4 matrices with dimensions p0 to p4 being 30, 120, 10, 80, 5. Compute the optimal parenthesization and the associated cost. (Hint: I would recommend compute the minimum cost m(i,j) and the s(i,j) tables similar to the ones on page 337, Fig 15-3).

 

 

 

 

This homework assignment will count 7% towards your final grade for this class.