# Question
Title: Sampling from a Acyclic Deterministic Finite Automaton
Assume you have a finite language $L$ succinctly represented as a acyclic DFA $M$ (models can't be much simpler than that :) ).

> How can we efficiently sample a word from $L$ with uniform distribution?

Note that counting the number of words in $L$ is easily doable in linear time in the size of $M$, which might be useful for the sampling process.

---

Clarifications:

* $L(M)=L$.
* $M$ is acyclic (has no loops).
* Sampling means you output each word $w\in L$ w.p. $\frac{1}{|L|}$.

# Answer
> 2 votes
Some rough thoughts:

As $M$ is acyclic and deterministic, each word $w$ in $L$ determines a unique path through $M$. Therefore, at each state $q \in Q$, we weight each transition based upon the number of valid subsequent paths (this is the size of the subset of $L$ with a particular prefix). This can be done recursively, and should be linear in the number of transitions.

Then, in order to sample, we can define a function $p: Q\times\Sigma \to R$ that gets us this 'weight' of a particular transition, and use this to define the probability of moving through that transition. At the end of this, rolling a die at each transition should get a normal sample.

I've probably missed something, but it seems like a decent approach.

---
Tags: automata, finite-automata, sampling, randomness
---


# Question
Title: Determining execution times of a concurrent system with exclusive resources
A certain system consists of 2 CPUs. The CPU that is not being used is assigned to a task whose execution is requested. On this system, two tasks, A and B, are executed.These tasks both use a common resource R exclusively.The CPU usage of the tasks A and B, the usage of resource R and the execution sequence are shown in the figure below.if both tasks are started at the same time, how long in ms will the completion of processing take for the two tasks?

**a)120**

**b)140**

**c)150**

**d)200**

According to this question, I understand the resource R is used exclusively by the CPUs, mean if one is using it, the other has to wait.

So my answer is `d` :

```
10 + 50 (first cpu) + 50(second cpu) + 60(first) + 30 (second) = 200

```

But the given answer is `b`, 140 :

```
10 + 50 + 60 + 20 = 140 ms

```

I don't get it, could someone explain to me?

Any help is greatly appreciated!

# Answer
Task A will request R first and immediately get access to ist. So task A will take 10 + 50 + 60 = 120 ms. It will release R after 10 + 50 = 60 ms.

Task B will request R after 40 ms, but has to wait until 60 ms to get acess. Thus Task B will take 60 + 50 + 30 = 140 ms. (You can split the 60 into 40 (cpu) + 20 (waiting).)

The combined execution time is the maximum of the two, i.e. 140 ms.
> 0 votes

---
Tags: concurrency, resource-allocation
---


# Question
Title: Is there a program that will tell you the optimal algorithm for ANY problem if the problem is decidable?
Is there a program that will tell you the optimal algorithm for ANY problem if the problem is decidable? If not, why not? If yes, how can such a program be realistically constructed?

I would prefer an intuitive explanation over a formal one, thanks.

# Answer
As discussed in the comments, the question is not well-defined, since it's unclear what the input is.

