# CMPT 280– Intermediate Data Structures and Algorithms Assignment 7

\$35.00

Category:

## Description

5/5 - (5 votes)

2.1 Topological Sort of a Directed Graph
Imagine a directed graph is used to represent prerequisite relationships between university courses. There
is a node in the graph for each course, and a directed edge from course A to course B if course A is a
prerequisite for course B. Here’s what such a graph would look like for some of our courses might look
like:
CMPT 141
MATH 110 CMPT 145
CMPT 270 CMPT 214 CMPT 260
CMPT 280 CMPT 215
Note that this is a graph and not a tree, because CMPT 270 has more than one “parent”. But, there are no
cycles in this graph.
If there are no cycles in a directed graph, we can perform an operation called a topological sort. A
topological sort of a graph produces a linear ordering of the nodes such that if there is a directed edge
from node A to node B, then node A appears before node B in the ordering. In the specific case of
the course prerequisite graph, a topological sort produces an ordering of the nodes such that no course
appears before any of its prerequisites – precisely the thing one needs to know in order to take courses in
the right order!
Note that there is not necessarily a unique answer for topological sort. For example, in the graph pictured above, we could take MATH 110 and CMPT 111 in either order (because neither has prerequisites),
so both of the following sequences would be valid topological sorts:
• 111, 110, 115, 270, 214, 260, 280, 215
• 110, 111, 115, 270, 214, 260, 280, 215
Also note that 280 and 215 could be taken in either order as long as they are taken after both 270 and 214,
resulting in more possible topological orderings:
• 111, 110, 115, 270, 214, 260, 215, 280
• 110, 111, 115, 270, 214, 260, 215, 280
The basic algorithm for topological sort, and a variation that is relevant to the specific problem we will
want to solve, is presented with Question 2.
Finally, it is worth noting that you cannot perform a topological sort on a graph that has a cycle. If
there is a cycle, then it is not possible to satisfy the prerequisites for any node in the cycle because each
course in the cycle is a prerequisite of itself.
Page 2
Question 1 (42 points):
For this question you will be implementing a k-D tree. We begin with introducing some algorithms
that you will need. Then we will present what you must do.
Helper Algorithms for Implementing k-dimensional Trees
As we saw in class, in order to build a k-D tree we need to be able to find the median of a set of
elements efficiently. The “j-th smallest element” algorithm will do this for us. If we have an array of n
elements, then finding the n/2-smallest element is the same as finding the median.
Below is a version of the j-th smallest element algorithm that operates on a subarray of an array
specified by offsets le f t and right (inclusive). It places at offset j (where le f t ≤ j ≤ right) the element
that belongs at offset j if the subarray were sorted. Moreover, all of the elements in the subarray
smaller than that belonging at offset j are placed between offsets le f t and j − 1 and all of the elements
in the subarray larger than that element are placed between offsets j + 1 and right, but there is no
guarantee on the ordering of any of these elements! The only element guaranteed to be in its sorted
position is the one that belongs at offset j. Thus, if we want to find the median element of a subarray
of the array list bounded by offsets le f t and right, we can call
jSmallest(list, left, right, (left+right)/2)
The offset (le f t + right)/2 (integer division!) is always the element in the middle of the subarray
between offsets le f t and right because the average of two numbers is always equal to the number
halfway in between them.
The j-smallest algorithm is presented in its entirety on the next page.
Page 3
Algorithm jSmallest ( list , left , right , j )
list – array of comparable elements
left – offset of start of subarray for which we want the median element
right – offset of end of subarray for which we want the median element
j – we want to find the element that belongs at array index j
To find the median of the subarray between array indices ’ left ’ and ’ right ’ ,
pass in j = ( right + left )/2.
Precondition : left <= j <= right Precondition : all elements in ’ list ’ are unique ( things get messy otherwise !) Postcondition : the element x that belongs at offset j , if the subarray were sorted , is at offset j . Elements in the subarray smaller than x are to the left of offset j and the elements in the subarray larger than x are to the right of offset j . if( right > left )
// Partition the subarray using the last element , list [ right ] , as a pivot .
// The index of the pivot after partitioning is returned .
// This is exactly the same partition algorithm used by quicksort .
pivotIndex := partition ( list , left , right )
// If the pivotIndex is equal to j, then we found the j-th smallest
// element and it is in the right place ! Yay!
// If the position j is smaller than the pivot index , we know that
// the j-th smallest element must be between left , and pivotIndex -1 , so
// recursively look for the j-th smallest element in that subarray :
if j < pivotIndex jSmallest ( list , left , pivotIndex -1 , j ) // Otherwise , the position j must be larger than the pivotIndex , // so the j-th smallest element must be between pivotIndex +1 and right . else if j > pivotIndex
jSmallest ( list , pivotIndex +1 , right , j )
// Otherwise , the pivot ended up at list [j] , and the pivot *is* the
// j-th smallest element and we ’re done .
Notice that there is nothing returned by jSmallest, rather, it is the postcondition that is important.
The postcondition is simply that the element of the subarray specified by left and right that belongs
at index j if the subarray were sorted is placed at index j and that elements between le f t and j − 1
are smaller than the j-th smallest element and the elements between j + 1 and right are larger than
the j-th smallest element. There are no guarantees on ordering of the elements within these parts of
the subarray except that they are smaller and larger than the the element at index j, respectively. This
means that if you invoke this algorithm with j = (right + le f t)/2 then you will end up with the median element
in the median position of the subarray, all smaller elements to its left (though unordered) and all larger elements
to its right (though unordered), which is just what you need to implement the tree-building algorithm!
NOTE: for this algorithm to work on arrays of NDPoint280 objects you will need an additional parameter d that specifies which dimension (coordinate) of the points is to be used to compare points.
An advantage of making this algorithm operate on subarrays is that you can use it to build the k-d
tree without using any additional storage — your input is just one array of NDPoint280 objects and
you can do all the work without any additional arrays — just work with the correct subarrays.
Page 4
You may have noticed that jSmallest uses the partition algorithm partition the elements of the
subarray using a pivot. The pseudocode for the partition algorithm used by the jSmallest algorithm
is given below. Note that in your implementation, you will, again, need to add a parameter d to denote
which dimension of the n-dimensional points should be used for comparison of NDPoint280 objects.
// Partition a subarray using its last element as a pivot .
Algorithm partition ( list , left , right )
list – array of comparable elements
left – lower limit on subarray to be partitioned
right – upper limit on subarray to be partitioned
Precondition : all elements in ’ list ’ are unique ( things get messy otherwise !)
Postcondition : all elements smaller than the pivot appear in the leftmost
part of the subarray , then the pivot element , followed by
the elements larger than the pivot . There is no guarantee
about the ordering of the elements before and after the
pivot .
returns the offset at which the pivot element ended up
pivot = list [ right ]
swapOffset = left
for i = left to right -1
if( list [ i ] <= pivot ) swap list [ i ] and list [ swapOffset ] swapOffset = swapOffset + 1 swap list [ right ] and list [ swapOffset ] return swapOffset ; // return the offset where the pivot ended up Algoirthm for Building the Tree An algorithm for building a k-d tree from a set of k-dimensional points is given below. It is slightly more detailed than the version given in the lecture slides. It uses the jSmallest algorithm presented above. Algorithm kdtree ( pointArray , left , right , int depth ) pointArray - array of k - dimensional points left - offset of start of subarray from which to build a kd - tree right - offset of end of subarray from which to build a kd - tree depth - the current depth in the partially built tree - note that the root of a tree has depth 0 and the \$k\$ dimensions of the points are numbered 0 through k -1. if pointArray is empty return null ; else // Select axis based on depth so that axis cycles through all // valid values . (k is the dimensionality of the tree ) d = depth mod k ; medianOffset = ( left + right )/2 // Put the median element in the correct position // This call assumes you have added the dimension d parameter // to jSmallest as described earlier . Page 5 jSmallest ( pointArray , left , right , d , medianOffset ) // Create node and construct subtrees node = a new kD - tree node node . item = pointArray [ medianOffset ] node . leftChild = kdtree ( pointArray , left , medianOffet -1 , depth +1); node . rightChild = kdtree ( pointArray medianOffset +1 , right , depth +1); return node ; Implementing the k-D Tree – What You Must Do Implement a k-D tree. You must use the NDPoint280 class provided in the lib280.base package of lib280-asn6 to represent your k-dimensional points. You must design and implement both a node class (KDNode280.java) and a tree class (KDTree280.java). Other than specific instructions given in this question, the design of these classes is up to you. You may use as much or as little of lib280 as you think is appropriate. You’ll be graded in the actual appropriateness of your choices here. You should aim to make the class fit into lib280 and its hierarchy of data structures, but you should not force things by extending classes inappropriately. You may use whatever private/protected methods you deem necessary. A portion of the marks for this question will be awarded for the design/modularity/style of the implementation of your class. A portion of the marks for this question will be awarded for acceptable inline and javadoc commenting. Your ADT must support the following operations: • Construct a new (balanced) k-D tree from a set of k-dimensional points (it must work for any k > 0).
• Perform a range search: given a pair of points (a1, a2, . . . ak
) and (b1, b2, . . . , bk