# Tag Info

Accepted

### How to convert a decision tree to an automaton?

A decision tree is a model of computation which makes sense for instance of constant size. In contrast, a language is usually a collection of instances of unbounded size. An automaton (in this context)...
• 278k
Accepted

### how does the shap algorithm work in polynomial time?

First, some notation. A decision tree is a binary tree in which each internal node is labelled by one of $x_1,\ldots,x_n$, and has two outgoing edges labelled $0$ and $1$. Leaves are labelled with ...
• 278k
Accepted

### Lower bound and worst case scenario

When analyzing algorithms it makes little sense to consider the best-case scenario as it is very often trivial and not very informative. You can convince yourself that almost every algorithm can be ...
• 29.6k

### In information theory, why is the entropy measured in units of bits?

Here is a simple intuition. Suppose we consider a random value that takes the values 0 or 1 with equal probability. Then this value can be represented in a single bit. Moreover, its Shannon entropy ...
• 164k
Accepted

### What is the main difference between binary decision tree and binary decision diagram(BDD)?

One is a tree; one is not. A BDD is a directed acyclic graph (dag), but not necessarily a tree. This allows a BDD to be more compact, in some cases. That's the only essential difference. Of course,...
• 164k
Accepted

### What do Arora and Barak mean by $x|_S$ in their definition of certificate complexity?

It is a typo. $S$ indeed should be a subset of $[n] = \{1,2,\ldots,n\}$. On page 263, in the second sentence of their proof of Theorem 12.5, they list a 0-certificate (or 1-certificate) as a subset of ...
Accepted

### What machine learning training algorithm to use for this kind of string dataset?

You want to perform supervised learning, i.e., you have set of training examples (in this case, a set of 4-vectors with a label that corresponds to one of the 100 songs). So in particular, you want to ...
• 22.7k
Accepted

• 278k
1 vote

### Decision tree complexity of deciding whether array is "zigzag"

You can prove a lower bound of $n-3$ comparisons, almost matching the trivial upper bound of $n-1$ comparisons (surely the gap can be closed with a bit more work). The proof uses an adversary argument....
• 278k

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