However, under any reasonable assumption, no such program exists. One way to see this is through context-free languages: assume we can solve your problem even to the very restricted class of context-free languages. Thus, we have a program $P$ that given a grammar $G$, outputs a TM $M$ whose runtime is optimal (which is also not clearly defined, but let's ignore that for now) and recognizes the same language as $G$.

We can use this program $P$ in order to decide, given a CFG $G$, whether $L(G)=\Sigma^\*$, by running $P$ and checking if it outputs a TM which is just a single accepting state (which is the only optimal TM under a reasonable optimality definition). Since this problem is undecidable, then $P$ cannot exist.
> 4 votes

---
Tags: artificial-intelligence
---


title: Simulate a fair die with a biased die

text:
# Question
Title: Simulate a fair die with a biased die
Given a biased $N$-sided die, how can a random number in the range $\[1,N\]$ be generated uniformly? The probability distribution of the die faces is not known, all that is known is that each face has a nonzero probability and that the probability distribution is the same on all throws (in particular, the throws are independent). This is the obvious generalization of Fair results with unfair die.

Putting this in computer science terms, we have an oracle representing the die rolls: $D : \mathbb{N} \to \[1,N\]$ such that $p\_i = P(D(k)=i)$ is nonzero and independent of $k$. We're looking for a deterministic algorithm $A$ which is parametrized by $D$ (i.e. $A$ may make calls to $D$) such that $P(A()=i) = 1/N$. The algorithm must terminate with probability 1, i.e. the probability that $A$ makes more than $n$ calls to $D$ must converge to $0$ as $n\to\infty$.

For $N=2$ (simulate a fair coin from coin flips with a biased coin), there is a well-known algorithm:

* Repeat “flip twice” until the two throws come up with distinct outcomes ((heads, tails) or (tails, heads)). In other words, loop for $k = 0..\infty$ until $D(2k+1) \ne D(2k)$
* Return 0 if the last pair of flips was (heads, tails) and 1 if it was (tails, heads). In other words, return $D(2k)$ where $k$ is the index at which the loop was terminated.

A simplistic way to make an unbiased die from a biased one is to use the coin flip unbiasing method to build a fair coin, and build a fair die with rejection sampling, as in Unbiasing of sequences. But is this optimal (for generic values of the probability distribution)?

Specifically, my question is: what is an algorithm that requires the **smallest expected number of calls to the oracle**? If the set of reachable expected values is open, what is the lower bound and what is a class of algorithms that converges towards this lower bound?

In case different families of algorithms are optimal for different probability distributions, let's focus on almost-fair dice: I'm looking for an algorithm or a family of algorithms that's optimal for distributions such that $\forall i, \bigl|p\_i - 1/N\bigr| \lt \epsilon$ for some $\epsilon \gt 0$.

# Answer
The following paper answers a close variant of this question: The Efficient Construction of an Unbiased Random Sequence, Elias 1972.

The question there seems to be this: Given access to this biased independent source, output a *sequence* of random numbers in $\[1,N\]$ (note the difference from your question in which only one output symbol is requested). As the length of the desired output goes to infinity, the "efficiency" of the scheme in the paper (which seems like a natural generalization of von Neumann) goes to $1$, meaning, I believe, that an input with entropy $h$ is converted to an output of entropy approaching $h$.

The question seems much better behaved when phrased this way, rather than requesting a single output digit, because, for instance, if we draw $N$ samples and end up with an output with lots of information (for instance, all $N$ input symbols are distinct), then we can use *all* of that information to produce many output symbols, whereas with the question as phrased here, any information beyond that used to produce one output symbol goes to waste.

I believe that the scheme repeatedly takes $N$ draws, looks at the sequence, and maps it some outputs or the empty string. Perhaps there is a way to improve the scheme for your question by looking at prefixes and stopping if we have "enough" information to output a symbol? I don't know.
> 3 votes

# Answer
The method you describe for $N=2$ generalises. We use that all permutations of $\[1..N\]$ are equally likely even with a biased die (since the rolls are independent). Hence, we can keep rolling until we see such a permutation as the last $N$ rolls and output the last roll.

A general analysis is tricky; it is clear, however, that the expected number of rolls grows quickly in $N$ since the probability of seeing a permutation at any given step is small (and not independent of the steps before and after, hence tricky). It *is* greater than $0$ for fixed $N$, however, so the procedure terminates almost surely (i.e. with probability $1$).

For fixed $N$ we can construct a Markov chain over the set of Parikh-vectors that sum to $\leq N$, summarising the results of the last $N$ rolls, and determine the expected number of steps until we reach $(1,\dots,1)$ for the first time. This is sufficient since all permutations that share a Parikh-vector are equally likely; the chains and calculations are simpler this way.

Assume we are in state $v=(v\_1,\dots,v\_N)$ with $\sum\_{i=1}^n v\_i \leq N$. Then, the probability of *gaining* an element $i$ (i.e. the next roll is $i$) is always given by

$\qquad\displaystyle \operatorname{Pr}\[\text{gain } i\] = p\_i$.

On the other hand, the propability of *dropping* an element $i$ from the history is given by

$\qquad\displaystyle \operatorname{Pr}\_v\[\text{drop } i\] = \frac{v\_i}{N}$

whenever $\sum\_{i=1}^n v\_i = N$ (and $0$ otherwise) precisely because all permutations with Parikh-vector $v$ are equally likely. These probabilities are independent (since the rolls are independent), so we can compute the transition probabilities as follows:

$\qquad\begin{align\*} &\operatorname{Pr}\[v \to (v\_1,\dots,v\_j + 1,\dots,v\_N)\] \\ &\qquad=\begin{cases} \operatorname{Pr}\[\text{gain } j\] &, \sum v \< N \\ 0 &, \text{ else} \end{cases}\\;,\\\\[3ex\] &\operatorname{Pr}\[v \to (v\_1,\dots,v\_i - 1, \dots v\_j + 1,\dots,v\_N)\] \\ &\qquad=\begin{cases} 0 &, \sum v \< N \lor v\_i=0 \lor v\_j=N \\ \operatorname{Pr}\_v\[\text{drop } i\] \cdot \operatorname{Pr}\[\text{gain } j\] &, \text{ else} \end{cases}\\;\text{ and}\\\\[3ex\] &\operatorname{Pr}\[v \to v\] \\ &\qquad=\begin{cases} 0 &, \sum v \< N \\ \sum\_{v\_i \neq 0} \operatorname{Pr}\_v\[\text{drop } i\] \cdot \operatorname{Pr}\[\text{gain } i\] &, \text{ else} \end{cases}\\;; \end{align\*}$

all other transition probabilities are zero. The single absorbing state is $(1,\dots,1)$, the Parikh-vector of all permutations of $\[1..N\]$.

For $N=2$ the resulting Markov chain¹ is

\[source\]

with expected number of steps until absorption

$\qquad\displaystyle \mathbb{E}\\,\text{steps} = 2 p\_0 p\_1 \cdot 2 + \sum\_{i\geq 3} (p\_0^{i-1}p\_1 + p\_1^{i-1}p\_0)\cdot i = \frac{1 - p\_0 + p\_0^2}{p\_0-p\_0^2}\\;,$

using for simplification that $p\_1=1-p\_0$. If now, as suggested, $p\_0 = \frac{1}{2} \pm \epsilon$ for some $\epsilon \in \[0,\frac{1}{2})$, then

$\qquad\displaystyle \mathbb{E}\\,\text{steps} = \frac{3 + 4\epsilon^2}{1 - 4\epsilon^2}$.

For $N \leq 6$ and uniform distributions (the best case) I have performed the calculations with computer algebra²; since the state space explodes quickly, larger values are hard to evaluate. The results (rounded upwards) are

Plots show $\mathbb{E}\\,\text{steps}$ as a function of $N$; to the left a regular and to the right a logarithmic plot.

The growth seems to be exponential but the values are too small to give good estimates.

As for stability against perturbations of the $p\_i$ we can look at the situation for $N=3$:

Plot shows $\mathbb{E}\\,\text{steps}$ as a function of $p\_0$ and $p\_1$; naturally, $p\_2 = 1 - p\_0 - p\_1$.

Assuming similar pictures for larger $N$ (kernel crashes computing symbolic results even for $N=4$), the expected number of steps seems to be quite stable for all but the most extreme choices (almost all or none mass at some $p\_i$).

For comparison, simulating an $\epsilon$-biased coin (e.g. by assigning die results to $0$ and $1$ as evenly as possible), using this to simulate a fair coin and finally performing bit-wise rejection sampling requires at most

$\qquad\displaystyle 2\lceil \log N \rceil \cdot \frac{3 + 4\epsilon^2}{1 - 4\epsilon^2}$

die rolls in expectation -- you should probably stick with that.

---

1. Since the chain is absorbing in $(11)$ the edges hinted at in gray are never traversed and do not influence the calculations. I include them merely for completeness and illustrative purposes.
2. Implementation in Mathematica 10 (Notebook, Bare Source); sorry, it's what I know for these kinds of problems.
> 2 votes

# Answer
Just a quick comment regarding the case $N = 2$. Take some large number $m$, and sample $m$ throws of the die. If you got $k$ heads then you can extract $\log \binom{m}{k}$ bits. Assuming the die is $p$ biased, the average amount of information is $$ \sum\_{k=0}^m p^k (1-p)^{m-k} \binom{m}{k} \log \binom{m}{k} \approx m h(p).$$ To get this estimate, use the fact that the binomial variable is concentrated around $k = pm$ together with the estimate $\log \binom{m}{k} \approx mh(k/m)$. As $m$ gets larger, we obtain the optimal rate of $h(p)$ per coin throw (this is optimal for information-theoretic reasons, for example the asymptotic equipartition property).

You can use the same method for general $N$, and you will probably get the same $H(\vec{p})$. These algorithms are only optimal in the limit, and there might be algorithms reaching the limit faster than these. In fact, I neglected to compute the speed of convergence - it might be an interesting exercise.
> 1 votes

# Answer
I would hazard the following answer.

The specific case of 2 you mentioned above is the specific case of expanding $(p + q)^2$ (where $p$ is prob of head and $q$ prob of tail) which gives you a term $2pq$ This means you can get $pq $ for one case and $qp$ for the other case. You will need to repeat sampling until you see either $pq$ or $qp$ (head-tail or tail-head) Using them as simulation, you will give equal probability.

When $N=3$ you have the expansion $(p + q + r)^3$ which gives you the term $pqr$. In this case, you do the same thing, sampling until you see all 3 outcomes $q$, $p$, $r$ in some order in 3 consecutive trials.

The same thing apply for the general case. Thinking carefully, I have to say the case of 2 is the best case where one can work things out in the expansion. When $N=3$ there are 6 different sequences for $pqr$ and there are many other terms in the expansion. I would feel quite uncomfortable with other terms where there are many more outcomes.

.

## Extra:

This makes me think about the idea of simply sampling a lot to estimate the probability of each outcome of the dice. In this simplest case of one layer model with no hidden layer (a known model), we can work out a bound to conclude that the estimation converges quickly. In fact Chernoff bound shows us that the error goes down exponentially as sampling increases (linearly).

Now that a good estimation of the probabilities for each side of the dice is known, there are many options. One option is that we can do the expansion above again, but this time we can potentially use many other terms in the expansion that have the same value as $\prod\_{i=1}^{i=n} p\_i$ (or any term that you use as based sequence). This will be a bit more efficient because more terms in the expansion will be used. But I admit I don't know if this will result in the smallest number of calls to the oracle to have a guarantee on whatever preconditions (such as confidence parameter), if they are given.

Nevertheless, this approach is an answer to different flavor of the question. The question asks for guaranteed perfect unbiased-ness at the cost of potentially large sampling (though low prob). This approach only uses finite sampling with bound on confidence parameter. So I don't think this approach is appropriate to this question even though it is very interesting.
> 1 votes

---
Tags: probability-theory, randomized-algorithms, random-number-generator
---


# Question
Title: Are constituency grammars and dependency grammars two different types of context free grammars?
From http://en.wikipedia.org/wiki/Parse\_tree

> A concrete syntax tree or parse tree or parsing tree\[1\] or derivation tree is an ordered, rooted tree that represents the syntactic structure of a string according to some **context-free grammar**.
>
> Parse trees are usually constructed according to one of two competing relations, either in terms of the constituency relation of **constituency grammars (= phrase structure grammars)** or in terms of the dependency relation of **dependency grammars**.

1. Are constituency grammars and dependency grammars two different types of context free grammars?
2. I went through the wikipedia articles for constituency grammars and for dependency grammars, but they seem to discuss only for natural languages.

From the perspective of formal language and grammars, is it correct that constituency grammars and dependency grammars seem to be about semantics, which is not just syntax/formal any more?

Thanks.

# Answer
> 2 votes
Concrete syntax trees and derivation trees exist for many types of grammars (e.g. tree adjoining grammars, TAG). They happen to be identical (up to labeling) in the case of CF grammars, but this is not always the case, for example for TAG. (there are technical errors or imprecisions in Wikipedia).

The derivation tree expresses how the rules are to be applied to obtain the derived string. The derived tree (or concrete syntax) associate a tree structure to the generated string, which may not be context free.

Constituency grammars is a name often used by linguists to refer to what we call Context-Free Grammar. This is intended to contrast them with Dependency Grammars based on a linguistic concept of dependency used by linguists.

The idea of constituency is a classic idea in formal systems: terms are formed with subterms. So the parse tree (very approximately) may be seen as a term of an abstract algebra, and the semantics of the whole is a composition of the semantics of the parts, the constituents (I insist that I am simplifying a lot). While parse trees are concrete syntax trees, the idea of abstract syntax trees (AST) was to emphasize in programming languages the algebraic term structure to better organize compilers and formal semantics.

Nevertheless, constituency is a syntactic concept, a very common one.

It has been extended to formalisms that consider discontinuous constituents (or multi-parts constituents), such as TAG and Linear Context-Free Rewriting Systems (LCFRS), which are strictly more powerful than CF grammars.

As far as I understand, the idea of dependency is related to lexicalized grammars (which also exists for extensions of CF grammars).

The idea of a lexicalized grammar is that every rule instance used in a derivation must be associated with a terminal of the generated string (usually a single one). As is well known, every CF language has a lexicalized CF grammar: you just put it in Greibach normal form. Actually, the research of Sheila Greibach was probably motivated by natural language considerations (she was working in the NL group of Anthony Oettinger at Harvard). This concept of lexicalisation comes from some natural language (NL) theories that consider that construction of sentences is lexicon driven.

So far, we are still in the CF realm.

Dependency Grammar (DG), as much as I understand it as I am no specialist, organizes the tree structure around the idea that each node of the syntax tree is associated with a terminal (lexical element), as in lexicalized grammar, but in such a way that it "controls" (dominates in the tree structure) some part of the sentence, of which it is supposed to be the central element (the exact term is "*head*"). So the verb will be the head of a sentence, and the noun the head of the noun part of the sentence, etc., according to some linguistic theory the linguist is developing to organize language structure..

It is quite characteristic that the wikipedia article on Dependency Grammars does not propose a formal definition of the concept. My feeling from a quick glance at the literature is that it is mostly a linguistic concept that can be formally dressed in different ways, without a standard reference one. There are, however, some formal definitions, for example in *Dependency Grammars and Context-Free Grammars*, by Steven Abney (unpublished, 1994). I have also seen contradictory statements regarding the power of DG, but it apparently at best weakly equivalent to CFG. Specific algorithms have been developed for dependency parsing, that seems to have interest for linguists.

A dissertation (for sale) may contain interesting material: *Dependency Structures and Lexicalized Grammars*: An Algebraic Approach\*, Marco Kuhlmann, Springer 2010. Slides about it are available.

Closely related to Dependency Grammar are Link Grammars, formally defined, which also seem to have been designed for their parsing properties, though advantages over CF grammars seem disputed. Link Grammars are weakly equivalent to CF grammars, according to their creators, Daniel Sleator and Davy Temperley.

But Dependency Grammars, or Link Grammars, though they may define the same languages as all or part of the CF grammars, are not CF grammars, and do not define the same structures for the strings.

It is worth noting also the Head Grammars, which are non-CF constituency grammar, though they emphasize the concept of *head* more often encountered with the dependency analysis of language. Head grammars are LCFRS.

I believe semantics considerations enter the concept of Dependency Grammars, but there in no clearcut limit between syntax and semantics in Natural Language.

Constituency grammars are often just our good old, syntactic, formally defined, context-free grammars, though it has been entended to more complex structures for constituants.

# Answer
> 2 votes
First I admit that I only know enough so I can navigate in this field. One can say that I am at a level above beginner, but not an expert (adept is perhaps the best word)

I would hazard an answer for your questions.

1. Constituency grammar is simply syntactic grammar that is about parsing parts of a full context free grammar tree. Dependency grammar is not really about syntactic. I would not say dependency grammar is just context free.
2. Yes dependency grammar is really about semantic of the sentence when you talk in linguistic context. Syntactic grammar does not care about semantic, it cares about whether a sentence conforms to a set of rules and thus belong to a language. The semantic that one can derive from syntactic parsed tree is simply a corollary.

Here, this is important, it is well known that given a set of grammatical rules for context free grammar (constituency grammar), one can parse a sentence if it is in the language in polynomial time. CKY parses in $O(n^2)$ where $n$ is the size of the sentence. This running time is exponential on the size of the grammar, but if you are given a grammar before hand, this is considered only a constant.

For dependency grammar, in its generic form, I am quite certain you cannot guarantee a polynomial time parser given a set of grammar rules. The problem will become exponentially hard because the edges of the graph can point back and forth, you can forget about doing it the dynamic programming way.

In practice, this is not much of a problem because in the domain where one can use dependency grammar is linguistic. In this domain, the grammar has set of rules that would massively reduce the complexity of parsing natural language sentence. If not then over the course of thousand years, society would change it so that things are 'understandable'.

The most interesting part about dependency grammar is that its purpose, unlike formal language in theory of computation, is not about deciding whether a sentence is in the language or not. The purpose is about 'guessing' a semantic structure that would generate the given sentence.

---
Tags: formal-languages, formal-grammars, parsers, parsing
---


# Question
Title: Propagating node labels upwards in a tree
I am trying to think of an efficient way to synchronize a tree's nodes with the following rules.

Consider for instance this tree:

so the top of the heap is always `B` which can have many leaf-type nodes called `G`, or children which are node themselves called `S`, which can have leaves as well (`G`)

it is possible in the future that each `G` will have many leaves, but I assume the algorithm will be the same

So each `G` has a list of `categories`, that I want to syncronize (add and remove) with their parents.

so if `g1` has categories `[a,b,c]` then `B` will have `[a,b,c]`, but if `g2` has categories `[a,g,w]` `B` will have `[a,b,c,g,w]` (all the categories of its children)

if the `S` nodes' leaves have categories it goes the same, each `G` of an `S` node will have categories that will propagate to their parent (which will get all the categories of its children) and in return will propagate the categories up to `B`, and `B` will have a union of all categories below it.

if any of the `G` leaves changes categories, or if the a `G` is added or an `S` is added the entire tree/heap need to syncronize according the new categories added.

I need the categories to be syncronized when added or removed. So every time a category is added I need the parent to get the categories of its children, which sort of scan the whole tree again

Is there an efficient way to do this?

# Answer
I understand your problem as follows (the best I could make of your presentation of it).

You have a tree rooted in node B. Each leaf is labeled wih *categories*. Each other node is labeled with the categories of all leaves below that node. The problem is to maintain proper labeling of all nodes, when changing the labels of leaves or adding or removing nodes from the tree.

The problem is easy when categories are added. You only have to propagate new categories from where they are added up to the root. The addition can come from adding a category to a leaf, or adding a new node with its own categories as a leaf, or with the categories of its daughters if it is an intermediate node.

The difficulty comes from removing categories, either by removing them from a leaf, or by removing a node and all the nodes below it. The difficulty comes from the fact that the categories it propagated upward may still have to be kept somewhere on the path, because they are provided by some other nodes.

However, this can be addressed very simply. Just keep a count of how many times a category is provided to a node from the leafs below that node. Then both addition and removal require only a bit of accounting. You remove a category from the labeling of a node when its count falls to zero for that node.

*Time complexity*

The complexity analysis below is added by an edit from Billiska. It can only be partial since the OP did not clearly state how the structure is to be used. In particular, it seems that he also intends to add or remove whole subtrees. But the information needed for the purpose is available from the root of the subtrees (assuming categories have been propagated beforehand in subtrees to be added), so that operating on whole subtrees is very similar to operating on leaves.

Let the tree have depth of $d$.

**Look-up** category of a given node is $O(1)$ since the category information is always stored up-to-date for each node.

**Add a category** to a given leaf node is $O(d)$ since the *count* of that category has to be incremented for every ancestor node up to the root.

**Remove a category** from a given leaf node is $O(d)$. Just the revert of add, we decrements the *count* of that category for every ancestor node up to the root.
> 5 votes

---
Tags: algorithms, trees
---


# Question
Title: Finding all partitions of a set s.t. each block contains exactly one subset from a given set of subsets - how hopeless?
Hello and apologies if my question will be too elementary. My background is from arithmetic geometry, but I have been recently faced with certain computational problems of combinatorial nature, where I feel way out of my league, so I will definitely appreciate some clarity on the matter :)

