\documentclass{article} \input{6854-preamble} \usepackage{clrscode} \begin{document} \psetnum{11} \date{2004/11/23} \collab{Collaborators: \{\texttt{sarahl,pramook}\}} \begin{pset} \begin{problem} Suppose we are given $N$ horizontal and vertical line segments in the plane. We give an external-memory sweep-line algorithm for identifying the $K$ intersections between them. We begin by generating a list of $x$-coordinates of interest (left and right endpoints of horizontal segments and vertical segment $x$-coordinates), and sorting them. We then sweep a vertical line across the plane from left to right, maintaining a buffer tree sorted by $y$-coordinate of active line segments. For each point, \begin{itemize} \item if it is a left endpoint of a horizontal segment, we $\proc{Insert}$ the segment into the buffer tree, ordered by its $y$-coordinate. \item if it a right endpoint of a horizontal segment, we \proc{Delete} the $y$-coordinate. (Note that each $y$-coordinate is inserted no more than once, since no two horizontal segments intersect.) \item if it is a vertical segment, we perform a $\proc{Batched-Range-Search}$ over the $y$-coordinates of the endpoints. Any matching horizontal segment intersects the vertical segment, so we output the intersection. (We tag both the \proc{Batched-Range-Search} and the \proc{Insert} records in the buffer tree with segment identifiers, so we know which segments are intersecting.) \end{itemize} Once the full plane has been swept, we perform a \proc{Flush} operation to ensure that all pending output from the buffer tree is produced. This algorithm requires $\bigO{\frac{N}{B} \log_{\frac{M}{B}} \frac{N}{B} + \frac{K}{B}}$ memory accesses. There are $\bigO{N}$ points along which the line is swept, since each segment contributes at most two. The initial sorting step requires $\bigO{\frac{N}{B} \log_{\frac{M}{B}} \frac{N}{B}}$ memory accesses. For each of the $\bigO{N}$ positions of the sweep line, we perform a \proc{Insert}, \proc{Delete}, or \proc{Batched-Range-Search}; the first two operations require $\bigO{\frac{1}{B} \log_{\frac{M}{B}} \frac{N}{B}}$ amortized memory accesses, and the latter requires $\bigO{\frac{1}{B} \log_{\frac{M}{B}} \frac{N}{B} + \frac{k}{B}}$ amortized memory accesses, where $k$ is the size of the output produced by that \proc{Batched-Range-Search} operation. So the total number of memory accesses required by the sweep-line portion of the algorithm is $\bigO{\frac{N}{B} \log_{\frac{M}{B}} \frac{N}{B} + \frac{K}{B}}$. Performing the final \proc{Flush} step requires $\bigO{\frac{N}{B} \log_{\frac{M}{B}} \frac{N}{B}}$ memory accesses. So the total cost is $\bigO{\frac{N}{B} \log_{\frac{M}{B}} \frac{N}{B} + \frac{K}{B}}$ memory accesses. \end{problem} \begin{problem} \begin{subproblem} We give a procedure for adding a pointer from each node to its successor's successor. We keep one copy of the linked list in the original ordering, and make another copy which we sort by the successor field. This requires $\bigO{\frac{N}{B} \log_{\frac{M}{B}} \frac{N}{B}}$ memory transfers using the black box. We then scan through these two lists in lockstep. Node $i$ in the originally-ordered list (call this $N_i$) will be the successor of node $i$ in the successor-ordered list (call this $S_i$). So we can add a successor's-successor pointer from $S_i$ to $N_i$'s successor. This requires $\bigO{\frac{N}{B}}$ memory transfers: a standard scanning procedure can be used. So the total cost is $\bigO{\frac{N}{B} \log_{\frac{M}{B}} \frac{N}{B}}$. \end{subproblem} \begin{subproblem} We now label each node with the outcome of a fair coin flip. Let $\alpha = \nicefrac{1}{4}$. We can obtain $\alpha N$ selected nodes in expectation by selecting the nodes which are marked \textsf{H} by the coin flip \emph{and} whose successors are marked \textsf{T}. This gives $\frac{N}{4}$ nodes in expectation: the probability that any node $x$ is selected is \[ \Pr{\left(x = \mathsf{H}\right) \cap \left(\proc{Succ}(x) = \mathsf{T}\right)} = \frac{1}{2}\left(\frac{1}{2}\right) = \frac{1}{4} \] since the coin flips are fair. So by linearity of expectation $\frac{N}{4}$ nodes are selected in expectation. This requires $\bigO{\frac{N}{B}}$ memory transfers once we have the originally-ordered and successor-ordered sorted lists described above. The assignment of a coin-flip value to each node can be performed by scanning over the lists in lockstep, and selecting the nodes $S_i$ such that $S_i$ is marked \textsf{H} and $N_i$ is marked \textsf{T} can also be performed by scanning over the list. So $\bigO{\frac{N}{B}}$ memory transfers are required for scanning, plus $\bigO{\frac{N}{B} \log_{\frac{M}{B}} \frac{N}{B}}$ for the sort. \end{subproblem} \begin{subproblem} We now remove all nodes which are not selected from the list. We use a scanning approach: we scan over the sorted originally-ordered and successor-ordered lists in lockstep again, partitioning the nodes into two output lists: if a node is selected, we place it in the first output list, and if it is not, we place it in the second output list. In addition, as we process a node, we add a pointer from each node (a $N_i$) to its predecessor ($S_i$). Since memory accesses are sequential, this can be performed using $\bigO{\frac{N}{B}}$ memory accesses for the scanning, plus the sorting time. \end{subproblem} \begin{subproblem} Now suppose we have recursively solved the list-ranking problem on the set of unselected elements. We show how to extend this solution to the original list-ranking problem. Recall that nodes were selected such that no two selected nodes were adjacent; so each selected node has both a predecessor and a successor in the unselected set. We sort the unselected elements by their (now-computed) rank, and sort the selected elements by their predecessor's rank. Then we scan over the two lists in lockstep. The $i$th item $S_i$ in the selected list will have the $i$th item $U_i$ in the unselected list as its predecessors. So $S_i$'s rank will be one greater than the rank of $U_i$, and we can assign it this rank. Computing this requires $\bigO{\frac{N}{B} \log_{\frac{M}{B}} \frac{N}{B}}$ memory accesses for sorting, and $\bigO{\frac{N}{B}}$ for scanning, so it is dominated by the sorting cost. \end{subproblem} \begin{subproblem} Each problem of size $N$ reduces to solving the list-ranking problem over the set of unselected elements, which has expected size $\frac{3}{4} N$, plus a merging cost of $\bigO{\frac{N}{B} \log_{\frac{M}{B}} \frac{N}{B}}$. So the recurrence is \[ T(N) = T\left(\frac{3}{4} N\right) + \bigO{\frac{N}{B} \log_{\frac{M}{B}} \frac{N}{B}} \] and we also have the standard base case \[ T(M) = \bigO{\frac{M}{B}} \] so the first level of the recursion tree (which has no branches) has cost $\bigO{\frac{N}{B} \log_{\frac{M}{B}} \frac{N}{B}}$, and the next has cost $\bigO{\frac{3}{4}\frac{N}{B} \log_{\frac{M}{B}} \frac{\frac{3}{4}N}{B}}$, etc., so the total cost is \[ \sum_{i = 0}^{\log_{\frac{3}{4}} \frac{M}{N}} \bigO{\left(\frac{3}{4}\right)^i\frac{N}{B} \log_{\frac{M}{B}} \frac{N}{B}} \le \sum_{i = 0}^\infty \bigO{\left(\frac{3}{4}\right)^i\frac{N}{B} \log_{\frac{M}{B}} \frac{N}{B}} = \bigO{\frac{N}{B} \log_{\frac{M}{B}} \frac{N}{B}}\] as it is simply a standard geometric series. \end{subproblem} \end{problem} \begin{problem} \begin{subproblem} Suppose we are given an array of $N$ nodes in arbitrary order with left and right child lists. We show how to augment the nodes with their parent pointers and whether they are left or right children of their parent. We begin by identifying the left children. We make a copy of the list and sort it by the value of the left child pointer. We then scan through the newly sorted list. For each element $x$ in the left-child-ordered list, we add a parent pointer from $x$.\textsf{left-child} to $x$, and mark $x$.\textsf{left-child} as a left-child. This is a scanning algorithm on the sorted list. But it also accesses the originally-ordered list in a scanning order: since left-child-ordered list is sorted by left-child, the left children of the list will be in a sequential ordering of the original list. Thus the number of memory accesses is bounded above by the amount needed for scanning, $\bigO{\frac{N}{B}}$. The dominating factor is the cost required for sorting, $\bigO{\frac{N}{B} \log_{\frac{M}{B}} \frac{N}{B}}$. This procedure identifies the left children; a symmetric procedure identifies the right children in the same time bound. \end{subproblem} \begin{subproblem} Now consider the problem of generating an Euler tour of the tree (with edges doubled to make it feasible). Note that an Euler tour satisfies the following local property at any vertex $x$: the vertex first traverses the edge $(x.\mathsf{parent} \to x)$, then $(x \to x.\text{\textsf{left-child}})$, then traverses $x$'s left subtree and eventually returns via the edge $(x.\text{\textsf{left-child}} \to x)$, then leaves via $(x \to x.\text{\textsf{right-child}})$ to traverse $x$'s right subtree, then eventually returns via $(x.\text{\textsf{right-child}} \to x)$, and finally leaves via the $(x \to x.\mathsf{parent})$ edge. Indeed, this property, if satisfied for all $x$, is sufficient to define an Euler tour over a tree. Thus at most 6 edges are required in an Euler tour per vertex: three entering the vertex, and three leaving. (This is in the case where a node has both left and right children; if one or both subtrees are missing, then we simply ignore the two edges that correspond to that subtree.) We can therefore represent the Euler tour in the following way: for every vertex $x$, we ``divide'' it into three vertices $x_1$, $x_2$, and $x_3$, numbered in the order they are traversed in the Euler tour. Then the tour takes a path \[ \mathsf{parent} \to x_1 \to \text{\textsf{left subtree}} \to x_2 \to \text{\textsf{right subtree}} \to x_3 \to \mathsf{parent} \] Note that each vertex has only one incoming and one outgoing edge, so it can easily be expressed as a linked list. Our procedure for generating the Euler tour is as follows: we scan over the array of nodes, and generate an output array in which each input node is replaced with the three corresponding output nodes. For each node $x$, let $p$ be its parent, and $l$ and $r$ be its left and right subchildren respectively. Then we output $x_1, x_2$, and $x_3$ with the following links: \begin{align*} x_1.\mathsf{prev} &= \begin{cases} p_1 & \text{ if $x$ is a left subchild of $p$} \\ p_2 & \text{ if $x$ is a right subchild of $p$} \end{cases} \\ x_1.\mathsf{next} &= l_1 \\ x_2.\mathsf{prev} &= l_3 \\ x_2.\mathsf{next} &= r_1 \\ x_3.\mathsf{prev} &= r_3 \\ x_3.\mathsf{next} &= \begin{cases} p_2 & \text{ if $x$ is a left subchild of $p$} \\ p_3 & \text{ if $x$ is a right subchild of $p$} \end{cases} \end{align*} Note that if $x$ has no left subchild, we simply change $x_1.\mathsf{next}$ to point to $x_2$ and set $x_2.\mathsf{prev}$ accordingly, and similarly if $x$ has no right subchild. It is straightforward (but tedious) to verify the correctness and consistency of the resulting linked list, which is the Euler tour. This is produced using a scanning algorithm, so the required memory is $\bigO{\frac{N}{B} + 1}$. The resulting linked list has 3 nodes for each node in the input list, so its size is $\bigO{N}$. \end{subproblem} \begin{subproblem} Suppose we wish to compute the size of the subtree rooted at each vertex. We can do so by generating the Euler tour using the procedure described above and computing the list ranking of the tour in $\bigO{\frac{N}{B} \log_{\frac{M}{B}} \frac{N}{B}}$. Recall that the Euler tour takes the path \[ x.\mathsf{parent} \to x_1 \to \text{\textsf{$x$'s subtree}} \to x_2 \to x.\mathsf{parent} \] so the size of the subtree rooted at $x$ is the number of (distinct) vertices the tour passes between when it reaches $x_1$ and when it leaves $x_3$, inclusive. Each vertex appears three times in this tour (as $a_1$, $a_2$, and $a_3$), so the size of the subtree rooted at $x$ is \[ \proc{Subtree-Size}(x) = \frac{\proc{List-Rank}(x_3) - \proc{List-Rank}(x_1) + 1}{3} \] We can compute this value for all $x$ by scanning over the Euler tour array in $\bigO{\frac{N}{B}}$, so the total number of memory accesses required is $\bigO{\frac{N}{B} \log_{\frac{M}{B}} \frac{N}{B}}$. \end{subproblem} \end{problem} \begin{problem} \begin{subproblem} Suppose the input stream contains $n$ (non-distinct) elements, more than $\frac{n}{2}$ of which are equal to some distinct value $A$. We show that at the end of the stream, the register contains value $A$. Suppose that at the end of the stream the register contains some element $B \neq A$. This leads to a contradiction. Every time that $A$ appeared in the input stream, there are two cases: if some other value stays in the register, then the $A$ lowers its count and there must have been a non-$A$ element before the $A$ in the stream; if the register contains $A$, then it increments the counter, and since in order for $A$ to not be in the register at the end, the counter eventually reaches zero, and so there must be a corresponding non-$A$ element somewhere after the $A$ in the stream. Thus, for each $A$ element, there is a corresponding non-$A$ element in the stream. So since there are at least $\frac{n}{2} + 1$ $A$ elements in the stream, there must be at least twice as many non-$A$ elements. But there are only $n$ elements in the stream. This is a contradiction $\nleftrightarrow$. \end{subproblem} \begin{subproblem} We maintain $k$ counters with $k$ registers. We initialize the registers to empty and the counters to zero. For each element in the stream, \begin{itemize} \item if the element is contained in one of the registers, we increment the associated counter. \item if the element is not contained in any of the registers, and there are any empty registers (with associated counter of zero), we place the new element in some empty register and set its counter to 1. \item if the element is not contained in any of the registers, and there are no empty registers, we decrement each counter by 1, and empty any registers whose associated counter now equals zero. If a register has been emptied, we place the new element in it and set the associated counter value to 1. \end{itemize} The proof of correctness for this algorithm is essentially the same as for the $k=1$ case: each element that is not in a register can decrement $k$ counters, so for each occurrence of an element that does not wind up in a register at the end of the algorithm, there must be $k$ occurrences of other elements. Thus, if the number of occurrences of this element is $x$, then there must be at least $kx$ other elements, and so the total number of elements is at least $x + kx$. But there are $n$ elements, so \begin{align*} x + kx &\le n \\ x &\le \frac{n}{1 + k} \end{align*} and thus all the elements that occur with frequency more than $\frac{1}{1+k}$ will be in a register at the end. \end{subproblem} \end{problem} \begin{problem} $\le$ 10 hours \end{problem} \end{pset} \end{document}