4

First note that $\text{increase-key}$ must be $O(\log n)$ if we wish for $\text{insert}$ and $\text{find-min}$ to stay $O(1)$ as they are in a Fibonacci heap. If it weren't you'd be able to sort in $O(n)$ time by doing $n$ $\text{insert}$s, followed by repeatedly using $\text{find-min}$ to get the minimum and then $\text{increase-key}$ on the head by $\...


3

This just means that the elements stored in a binary search tree are one dimensional. Or more generally that they can be ordered in some meaningful way. You can think of this ordering as putting all the elements on a line, from "smallest" to "biggest" (for an appropriate notion of small and big depending on the particular case). And partitioning then always ...


3

No, not all foldable data structures are recursive, although the in the non-recursive case what we have is really a degenerate version of a fold. For example, we can view the function if : Bool -> a -> a -> a as a fold over the type Bool. In general, when dealing with recursive or non-recursive types, the fold are called eliminators, since they ...


2

Let $R=\{r_1, \cdots, r_n\}$ be the set of all rows. Let $C=\{c_1, \cdots, c_m\}$ be the set of all columns. If and only if the matrix entry at row $i$ and column $j$ is 1, we connect $r_i$ with $c_j$ with an edge. Now we have a bipartite graph $G=((R,C), V)$, since there is no edge between two rows nor between two columns. A vertex cover of $G$ ...


2

There is a $O(|X|)$ algorithm for this problem using a stack. Algorithmic details: For a building $i\in \{1, ..., n\}$, we will be pushing $i$ onto the stack $S$. For building $i$, let $X_i$ be its coordinate, $H_i$ be its height and $R_i$ be its range. While iterating over the data (i.e. $i = 1 ... n$), we maintain the loop invariant that $S$ will only ...


1

Make a Node class whose objects hold and an array of references to the other nodes they connects to. Make a Graph class whose objects store a dictionary mapping node IDs to nodes, and implement your 3 methods.


1

The nice picture in the question does not include the summary nodes nor the min and max fields, both of which are indispensable components of a van Emde Boas tree (vEB tree). A better illustration might be the following picture taken from how to read off the set represented by a van-Emde-Boas tree, which was drawn by Raphael based on a figure in CLRS, where ...


1

The Natural Language Toolkit (NLTK) offers binarization: nltk.treetransforms.chomsky_normal_form(). The algorithm in NLTK implements the standard, straight-forward transformation into Chomsky normal form. It assumes the tree was generated via an underlying (context-free) grammar. This results in the deep trees in the bottom row (diagram in the question post)....


Only top voted, non community-wiki answers of a minimum length are eligible