Long story short, I am faced with the following type of a problem, which I would like to illustrate here with an example for the sake of better clarity:

Let $S:=\\{1,2,...,42\\}$ be a set of integers and let $N\subset\\{T\in 2^S:|T|=3\\}$ be fixed (pre-generated in a specific way). Typically, $|N|$ is in the order of 1500-2000. I would like to construct all 7-el. partitions $\Sigma=\\{S\_1,S\_2,S\_3,S\_4,S\_5,S\_6,S\_7\\}$ of $S$ (i.e.$S\_i\neq\emptyset$ for $i=1,...,7$ and $\cup\_i S\_i=S$) **s.t. $|S\_i|=6$ and $S\_i$ contains exactly one element of $N$ as a subset, $i=1,...,7$. (\*)**

My question is, is this computationally feasible (e.g. a few days of number crunching on a modern workstation) by using an optimized routine/algorithm? And if yes, how?

In the particular example from above, a straightforward approach to obtain all 6-el. subsets of $S$ that contain exactly one element of $N$ as a subset yielded ~ 470 000 different subsets (also see this SO thread), which does not seem aproachable by a straightforward solution of the exact cover problem. Furthermore, in another example with $|S|=48$ and $|\Sigma|=8$, it yielded ~1.5 Mil different subsets.

Note that constructing all partitions, even with fixed block size, for sets with as many elements is kinda out of reach (cfg. Bell number or Stirling number of the 2nd kind). However, conjecturally, because of the specific nature of $N$ and the additional restriction on the blocks of the partition, it is expected that there are only very few such valid partitions (probably no more than 1 or 2). **In other words, I am hoping that imposing the additional restriction (\*) could be still used to obtain a suitable algorithm.**

Since the underlying math for a potential proof or disproof may well be out of reach for now, I am hoping to at least get some computational verification for "larger" numbers before even attempting an attack on the mathematical part.

Thanks!

# Answer
> 2 votes
Here's an approach that I suspect will work very quickly.

I suggest you start by enumerating all possible values for an $S\_i$, i.e., all possible 6-element subsets of $S$ that contain exactly one element of $N$ as a subset.

How many such sets do you expect to find? By a crude back-of-the-envelope estimate, I estimate there will be only a handful, maybe 10 of them are so. This estimate might be wrong, but this would be easy for you to test.

Let $\alpha$ be the number of possible such sets (i.e., $\alpha$ counts the number of ways to choose a 6-element subset of $S$ that contains exactly one element of $N$, i.e., there are $\alpha$ possible values for each $S\_i$). I am predicting you'll find $\alpha \approx 10$, or something similarly small.

If this prediction is accurate, this suggests a simple, naive algorithm to enumerate the partitions: namely, enumerate all ${\alpha \choose 5}$ ways to choose five valid possibilities for the $S\_i$, and check whether those five sets forms a partition. The running time of this algorithm is $O(\alpha^5)$. If $\alpha$ is very small, say $\alpha=10$, this will be plenty efficient.

If it turns out that $\alpha$ is a bit larger, you can optimize this naive algorithm a bit. Enumerate all ${\alpha \choose 2}$ ways to choose two out of these $\alpha$ 6-element sets, say $S\_4,S\_5$. Filter out pairs that have an overlap (i.e., an element of $S$ in common). Now store them in a hashtable, keyed by $S\_4 \cup S\_5$. The hashtable will contain $O(\alpha^2)$ entries and can be constructed in $O(\alpha^2)$ time. Next, enumerate all ${\alpha \choose 3}$ ways to choose $S\_1,S\_2,S\_3$. If $S\_1,S\_2,S\_3$ are pairwise disjoint, look up $S \setminus (S\_1 \cup S\_2 \cup S\_3)$ in the hashtable to see whether there is pair $S\_4,S\_5$ that can be combined with $S\_1,S\_2,S\_3$ to form a full partition of $S$. The running time of this optimized algorithm will be $O(\alpha^3)$.

And note that if $\alpha$ is indeed small, say $\alpha=10$ as I'm predicting, then it will be easy to enumerate all $\alpha$ possible values for an $S\_i$. You just enumerate all possible elements of $N$, then try extending each with three more elements of $S$, one by one, testing each one to make sure that the resulting set does not contain any other element of $N$ as a subset. (In other words: select an element $T$ of $N$; select an element $x$ of $S \ T$, and check that $T \cup \\{x\\}$ does not contain any other element of $N$ as a subset; select an element $y$ of $S \setminus (T \cup \\{x\\})$, and check that $T \cup \\{x,y\\}$ does not contain any other element of $N$ as a subset; select an element $z$ of $S \setminus (T \cup \\{x,y\\})$, and check that $T \cup \\{x,y,z\\}$ does not contain any other element of $N$ as a subset. Each step is pretty easy to do, and the overall running time should be very fast, assuming that $\alpha$ is indeed small as I expect.)

So, I suggest you start by running a little experiment to measure $\alpha$, then see if any of these algorithms is fast enough. If it's not, edit your question to provide more details, including the value of $\alpha$.

---

Why do I estimate that $\alpha$ might be about 10? Here's my crude back-of-the-envelope calculation.

First off, there are ${30 \choose 6} \approx 2^{19}$ ways to choose a 6-element subset of $S$, and ${30 \choose 3} \approx 2^{12}$ ways to choose a 3-element subset of $S$. Therefore, $N$ contains about half of the possible 3-element subsets of $S$: in other words, if we pick a random 3-element subset of $S$, it'll be in $N$ with probability about 50% (roughly).

Also, for any 6-element subset $S\_i$ of $S$, there are ${6 \choose 3} = 20$ ways to choose a 3-element subset of $S\_i$, and each one has about a 50% chance of being an element of $N$. We want there to be exactly one 3-element subset of $S\_i$ that is in $N$. This is like doing 20 coin flips, and we want to get exactly one heads (and the rest tails). The probability of that is ${20 \choose 1} \times 2^{-20}$, i.e., $20/2^{20}$. So, if we pick a 6-element subset of $S$, it will have probability about $20/2^{20}$ of being a valid possible value for some $S\_i$.

Finally, there are $2^{19}$ possible 6-element subsets. So, we expect that about $2^{19} \times 20/2^{20} = 10$ of them will be a valid possible value for $S\_i$. So, I'd expect $\alpha \approx 10$, using this crude argument.

This is a very crude estimate, because it assumes everything behaves randomly. It is not rigorous, both because your set $N$ might not be random; and also because I made independence assumptions all over the place, even though things are not independent. So, you will need to check empirically whether this estimate turns out to be accurate or not -- fortunately, that should be pretty easy to do.

---
Tags: algorithms, combinatorics, efficiency, partitions
---


title: How can I prepare for CS in university

text:
# Question
Title: How can I prepare for CS in university
How can I prepare for an introductory CS college course?

I am currently in Grade 12 and next year I will be studying Computer Science at a university in South Africa (syllabus is here). However CS has a very high dropout rate here in South Africa, more than any other course, and I'm nervous because of that. My experience with programming is limited to Java in the Net beans environment. I understand the basics of programming (loops, arrays, methods and classes, reading and understanding other languages, etc).

My question is how can I be more prepared? I'm willing to learn new languages or take online courses or anything that can help me next year.

# Answer
> 3 votes
A lot of the other answers seem to be pointing in the right direction and get to the gist of things. I will give you a more pointed and concrete answer since I think it will be useful.

