New answers tagged

0

In order to get the files in the desired order, simply follow the following rule: A node can be deleted iff all of its children have been deleted. This is the same as a postorder traversal of a tree. Let's say you use a container $S$ for your search structure (stack for DFS or queue for BFS). Now, we create a stack $T$ which will in the end will be the ...


0

I'm not sure about the algorithm modification to directly call the callback function in a reverse order, but I found a way to do this without extra memory allocation. My solution is to embed a doubly linked list node within the data structure storing rules. (It actually turns out there was already a linked list node in the data structure I used for other ...


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)....


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

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 ...


0

I think we can reduce uncolored graph isomorphism to this problem. For connected rooted graphs $G$ and $H$, construct trees $G'$ and $H'$ in the following way: Begin creating graph $G'$ with just a single vertex $0$. This vertex will be the root of the resulting tree (which will be just of depth 2). For each vertex $v$ in $G$, create a vertex $v$. ...


Top 50 recent answers are included