New answers tagged

1

You have to do three things: Exhibit an algorithm. Prove that it is correct (it outputs the right value). Prove that its running time is $O(|V|)$. @Steven describes one way to prove the running time. One can probably prove correctness using structural induction as well.


2

You can prove that formally by using structural induction. The structure of the proof is as follows: Observe that a preorder traversal of a tree with $1$ vertex requires constant time. Then, assume that a preorder traversal of a tree with up to $i \ge 1$ vertices can be performed in time at most $c \cdot i$, for a suitable constant $c$, and show that the ...


0

Interesting question. For a better theoretical understanding of the whole theory I would suggest you to re-read "Introduction to Algorithms, Third Edition, Cormen" Chapter 12 (Trees) and Chapter 13 (Red-Black Trees). Since it is stated there that (page 311): As an immediate consequence of this lemma, we can implement the dynamic-set operations ...


2

A tree structure can be completely described by three functions: a function that given a node $x$ returns the number of children of that node, a function that given a node $x$ and index $i$ returns the $i$th child of that node, and a function that given a node $x$ returns an associated value $v$ stored at that node.


0

The following paper considers your task in the general case: Partial-Match Retrieval Algorithms. Ronald L. Rivest. SIAM Journal Computing, vol 5 no 1, March 1976. It yields a data structure with a running time that is slightly better than enumerating all words in the dictionary and checking each to see if it meets the conditions.


1

If I've got nothing more than a check of whether an arbitrary string is an English word, I have to do 5^26 calculations. $5^{26}$ is of order $10^{18}$, while the actual number of English words is of order $10^5$. So, depending on your application, simply enumerating all words and checking whether they satisfy the constraints may already be sufficiently ...


1

What you can do is to add a counter $t$ to each node, initially 0, indicating how many of its children are terminal. When $t = c$ where $c$ is the number of children of a node, the node itself becomes terminal and increments the $t$ counter of its parent. Note that with this definition leaf nodes are automatically terminal, as they have no children, giving $...


Top 50 recent answers are included