---

In my opinion, you are best served learning a bit of **discrete maths** and **logic**. The courses in the syllabus appear to either assume you know it or might skim over it when needed. A lot of CS students have a hard time with these topics. I have seen a good number of "elite" programmers entering university that hit a wall, here. On the other hand, I have seen others sail right through without an issue. I don't know anything about the high dropout rate in CS within South Africa, but difficulty getting past the discrete maths material does weed people out.

The primary goal is to learn how to think analytically and problem solve. I think this material is one of the best approaches to going about this.

Checklist of Topics:

* Combinatorics (Counting principles)
* Formal Logic (aka Boolean Logic)
* Basic Set Theory/Algebra
* Theorems and Proofs (Proofs by contradiction, Proofs by induction)
* Graph Theory

Since your goal is preparation, you probably only need to focus on the basics. By this, I mean focus specifically on the easy, introductory material. You're looking for a strong conceptual framework concerning how to think.

---

**Materials:**

Textbook: Discrete Mathematics Lecture Notes \ \ This is just a decent set of lecture notes I found online. Googling around might help you find others.

Video Lectures for Discrete Maths: Are there any good Discrete Mathematics video online? \ \ (I really like the Arsdigita stuff)

---

# Answer
> 7 votes
I'm not well aware of study pattern in your region, but I can advise you according to my own experience of 6 years in this field. I am in post graduation course. One of the many things you need to know is CS is not all about programming, although most of the concepts you can relate to it and easily understand. Most importantly, its useless to learn every language, but mastery in any one language would be very helpful. Slowly you'll start understanding that all you need to understand is declaring variables, loops, functions and some built-in or library functions for a language, and it'll do most of your basic work.

Secondly, theory alone is of little use, except in the field of algorithms. From programming to digital and networking, you need to understand the practical examples. You need to start from "How will I do this?" then go for "what are the problems in my ways?" and then you'll almost always end up with adopting standard ways of doing things, this methodology will give you a lot of help.

Nothing is too difficult if you work hard and follow right approach. Computer science is a field where either you'll understand things or you won't. There is little to no use of understanding half things. You can't know half algo. You can't know OSI architecture upto 3 layers. You'll forget things if you do them that way. But once you have struggled enough, things would start relating so nicely that you'll easily be able to forecast solutions to a problem in one subject due to your experiences from other subjects.

My advice would be to go for the course if there is some curiosity in you when you think how facebook works? How Windows work? How am I connected? Why is everything 0 or 1? WHAT is 0 and 1? All the best.

# Answer
> 0 votes
HristoM, I've read your syllabus, and as I can see, you will study mathematical courses. Therefore, it's necessary to be familiar with logic: you have to be able to construct correct reasoning and to evaluate it's correctness. I think, it's much more useful to study in university than knowledge of various programming languages. So, the best way to study logic is to prove mathematical statements.

# Answer
> 0 votes
For computer science, one thing is very important, Maths. Computer science is not just programming, it provides solutions to complex problems by using algorithms, maths, data structures and design patterns. The more strong you are in problem solving, the more you will be good in CS.

Making your maths strong in practical problem solving will help you during your CS study, but please note that you have to understand Maths and you should apply it to real world problems so that you get command on problem solving. If you are not good in Maths, then i think you should consider another course. And never try to force yourself to play with Maths if you are not naturally good in it, as understanding Maths and Programming are God gifted, not human developed :)

# Answer
> 0 votes
I think a good starting point would be reading a book about theoretical computer science as it teaches you to think in structures and formalisms, which are the cornerstones of computer science.

Have a look at Sipser's book. Read the book slowly from cover to cover and try to understand every definition, theorem, and proof (May take some time).

---
Tags: education
---


# Question
Title: What does the processor do while waiting for a main memory fetch
Assuming l1 and l2 cache requests result in a miss, does the processor stall until main memory has been accessed?

I heard about the idea of switching to another thread, if so what is used to wake up the stalled thread?

# Answer
Memory latency is one of the fundamental problems studied in computer architecture research.

## Speculative Execution

Speculative execution with out-of-order instruction issue is often able to find useful work to do to fill the latency during an L1 cache hit, but usually runs out of useful work after 10 or 20 cycles or so. There have been several attempts to increase the amount of work that can be done during a long-latency miss. One idea was to try to do value prediction (Lipasti, Wilkerson and Shen, (ASPLOS-VII):138-147, 1996). This idea was very fashionable in academic architecture research circles for a while but seems not to work in practice. A last-gasp attempt to save value prediction from the dustbin of history was runahead execution (Mutlu, Stark, Wilkerson, and Patt (HPCA-9):129, 2003). In runahead execution you recognize that your value predictions are going to be wrong, but speculatively execute *anyway* and then throw out all the work based on the prediction, on the theory that you'll at least start some prefetches for what would otherwise be L2 cache misses. It turns out that runahead wastes so much energy that it just isn't worth it.

A final approach in this vein which may be getting some traction in industry involves creating enormously long reorder buffers. Instructions are executed speculatively based on branch prediction, but no value prediction is done. Instead all the instructions that are dependent on a long-latency load miss sit and wait in the reorder buffer. But since the reorder buffer is so large you can keep fetching instructions *if* the branch predictor is doing a decent job you will sometimes be able to find useful work much later in the instruction stream. An influential research paper in this area was Continual Flow Pipelines (Srinivasan, Rajwar, Akkary, Gandhi, and Upton (ASPLOS-XI):107-119, 2004). (Despite the fact that the authors are all from Intel, I believe the idea got more traction at AMD.)

## Multi-threading

Using multiple threads for latency tolerance has a much longer history, with much greater success in industry. All the successful versions use hardware support for multithreading. The simplest (and most successful) version of this is what is often called FGMT (*fine grained multi-threading*) or *interleaved multi-threading*. Each hardware core supports multiple thread contexts (a *context* is essentially the register state, including registers like the instruction pointer and any implicit flags registers). In a fine-grained multi-threading processor each thread is processed *in*-order. The processor keeps track of which threads are stalled on a long-latency load miss and which are ready for their next instruction and it uses a simple FIFO scheduling strategy on each cycle to choose which ready thread to execute that cycle. An early example of this on a large scale was Burton Smith's HEP processors (Burton Smith went on to architect the Tera supercomputer, which was also a fine-grained multi-threading processor). But the idea goes much further back, into the 1960s, I think.

FGMT is particularly effective on streaming workloads. All modern GPUs (graphics processing units) are multicore where each core is FGMT, and the concept is also widely used in other computing domains. Sun's T1 was also multicore FMGT, and so is Intel's Xeon Phi (the processor that is often still called "MIC" and used to be called "Larabee").

The idea of Simultaneous Multithreading (Tullsen, Eggers, and Levy, (ISCA-22):392-403, 1995) combines hardware multi-threading with speculative execution. The processor has multiple thread contexts, but each thread is executed speculatively and out-of-order. A more sophisticated scheduler can then use various heuristics to fetch from the thread that is most likely to have useful work (Malik, Agarwal, Dhar, and Frank, (HPCA-14:50-61), 2008). A certain large semiconductor company started using the term *hyperthreading* for simultaneous multithreading, and that name seems to be the one most widely used these days.

## Low-level microarchitectural concerns

I realized after rereading your comments that you are also interested in the signalling that goes on between processor and memory. Modern caches usually allow multiple misses to be simultaneously outstanding. This is called a Lockup-free cache (Kroft, (ISCA-8):81-87, 1981). (But the paper is hard to find online, and somewhat hard to read. Short answer: there's a lot of book-keeping but you just deal with it. The hardware book-keeping structure is called a MSHR (miss information/status holding register), which is the name Kroft gave it in his 1981 paper.)
> 30 votes

# Answer
The short answer is: nothing, the processor stalls.

There aren't so many possibilities. Switching to a different task isn't really an option for two reasons. That's an expensive operation, and since the current task and other task are competing for space in the cache, switching to the other task may itself require a main memory access, and so may switching back to the original task. Furthermore, this would have to involving the operating system, so the processor would have to trigger some form of interrupt or trap — in fact the processor would be switching to some kernel code.

While the processor is stalled, the timer continues to run, so there could be a timer interrupt, or there could be an interrupt from other peripherals. So a context switch is more likely to happen during a main memory access than during a cache access, but only because it takes longer.

Nonetheless modern computers do include a variety of techniques to try to reduce the time wasted in the processor waiting for main memory. Stalling does happen, but only when it couldn't be avoided.

One technique is **speculative fetches**: the processor tries to guess which memory location will be accessed, and fetches it to cache ahead of time. For example, loops over a memory block are common, so if cache lines have been loaded for memory addresses 0x12340000, 0x12340010 and 0x12340020, it might be a good idea to load the line for 0x12340030. The compiler can help by generating prefetch instructions which are like loads except that they only transfer data from main memory to the cache, not into a processor register.

Another technique is **speculative execution**. The processor starts executing the next instruction before the load is performed. This happens naturally anyway because of the pipelining of instructions. Only instructions that don't depend on the loaded value can be executed this way: the processor must perform a dependency analysis. For conditional instructions (e.g. load r1; branch if r1 ≠ 0), processors employ branch prediction heuristics to guess what the value will be. Speculative execution after a load can need to be rewound in case the load triggers an abort.

Some architectures such as Itanium facilitate the execution of instructions in a convenient order by allowing instruction reordering by default: instead of consisting of a sequence of elementary instructions that are semantically executed one after another, programs consists of very long instruction words: a single instruction includes many operations that are to be executed in parallel by different components of the processor.

Switching to another thread happens in **hyperthreading**, found on high-end x86 processors. This is a hardware design technique: each processor core contains two separate register banks (each corresponding to a task context), but a single instance of other elements, so that it can support two independent execution threads, but only effectively execute instructions from one at a time. While one thread is stalled, the other thread proceeds. From the point of view of the software, there are two independent processors; it just happens that those processors share many components under the hood.

Swap is one more level on the memory cache hierarchy: the main memory can be seen as a cache for swap space. With swapping, the mechanisms and the performance ratios are different. If a task needs data to be loaded from swap, the load instruction triggers a trap which executes kernel code to allocate a page in RAM and load its content from disk. While this happens, the kernel may well decide to switch to another task.
> 16 votes

# Answer
The answer to this question will vary with the architecture in question. While many CPUs will stall (ARM, x86 w/o hyperthreading, etc.) because it takes them too long to switch threads, that's not the approach taken by every architecture. In some architectures, each thread scheduled on a CPU has its own independent register file, so the processor may simply execute work from a thread that is not waiting on a memory access. It is my understanding that this is, to a limited extent, what x86 hyperthreading does (using just 2 threads,) but it's far more common on GPGPU architectures. In the particular case of CUDA, at least dozens, if not hundreds, of warps of threads are usually loaded on a given multiprocessor at any given time, with each thread (hundreds or thousands of them) having its own registers. This allows the architecture to execute an instruction from another thread on the very next cycle when a given thread issues a memory access. So, as long as sufficiently many threads are loaded, the processor cores never idle for memory accesses. See the Performance Guidelines and Memory Hierarchy for more information.
> 5 votes

---
Tags: computer-architecture, cpu-cache, cpu-pipelines
---


# Question
Title: Which article in front of O(.), Ω(.), ...?
Writing a survey, I am confronted to a very difficult and -- I dare say -- deep issue: I have many sentences mentioning or stating results of the form *"a $\Omega(\sqrt{n})$ lower bound"*, or *"a $O(\sqrt{n}/\varepsilon^2)$ algorithm"*. And I am struggling to decide whether I should use "a" or "an" in front of these: is there a consensus/precedent?

(in hindsight, this may not be the best place to raise such profound questions; I was just unable to find any better one)

# Answer
Write it as you pronounce it: "an omega". Or, especially when it can be pronounced with a vowel or consonant, rephrase to avoid the issue: "a bound of..."
> 3 votes

---
Tags: terminology, asymptotics, landau-notation
---


title: Convolution of Haar filter

text:
# Question
Title: Convolution of Haar filter
In "Conceptual Wavelets" (2009) by D. Lee Fugal, on pg 47 he writes

```
Conv ([-1, 1], [1, 1]) = [-1, 2,-1]

```

When I do it I get

```
0    -1    1    0
1     1                           > -1
       1.   1.                   > 0
             1     1.            > 1

```

So I get \[-1, 0, 1\]. What am I not understanding?

The definition Fugal is using is the Matlab function conv which I assume is just traditional convolution....

# Answer
> 2 votes
If the book is really using Matlab's `conv` then it must be a typo.

Bring up Matlab and try it. (Or if you don't have Matlab then go to octave-online.net and try it.)

The Matlab definition of `conv` over finite sequences also agrees with your answer.

---
Tags: signal-processing
---


title: Direct NP-Complete proofs

text:
# Question
Title: Direct NP-Complete proofs
I'm just starting to learn about NP-completeness. While I understand that reducibility plays a key role in this, I'm astonished how few problems I've been able to find who's proof that they are NP-Complete is **not** based on reduction to an existing NP-Complete problem.

While I understand these proofs are perfectly valid, you loose insight into what makes a particular problem difficult if you have to trace logic through 3, 4, 5+ reductions.

Since NP-Complete is, by definition, an equivalence class, I should be able to start with any of them; however I can only seem to find is this general strategy.

Are there any other problems with direct proofs that they are NP-Complete other than Circuit-SAT and SAT?

# Answer
At risk of sounding like I'm avoiding the question, I claim that every reduction *is* a direct proof of NP-completeness, just avoiding a lot of tedious, unnecessary work.

First, let me talk a little about the proof of the Cook-Levin theorem (SAT np-completeness).

At a very high level, the cook-levin theorem proof does this:

Assume R is some problem in NP. Then, by definition, there is a nondeterministic TM $T$ that runs in $p(n)$ time and decides $R$, for $p(n)$ a polynomial.

Then, it is sufficient to show that for any $x$, we can construct in polytime a boolean formula $B$ such that $B$ is satisfiable if and only if $T$ accepts $x$ (within $p(|x|)$ steps, by assumption of $T$).

Finally, by taking the formal definition of a nondeterministic turing machine and translating it into the language of a SAT instance, we construct a formula that is true only if $T$ accepts $x$ within $p(|x|)$ steps. This is a tedious and difficult process, which you can read about here http://en.wikipedia.org/wiki/Cook%E2%80%93Levin\_theorem#Proof

Anyways, the point of this explanation is the last paragraph: notably, that the only nontrivial part of this proof is taking the parts of a NTM and putting it in the language of a SAT instance. But, this is essentially what a reduction is!

For example, when you write a reduction from SAT to 3-coloring, what you are showing is that a SAT instance can be translated into a 3-coloring instance -- and this gives you a direct proof of np-completeness, because we already have a translation from a p(n) time NTM into a SAT instance.

So, cook-levin tells us how to make boolean formulas from an NTM, and a 3-coloring reduction tells us how to make vertices and edges from boolean formulas. Put these together, and you get a direct translation from an NTM into vertices and edges, which is exactly what you're looking for. It just happens to be tedious to deal with all the annoying little pieces of the NTM formalism, so no one likes to deal with that. It's much easier to do a reduction from SAT than a 'reduction' from NTM.
> 11 votes

# Answer
Fagin's proof that model checking existential second-order logic is **NP**-complete is a direct reduction from an arbitrary **NP** Turing machine, very much like the SAT proof.
> 3 votes

---
Tags: complexity-theory, reference-request, np-complete, proof-techniques
---


title: Language for teaching basic programming

text:
# Question
Title: Language for teaching basic programming
I'm interesting in teaching programming to middle school students. I'd like a programming language with the following criteria:

1. *Simple* \- pared down to the absolute minimum needed to support sophisticated programming without too much code. As such, for this language, I'm not interested in pointers and am weary of object-orientation (although functions are good).
2. *Powerful* \- I'd like to be able to program 21st-century elements, including graphics, networking, and distributed processing.
3. *Debuggable* \- I'd like an elegant Integrated Development Environment with a human-readable debugger (i.e. not some strange error message with a stack trace, but a clear explanation that an average middle school student can use to determine what is wrong with the code).

The standard programming languages (C,C++,C#,Java) fail the first criterion. Basic programming languages like Scratch fail the second (and possibly third) criterion. Scripting languages (perl, python, php) fail the last criterion.

I'd like to know if someone knows of such a beast, before I sit down to make it up myself.

# Answer
> 4 votes
I recommend Javascipt.

* Just about everyone reading this has access to a development environment by default in their browser.
* It's forgiving for new programmers.
* It supports a modern feature set.
* There's a *vast* repository of sample code on the internet, quality notwithstanding
* It's a real-world applicable language.

# Answer
> 8 votes
You should perhaps look into Racket (formally known as Scheme, a derivation of Lisp). It's the language taught to first year CS students at my University. Since it's a functional programming language, the syntax and concepts are quite simple compared to C/C++, there are several libraries that can do some basic drawing or networking related things, and Dr. Racket as several debugging features... including a Stepper (i.e it will show and perform one substitution at a time when you click the "next" button). I think that it may be worth looking into: http://racket-lang.org/. It has several other features that you may like, such as teaching modules (beginner, intermediate, advanced, full student levels) and pretty good documentation and examples. The book: How To Design Program (http://www.htdp.org) is a great teaching reference for this language which has a few nice examples using some of the libraries I mentioned above.

# Answer
> 3 votes
If you decide Python might work for you, I would take a look at the Jython Environment for Students (JES). There are some nifty debugging tools including a "watcher" that lets you choose variables to watch. You can control the steps or let it go quickly. I have used this IDE with middle-school-aged learners in a summer program successfully, but I also use this in an introductory course at the University level. The media computation libraries are fun, too. Students in my courses have enjoyed editing pictures and sounds. There is support for making animations too.

I have not used it for networking and distributed processing. There are examples in the Media Computation textbook by Guzdial and Ericson for topics like databases and functional programming, including higher-order procedures. You can do regular Python things in JES, but it has extra support for media things.

# Answer
> 2 votes
Python is a "almost pseudocode" language that is powerful enough to do "real" programming (most of the administrative tools in e.g. Fedora Linux are written in Python), it has simple to use extensions for graphics/graphical interfaces, it can handle large numerical problems (people use NumPy for this), much web programming is done in it, several programs use it as extension language. There is an extensive library, and many larger systems written in/for it. So it is not a toy language, learning it is useful later on.

Look at it's homepage, there are mature implementations available for almost any platform you might care for. It is free (not just zero cost). There is extensive documentation available, a Google search for "python tutorial" gives millions of hits. A hands-on web tutorial is Learn Python. For an introductory programming course using Python, consider Downey's Think Python.

# Answer
> 1 votes
you exclude scratch developed by MIT which seems to roughly fulfill some of the criteria. anyway here are two newer languages that are worth some consideration.

* Go by google. designed for fast compilation. here are the design goals
* Swift by Apple for mobile development. designed to be a less complex alternative to Apple's Objective C.
* node.js is newer & basically designed to expand the capabilities of Javascript to the server side & include networking capabilities.

# Answer
> 1 votes
You should probably use Visual Basic. It is simple, you can easily make the contacts list application along with some simple GUI games. You can also debug it. If your school is willing to dish out the dough you can get a dreamspark subscription. I think it will hold the students' attention.

# Answer
> 0 votes
Have you looked at Newspeak? Newspeak is a modern variant of Smalltalk. So yes, it's object oriented, but in the Alan Kay sense rather than the Simula 67 sense.

Having said that, if I were teaching programming to the middle school, I would ditch the debugger requirement and teach something more like Haskell.

---
Tags: programming-languages, education
---


# Question
Title: match an array with a given set of arrays
We have a set of 24 distinct arrays, each array has 36 elements and each element can have one of 13 possible values.

Then we're given an array X (this array is certainly part of our set) and we have to find to which array of our set it corresponds to.

Of course, we can check all 36 elements of X against each of 36 elements of our 24 arrays and find out with which it corresponds to.

I'm trying to reduce this number of 36 comparisons.

My naive approach is something like this:

* Take all possible subsets of 0..35, except the empty subset. Each of this subsets denotes which elements we should compare.
* Use each of this subsets with input all the 24 arrays of our given set and check which of these subsets produce as output the given set of our 24 arrays, these are valid subsets.
* From these valid subsets, the one with the fewer elements is our solution.

Unfortunately, all possible subsets of 0..35 excluding the empty subset is $2^{36}-1$

I was wondering if there could be another approach to the problem.

Many different arrays X will be matched against the given set of 24 arrays so any preprocessing of the 24 arrays is really worth the effort.

User JarkkoL suggested to precompute CRC32 of the set of the given arrays and then compare with the CRC32 of the array X.

Still, I'm wondering if there's a smart way not to calculate CRC32 for the whole array. I'm looking for the smallest possible number of elements for which I should compute it.

# Answer
> 1 votes
Let $s$ be the size of an array (36 in your example), $v$ the number of possible values (here 13) of each element, $n$ the numbers of reference arrays (here 24), i.e., the size of the set $S=\\{A\_i \mid i\in\[1..n\]\\}$ of arrays.

I am assuming that the cost for preprocessing the arrays does not matter. Else, you can alsways simplify the procedure below, as long as you do it well enough no to exceed the worst case time complexity $O(n)$.

Ideally you want to get a balanced binary tree of test for identification so that you get your answer in $\lceil \log\_2 n \rceil$ tests, i.e. 5 tests at most with the given figures. In other words, you are looking for 5 bits of information, that allow you to discriminate between your $n=24$ arrays.

For that you would need a criterion, testable in one comparison, that can cut approximately in two any given set of arrays, so that if $n\_1$ and $n\_2$ are the sizes of the 2 subsets, $\lfloor \log\_2 n\_1 \rfloor = \lfloor \log\_2 n\_2 \rfloor$.

However, that is not always possible. A worst case example is, when array $A\_i$ contains only $0$, except for element $A\_i\[i\]$ that contains $1$. Then the only way to identify $X$ in the reference set is to scan the elements of $X$ to find which has value $1$. This has complexity $O(n)$

So you you know complexity can be as bad as that, when an index will discriminate at best one array. Of cours, in general, you have to analyse the set of arrays to determine which indices you have to look at.

However, if the set of arrays permit, you can do better, as indicated above. For each index $i$ for the arrays, you try to identify a simple test $T\_i$ that will partition the set $S$ of arrays in two subsets $S\_1$ and $S\_2$ of nearly equal sizes: $n\_1$ and $n\_2$, such that $|n\_1-n\_2|$ is minimal (this is a bit stronger than the condition above, but the idea is to keep some slack on each half for future partitions). You do that for each index $i\in\[1..s\]$, and you keep the index $i\_0$ that gives the minimal difference $|n\_1-n\_2|$. Of course, you can stop as soon as you have a difference that is less than $2$, or possibly as soon as $\lfloor \log\_2 n\_1 \rfloor = \lfloor \log\_2 n\_2 \rfloor$ (the choice is purely heuristic). You can even stop earlier if you are not too worried about getting the fastest test tree.

Now for index $i\_0$ you have a test $T\_{i\_0}$ that partitions your set $S$ of arrays into two disjoint subsets $S\_1$ and $S\_2$ of respective sizes $n\_1$ and $n\_2$, on the basis of the values at index $i\_0$.

This will be the first test you apply to a new array $X$ to identify it in the set $S$. This test will tell you whether it is in $S\_1$ or $S\_2$. Then you know that your identification of X will take at most $1+\max(n\_1,n\_2)$ steps.

Then you pursue the construction of your balanced tree, on each of the two subsets $S\_1$ and $S\_2$, and with some luck you can approach the optimal complexity $O(\log\_2 n)$. No garantee given, since a bad set of arrays can impose the maximum complexity $O(n)$, with the forced reading of, on average, n/2 elements of $X$.

But there is still one very important detail that is missing. **What kind of test is to be used**. The answer is: any kind that is easy enough to count as one step. So I guess a primality test that partitions arrays into those with prime integer at index $i$ and those with non-prime at index $i$ is *not a good idea*.

Suggestions are: testing if the $A\_j\[i\]$ is equal to a given value, or whether it is greater than some value, or whether $A\_j\[i\] \mod p = r$ for two values $p$ and $r$. Just use your imagination, if there is a need for it. This can all be mechanized, tried automatically, but with a computation cost. What you should do depends on how much speeding up recognition by thorough preprocessing is essential for you.

## A faster solution for large values of $n$, assuming $v$ remains small.

Actually, though the worst case $O(n)$ cannot be improved, one can do better than the first solution I propose above, assuming $v$ remains small.

The idea is that one does not need to use binary tree. With more branching, one can get even faster to the answer.

For that purpose, we need to build a function $\phi$ that maps the $v$ values used into the integer range $\[1..v\]$. This can be done by hashing or by other means. Then *we can assume without loss of generality that the values used are the integer in $\[1..v\]$.*

Then one could find a minimal set $I$ of indices for the arrays, so that for any pair of arrays $A\_j$ and $A\_k$ there is an index $i\in I$ such that $A\_j\[i\] \neq A\_k\[i\]$. Then, for any array $X$ known to be equal to an array $A\_h\in S$, we can identify $A\_h$ by looking only at the values for the indices in $I$. One could then build a decision tree based on these indices considered in succession.

However, finding such a minimal set of indices may be difficult (I did not look into its complexity), and there may be better solutions, by using independent indices for the different nodes on a given level of the decision tree.

So we can probably get an even faster result by proceeding as follow. Choose a first index $i\_0$ such that the $p$ different values for that index partition the set $S$ of arrays into $p$ subsets $S\_x$ for $x\in \[1..p\]$. Depending on whether you try to reduce the average cost or the maximum cost, you may try to choose $i\_0$ so as to maximize $p$, or to minimize the maximum size of the subsets $S\_x$ (though this is heuristic). These $p$ subsets are the daughters of the root in the decision tree being built.

Then you repeat this operation for each subset, finding independently for each subset $S\_x$ a new index $i\_{x,1}$, so as to further partition the subset.

You repeat the operation until you reach the leaves which correspond to singleton sets, i.e., a specific array in $S$.

You get a widely branching decision tree, where each non-leaf node (actually corresponding to a subset of arrays) is labeled by an index, each branch is labeled by a value found for that index, and each leaf is labeled by an array in $S$. This tree must be implemented so that each branch can be accessed in one step by direct indexation.

Then, given an array $X$, you read its value at the index $i\_0$ labeling the root, and use this value as $\phi(X\[i\_0\])$ to access by indexation the next node in the tree. Then you repeat the step until you reach a leaf.

**When $v$ is large**, the algorithm has to be adapted by using a different function $\phi$ at each node.

# Answer
> 1 votes
You could calculate something like crc32 of the arrays and compare them with the crc32 of the new array. If the crc32's of the arrays match then you can do further check if the elements actually match (in case there is crc32 collision, which is very rare). If you know the new array exists in the set, you could select crc32 seed value which avoids the crc32 collisions, so once you find the crc32 match you can be sure it's the correct one without comparing the elements at all (just test max 24 ints). You could try something more lightweight than crc32 too if that's a performance issue.

If you would really want to push this, you could then sort the arrays by the checksum value and find the matching checksum with binary search, thus cutting the number of comparisons to log2(24)=5. Maybe not worth it for such a small amount of arrays though.

---
Tags: algorithms, arrays, equality
---


# Question
Title: Count of all simple paths between two vertices in a Complete graph
A path is simple if no vertices are repeated. How many simple paths exist between two vertices in a complete graph?

One way is listing all simple paths using depth-first search. but I think it should be more simple to find the number of all simple paths between 2 nodes in a complete graph.

Here is the same problem but mine is for a complete graph: Algorithm that finds the number of simple paths from $s$ to $t$ in $G$

# Answer
$c(1)=0,$

$c(n)=(n-2)\*c(n-1)+1$

suppose we have c(n-1) path in (n-1)-Complete Graph. when we add one more vertices, we add $(n-2)\*c(n-1)$ new path and one for directed path.

the result is same as real:

1. 0
2. 1
3. 2
4. 5
5. 16
6. 65

===============================EDITED

$c(n)=\sum\_{i=0}^{n-2} \frac{(n-2)!}{i!}=(n-2)!\*\sum\_{i=0}^{n-2}\frac{1}{i!}$

.

This shows that's about $(2\text{≈}3)\*(n-2)!$
> 0 votes

---
Tags: graphs, combinatorics
---


# Question
Title: Converting decision problems to grammars?
I'm struggling to understand some concepts related to the relationship between language and computability theories.

Can we convert decision problems to the corresponding grammars describing the languages? Can every decidable decision problem be converted to a context-free or context-sensitive grammars?

If it does not make sense at all, what is the relationship between the decision problems and languages?

# Answer
> 3 votes
Yes, every decision problem can be converted into a grammar that generates exactly the "yes"-instances of the problem.

And no, even if the problem is decidable, there is not necessarily a context-sensitive (let alone a context-free) grammar. An example would be the equivalence problem for regular expressions with exponentiation. (reference)

---
Tags: computability, formal-grammars
---


# Question
Title: Distributing values of an array into smaller arrays with bounded sums
Take the following array of integers:

\[60, 45, 30, 45, 45, 5, 60, 45, 30, 30, 45, 60, 60, 45, 30, 30, 60, 30, 30\]

They need to be sorted into pairs of sub-arrays. The first sub-array in each pair must total at most 180, and the second must total at most 240.

How would you find the right combinations of elements so that no elements are remaining after all pairs have been created? I'm told that it is possible with this data set.

# Answer
This is trivial: Since all elements are less than 90, you can create one sub-array with 2 elements and 17 sub-arrays with a single element each and pair them in any way you like.
> 1 votes

---
Tags: algorithms, arrays
---


# Question
Title: Determine if DFAs accept any word which contains bb
Let $\Sigma=\\{a,b,c\\}$. Describe an algorithm that takes as input a deterministic finite automaton $M= (Q,\Sigma,\tau,s,A)$ and determines whether or not $M$ accepts a word containing $bb$ (i.e., a word of the form $\alpha bb \gamma$ for some $\alpha,\gamma \in\Sigma^\*$). You do not have to give a formal proof that your algorithm is correct but you should indicate why this is the case.

# Answer
> 1 votes
**Hints**

* The language $BBS$ consisting of all strings over $\\{a, b, c\\}$ with a substring $bb$ is regular. (Consider the language denoted by the regular expression $(a\cup b\cup c)^\*bb(a\cup b\cup c)^\*$).
* The intersection of two regular languages is regular.
* There is a standard decision algorithm to determine whether a regular language is empty.

So if the language of your input FA, $M$ is $L$, what does $L\cap BBS$ tell you about whether $M$ accepts a string "$\dotsm bb \dotsm$"?

---
Tags: algorithms, finite-automata, decision-problem
---


# Question
Title: A recursively enumerable language and a recursively enumerable set
I am confused between these two terminologies: recursively enumerable language, recursively enumerable set.

Do they have the exactly same meaning?

# Answer
> 2 votes
No they do not have *exactly* the same meaning. A language is a set of strings, whereas a set can be virtually anything. Usually such a set is a set of (natural) numbers, but we also can consider sets of graphs.

However, when the sets are accepted or generated by Turing machines, then they have to be represented on a tape (for input or output). This means they have to be represented as strings anyhow. Hence for the Turing machine itself there is no difference. Only for the human beholder there is an interpretation of the string as number or graph.

# Answer
> -1 votes
The language describes the set, it defines how to decide if a given element is part of the set or not.

The complexity in your given case for that decision is recursively enumberable. You could create a Turing Machine to make this decision, or an computer program in any other prorgamming language like e.g. Java.

Example: The Java compiler tells you if the given input is part of Java or not. Language: Java Set: All possible programs accepted by the Java Compiler Complexity: Time a Turing Machine will take to decide if input is part of the set defined by the language.

Personally I would say the terms can be regarded as the same thing at least in spoken language.

---
Tags: terminology, computability
---


# Question
Title: How do I prove all constants to some exponential power belong to little-o of some function
I'm trying to prove that *c2n = o((loglog n)n)* (That's little-o) for any constant c. I understand that we can prove one function grows at a smaller rate than the other by taking the limit as *n* approaches infinity, and I can very easily pick some arbitrary integer value for *c* and show that indeed *((loglog n)n)* grows at a faster rate. But how do I prove this to be true for any constant *c*?

# Answer
Try proving that $5^{2n} = o((\lg \lg n)^n)$. Write out the proof in detail, and make sure you understand every step.

Then, try replacing the $5$ in the base with an arbitrary constant $c$. Does every step still go through? Hint: you should be able to extend the argument to handle an arbitrary constant $c$, with very little change.

If you're still stuck, edit the question to show us what you've tried, including showing us your proof that $5^{2n} = o((\lg \lg n)^n)$ and your reasoning about which steps are still valid when you replace $5$ with an arbitrary constant $c$.
> 2 votes

---
Tags: asymptotics
---


# Question
Title: Hoare Calculus Incorrect Assignment Axiom
I'm currently preparing for an exam and recently came across the following exercise and would like to know whether my solution would be correct.

**Exercise**: Prove that the following axiom is not correct in the Hoare Calculus:

{true} u:= t {u=t}

**My Proof** via Reductio ad absurdum:

*Assumption*:

Axiom is valid Hoare Calculus Axiom and therefore agrees with the other Axioms.

*Proof*:

Consider the Hoare Triple: {t = u+1} u:=t {u = t}

This triple is obviously invalid because it does not agree with the Assignment Axiom of the Hoare Calculus.

However, given our Assumption, we can derive it as a valid triple:

(t= u+1) =\> (true) (Weaken Precondition)

{true} u:=t {u=t} (Axiom of the Assumption)

=\> {t = u+1} u:=t {u=t} \<- contradiction! =\> Assumption was false, Axiom is not correct.

q.e.d

# Answer
> 0 votes
> Consider the Hoare Triple: {t = u+1} u:=t {u = t}
>
> This triple is obviously invalid because it does not agree with the Assignment Axiom of the Hoare Calculus.

Your mistake is in the *obviously*. In order to prove that the triple is invalid, you need to prove that there is no way to derive it from any combination of the axioms of the Hoare calculus — whether from the assignment axiom alone (perhaps with a strange postcondition) or from that and other axioms. As Andrej Bauer has explained, this tripe is in fact valid in the Hoare calculus.

You can prove that the axiom is invalid by contradiction. However, you'll need to find the contradiction; I don't think this approach leads to an intuitive way of spotting one.

Since the proposed rule is very close to the assignment axiom, let's consider how one might prove it from the assignment axiom, and see where the proof gets difficult. This is often a good way of finding a potential counterexample.

We want to prove that $$\dfrac{}{\\{\mathrm{true}\\} \\; u := t \\; \\{u=t\\}} \tag{A}$$ is valid. The assignment axiom lets us derive any triple of the form $\\{P\[u \leftarrow t\]\\} \\; u := t \\; \\{P\\}$. Ok, so let's take $P = (u=t)$ to get the right postcondition. So the precondition for this application of the assignment axiom is $P\[u \leftarrow t\] = (t = t\[u \leftarrow t\])$. We would like to have the precondition $\mathrm{true}$, which is logically equivalent to $t = t$, but that isn't exactly what we have. The assertion $t = t\[u \leftarrow t\]$ is $t = t$ only when the variable $u$ doesn't appear in $t$. What if it does?

This suggests a counterexample where the variable $u$ appears in the expression $t$. For example, let's take $t$ to be the expression $u+1$, i.e. the instance of the proposed axiom $(A)$ is $\\{\mathrm{true}\\} \\; u := u + 1 \\; \\{u = u + 1\\}$. The precondition is always true, whereas the postcondition is always false, so a calculus that allows us to derive this triple is inconsistent. Therefore the axiom schema $(A)$ is invalid.

# Answer
> 1 votes
Your solution is incorrect because you did not reach a contradiction. You claim that you reached a contradiction with the Assignment axiom. For this to be true, you must produce the negation of an instance of the axiom.

The axiom of assignment states that $$\\{P\[e/x\]\\} \\; x \mathbin{:=} e \\; \\{ P \\}$$ In your example we would have $u$ instead of $x$, $t$ instead of $e$, and $P$ would be the statement $u = t$, which gives us the following instance of the axiom $$\\{ t = t \\} \\; u \mathbin{:=} t \\; \\{ u = t \\}$$ You seem to think this is in contradiction with $$\\{ t = u + 1\\} \\; u \mathbin{:=} t \\; \\{ u = t \\}$$ but that is a logical error. In fact, the axiom of assignment *implies* your statement:

1. $\\{ t = t \\}\\; u \mathbin{:=} t \\; \\{ u = t \\}$ (instance of the axiom of assignment, as above)
2. $\\{ t = u + 1 \\}\\; u \mathbin{:=} t \\; \\{ u = t \\}$ (weakening of the precondition because $t = u + 1 \Rightarrow t = t$.)

**Hint:** to solve the exercise, consider the possibility that the expression $t$ contains $u$.

---
Tags: proof-techniques, correctness-proof, check-my-answer, program-correctness, hoare-logic
---


title: Why use SIMD if we have GPGPU?

text:
# Question
Title: Why use SIMD if we have GPGPU?
I thought this question is better served in the CS part of Stack Exchange. Now that we have GPGPUs with languages like CUDA and OpenCL, do the multimedia SIMD extensions (SSE/AVX/NEON) still serve a purpose?

I read an article recently about how SSE instructions could be used to accelerate sorting networks. I thought this was pretty neat but when I told my comp arch professor he laughed and said that running similar code on a GPU would destroy the SIMD version. I don't doubt this because SSE is very simple and GPUs are large highly-complex accelerators with a lot more parallelism, but it got me thinking, are there many scenarios where the multimedia SIMD extensions are more useful than using a GPU?

If GPGPUs make SIMD redundant, why would Intel be increasing their SIMD support? SSE was 128 bits, now it's 256 bits with AVX and next year it will be 512 bits. If GPGPUs are better processing code with data parallelism why is Intel pushing these SIMD extensions? They might be able to put the equivalent resources (research and area) into a larger cache and branch predictor thus improving serial performance.

Why use SIMD instead of GPGPUs?

# Answer
> 19 votes
Nothing is free. GPGPUs *are* SIMD. The SIMD instructions on GPGPUs tend to be wider than the SIMD instructions on CPUs. GPGPUs tend to be fine-grained multi-threaded (and have many more hardware contexts than CPUs). GPGPUs are optimized for *streaming*. They tend to devote a greater percentage of area to floating point units, a lower percentage of area to cache, and a lower percentage of area to integer performance.

Let's do a comparison. Intel's core i7-5960x has 8 cores, each with 4-wide (double precision) SIMD, running at 3 GHz (3.5GHz turbo), a 20M L3 cache, consumes 356mm^2 and 140W and costs \\$1000. So 8\*4\*3\*4 = 384 double precision GFlops. (The extra 4x is because you can do two fused-multiply-adds per vector lane per cycle.) It can do 768 single precision GFlops. That's about 1.08 DP GFlops/mm^2 and 2.75 DP GFlops/Watt. There's also about 57.5 KB/mm^2 of on-chip cache.

NVidia's GeForce GTX Titan Black has 15 SMXs, each with 32-wide double precision SIMD, running at 890MHz (980MHz turbo), 3.5M of L1+L2 cache, consumes 561mm^2, 250W and costs \\$1000. So 15\*32\*.89\*4 = 1709 double precision GFlops. (Same 4x from two fused-multiply-adds per vector lane per cycle.) It can do 5126 single precision GFlops. That's about 3.05 DP GFlops/mm^2 and 6.8 DP GFlops/Watt. So 3x the DP floating point density per unit area and 3x the DP floating point power efficiency. And the tradeoff? 6.4 KB/mm^2 of on-chip cache. About 9x less dense than the CPU.

So the main difference is that the GPU has chosen an area balance that strongly favors floating point (and especially single-precision floating point) over cache. Even ignoring the fact that you need to copy stuff back and forth between the CPU and GPU to do I/O, how well the GPU is going to do compared to the CPU depends on the program you are running.

If you have a data parallel floating point program with very little *control divergence* (all the vector lanes are doing the same thing at the same time) and your program is *streaming* (can not benefit from caching), then the GPU is going to be about 3x more efficient per unit area or per Watt. But if you have any significant amount of divergent control, non-data-parallel work to do, or could benefit from large read-many-times data structures, the CPU will probably do better.

---
Tags: computer-architecture, parallel-computing
---


title: Determine machine epsilon

text:
# Question
Title: Determine machine epsilon
Consider a base 2 computer that stores floating point numbers using a 6 bit normalized mantissa (x.xxxxx), a 4 digit exponent and a sign for each.

a) For this machine, what is machine epsilon?

b) What is the smallest positive number that can be represented exactly in this machine?

c) What mantissa and exponent are stored for the value 1/10?

I shall present my answers. My question is to know if my answers are correct or incorrect.

My answer for a): 1 would be represented by $1.00000\times 2^0$. The next smallest number after 1 would be $1.00001\times 2^0$. Hence machine epsilon is $1.00001-1.00000=0.00001$. This is equivalent to $\frac{1}{32}$ in base 10.

My answer for b): The smallest positive number that can be represented exactly in this machine would be $1.00000\times 2^{-1111}$

My answer for c): $\frac{1}{10}$ is the repeating decimal $0.\overline{00011}$ in base 2. So the mantissa should be 0.00011 BUT I DON'T KNOW what the exponent should be.

# Answer
> 1 votes
a) Correct!

b) This seems to be correct, but I have to say, this representation for exponents is very strange. A four digit exponent plus a sign bit lets you represent an exponent between $-1111\_2$ to $1111\_2$, however, it has two representations for an exponent of zero, and gives no way to represent the number zero.

c) No. Remember, the leading $1$ is implicit in a normalised number. Hint: $0.\overline{00011}\_2$ = $1.\overline{10001}\_2 \times 2^{-4}$

---
Tags: numerical-analysis
---


# Question
Title: For each vertex of a tree count vertices closer than a specified value
We have a weighted tree of $n\leq 10^5$ nodes, and for every node $v$, value $L(v)$. The goal is to calculate, for every vertex $v$, number of vertices $u$ such that $\mathrm{dist}(v,u)\leq L(v)$. This is a task from a programming contest. Judging by the limit on $n$, and also specifics of time limits on this contest, the desired complexity should be close to linear, i.e. $O(n \log n)$.

If the tree was rooted, and we were asked to count vertices $u$ that are also in a subtree of $v$, then the task could be solved by in-order traversal and a segment tree. However, this doesn't seem to help with this more general problem.

# Answer
> 2 votes
As it is a contest problem, I will give you some tips which may be a good start point.

1. Consider an easier problem: the graph has a vertex $v$ and multiple paths going out of it (they are straight). Of course, the result for vertex $v$ is easy to compute (one DFS). Now try to use the binary search to find the result for remaining vertices (tip: make a sorted list of distances from $v$ to all the other vertices in whole graph and in each separate branch).
2. Now the real problem. Choose any vertex $v$. We can compute the result for it using usual DFS. What if we remove this vertex? Let's say we computed recursively the result in each of the generated subtrees. Then for each vertex $w$ other than $v$ we need to add the number of vertices $s$ outside the $v$-subtree containing $w$ (formally, vertices $s$ such that $d(s,w)\le L(w)$ and $s\to w$ path contains vertex $v$). Try to do it in total $O(n \log n)$ time using the experience from point (1.).
3. Can you choose such vertex $v$ in the graph such that the size of the subtrees after removing $v$ doesn't exceed half of the initial size? Assuming you can, prove that the total running time is $O(n \log^2 n)$.

# Answer
> 0 votes
Since this is a contest problem, I'll just give a hint at one possible approach.

It sounds like you know how to efficiently answer queries of the form "how many vertices are of distance $\le d$ from $v$ and are within the subtree under $w$?".

So, try using that as a subroutine. Assume this is a rooted binary tree. Look at the path from $v$ to the root. In particular, consider $v$'s sibling, $v$'s father's sibling, $v$'$ grandfather's sibling, and try issuing an appropriate query for each. What will the running time be? Does this give you any tips on how to choose the root to make the resulting algorithm efficient?

Update: This doesn't suffice for $O(n \lg n)$ running time, because there may be no way to choose the root so that the average depth of a random leaf is $o(n)$.

---
Tags: algorithms, trees
---


# Question
Title: Communication complexity of comparing sets, for Bitcoin
In Bitcoin, when one node wants to tell another node about a block, it sends the block header, then all the transactions it contains. This is inefficient, because the receiving node might already have some or all of those transactions.

The sending node needs to tell the receiving node

* the transactions that the receiving node does not have
* which transactions are in the block
* what order those transactions are in

What would be more efficient than sending all of the transactions? (Each transaction is about 160 bytes)

You could send a list of hashes of the transactions. That would reduce the overhead for each transaction to 20 bytes (if you used SHA1). The receiving node could ask for the transactions that it was missing. This is the most efficient method that I can think of - but I think there’s probably something better.

# Answer
> 2 votes
One possibly better approach would be to use a Merkle tree, or some other hierarchical data structure like that. If there's a large set of transactions that the sender can identify as probably already known to the recipient, then this might save a significant amount of data transfer.

Build a binary tree, where each leaf corresponds to a single transaction, and where each internal node has two children. Now each leaf node will be labelled with 20 bytes, namely, the hash of the transaction. Each internal node will be labelled with 20 bytes, namely, the hash of the concatenation of the labels on its two children. For example, for each $i$, we might have an internal node at height $i$ that covers the first $2^i$ leaves, with a complete binary tree hanging underneath it (along with a bunch of other internal nodes).

The two parties can then compare their Merkle trees via some interactive protocol. Note that if Alice and Bob established that they both have the same label for some node of their tree, they don't need to examine anything under that node; they know the subtree rooted at that node is the same for both of them. If they have a different label for some node of their trees, then they can recurse and compare their children.

You can probably choose the structure of Merkle tree to take advantage of the probability distribution on where differences are most likely to appear. You can also vary the branching factor. This gives you a space of possible trees, with a range of tradeoffs between the typical number of rounds of interaction vs the typical amount of data that must be communicated. You might be able to choose a parameter setting that is optimal in your setting.

Also, as another optimization, Alice can start by sending Bob the value of some fixed set of her nodes. Notice that your example of sending a list of hashes corresponds to Alice proactively sending the value of all of the leaves. However we might be able to do better by taking advantage of interaction: e.g., if Alice expects that one of her subtrees is probably shared by Bob, she can send just the label on the root of that subtree, and not send anything under that node (e.g., not the hashes of any of the transactions). If she is right and Bob *does* have that transaction, neither has to do any other work. If she is wrong, then some further interaction and additional data must be exchanged.

Many variations on this basic idea are probably possible.

---
Tags: sets, communication-complexity
---


title: doubt regarding power of graph

text:
# Question
Title: doubt regarding power of graph
could you help me in clarifying a doubt regarding how to find square of a graph g from graph g.the doubt occurs on 15th page of the document which I have shown you by the link given.the doubt is that I could see all edges and vertices were correct for square of the graph.But I couldn't see an vertex for sugar,sugar and flour,flour.But it's there for frosting,frosting and eggs,eggs. The link is:http://1drv.ms/1qp7ZDE

# Answer
> 4 votes
The slides you link do not give a clear definition of what $G^2$ is. On page 8, they say

> * Creating a node pair graph $G^2$ from $G$
> * $\langle(p,q),(a,b)\rangle$ is in $G^2$ if $\langle p,a\rangle$ and $\langle q,b\rangle$ are in $G$

and they give an example. From the examples, it appears that they use $(x,y)$ for the *unordered pair* $\\{x,y\\}$, but this is never stated. They don't say what the vertex set of $G^2$ is and they don't say that $\langle(p,q),(a,b)\rangle\in E(G)$ if *and only if* $\langle p,a\rangle\in E(G)$ and $\langle q,b\rangle\in E(G)$. The most natural interpretation would be that the vertex set of $G^2$ is *every* unordered pair $(x,y)$ such that $x,y\in V(G)$, including all pairs $(x,x)$. That would give the usual tensor product of graphs, except using unordered pairs as the vertex set.

However, the example on page 8 has five vertices in $G$ and only eight in $G^2$ (there should be 15). And, as you say, the bipartite example on pages 14–16 has four vertices on the right side of $G$ but only eight on the right side of $G^2$ (there should be ten). So, the slides are completely unclear on this point but my best guess is that, yes, there should be vertices $\langle\mathrm{sugar},\mathrm{sugar}\rangle$ and $\langle\mathrm{flour},\mathrm{flour}\rangle$.

---
Tags: graphs
---


# Question
Title: Fastest algorithm for finding the longest palindrome subsequence
First of all we must read a word, and a desired size.
Then we need to find the longest palindrome created by characters in this word used in order.
For example for size = 7 and word = "abcababac" the answer is 7 ("abababa").

Postscript: the size of the word is smaller than 3000.

# Answer
> 6 votes
There's an algorithm named after Manacher's algorithm, which is really fast, a linear time algorithm.

See Wikipedia's reference

---

Postscript: If you're really familiar with Z Algorithm, you will find that they're alike.

---

**Edit**

I've just misunderstood the OP's meaning (but I don't want to delete the proceding information. It's somewhat useful). He means the longest palindrome subsequence of a string, so dynamic programming seems good: \begin{align\*} f\_{j,k}&=\max(f\_{j,k+1},f\_{j+1,k},2\[S\_j=S\_k\]+f\_{j+1,k-1}),\qquad j\<k\\ f\_{k,k}&=1\\ f\_{j,k}&=0,\qquad j\>k\\ \end{align\*} where $f\_{j,k}$ denotes the length of the longgest palindrome subsequence of $S\_{j..k}$, and $\[P\]$ is Iverson bracket I think it's just like LCS.

# Answer
> 5 votes
The fastest algorithm I can think of is applying LCS in a creative way. It can solve this problem in O(N^2) time and O(N^2) space where N is the size of string.

LCS (S, reverse (S)) will give you the largest palindromic subsequence, as the largest palindromic subsequence will be the largest common subsequence between the string S and its reverse.

For example,
S = "abcababac"
T = "cababacba" (reverse of S)
LCS (S, T) = "abababa"

# Answer
> 2 votes
Problem of finding LPS of a string can be converted into finding Longest Common Subsequence of two strings. In this, one string will be original one and the second will be reverse of the original string.

The Longest Common Subsequence problem is like the pattern matching problem, except that you are allowed to skip characters in the text. Also, the goal is to return just one match, which is as long as possible.

LCS can be solved in $O(n^2)$ using Recursion and Memoization.

There exists a slightly faster algorithm discovered by Masek and Paterson of time complexity $O(n^2/\lg n)$. Paper link: Masek and Paterson

Two other algorithms presented by Hirschberg to compute LCS of two strings $A$ (size $n$) and $B$ (size $m$). Based on the assumption that the symbols that may appear in these strings come from some alphabet of size $t$ (that is actually true in most of the cases). So symbols can be stored in memory using $\log(t)$ bits, which will fit in one word of memory. two symbols can be compared in $O(1)$ time. Number of different in string $B$ is denoted by $s$, which is of-course less than both $m$ and $t$.

1. This one requires $O(pn + n\lg n)$ time where $p$ is the length of LCS. This is used when length of LCS is expected to be small. When we solve this the problem using Dynamic Programming then we encounter that most of the entries in the matrix are same, so we can use the idea of Sparse Dynamic Programming.
2. This algorithm requires $O(p(m+1-p)\log n)$ time. This is very efficient when length of LCS is close to $m$, in that case it will be close to $O(n \lg n)$.

Detailed procedures and algorithms are explained in the Hirschberg's paper.

An another good algorithm is proposed by Sohel Rahman that runs in $O(R \log\log n)$ time, where $R$ is the total number of ordered pairs of positions at which to strings match. It is not applicable when $R$ is the order of $O(n^2)$, but there are many cases when $R$ is the order of $n$. This one uses the concept RMQ (Range Maximum Query). Paper link: Rahman

# Answer
> -2 votes
I'm probably missing something, because it seems rather trivial to me: Try to pair each character with an equal character. Then put the first character of each pair on the left side, the other character on the right side, and if there are any characters remaining (ie, characters not paired with another one), then pick one of them and put that one in the middle.

---
Tags: algorithms, strings, subsequences
---