# Question
Title: How internet speed is manipulated at the physical level
Although I am a computer science major, I am having a hard time understanding how internet providers have control over internet speed (example: offer different speeds to different customers, one with a higher price, etc.).

And I mean how is it that they do it at the physical level or bit level if I may. I think that they might have some tool that let more bits flow through a certain pipe or something like that. I would appreciate if someone could answer my question or ask me any clarification about my inquiry if it's not clear.

# Answer
> 7 votes
This is a very wide topic indeed.

Basically, there are two ways to measure and control the speed of a connection: physical speed and logical speed.

Physical speed is determined by the technology, protocol and sometimes the physical conditions of the line. For example, a Fast Ethernet has a physical speed of about 100 Mbps, meaning that it could in theory transmit information at 100 Mbps at physical layer (brute bits). Most current optical fibre connections can reach several gigabit per second of brute speed.

In some case, the physical conditions may affect the physical speed for a particular link. In those cases, a initial negotiation when the link is established determines the maximum physical attainable speed. This is how old modem and current xDSL systems work.

On the other hand, there is a logical speed in the line, usually lower than the physical connection. In most current systems, at a logical (more abstract) level, the information travels in packets. Ethernet for example uses Ethernet packets, which usually is comparable to IP packets but not always. ATM networks use ATM packets that contains 53 bytes of data (48 of them are payload).

Now the relationship between both speeds: single packets travel at physical speed. If you have at home a GPON (fiber) connection, it may have a physical speed of 2.4 Gbps. Every GPON packet will travel at 2.4 Gbps. So how the speed provided to the user is limited? Limiting the packet rate at a higher level. Send a 1 Kbps packet every 1 ms, and you just limited the perceived speed to 1 Mbps. This can be easily done by software, allowing all kind of traffic control, burst control, congestion control, monitoring, etc.

Deploying a high-speed physical connection to provide low-speed logical speed services has several advantages:

* The same physical link can serve for different logical speeds. Same technology makes the deployment easier and the manufacturing cheaper.
* Logical speed can be modified to any value, at any time, simply by a change in the configuration of one or more devices. No need to replace equipment unless you need to provide more speed that the one supported by the physical layer.
* The same physical link can be used by more people, and this is key. If you have a 1 Mbps service using fibre or cable connection, the physical layer would be unused between your packets. But it can be used for other user's packets, it is shared. And it is aggregated in the network hierarchy. A 10 Gbps link can carry thousands of low-speed link from thousands of users.

I hope this is clear and answers your question, but certainly it is just a very simplified overview. Feel free to ask more questions or clarifications.

---
Tags: computer-networks
---


title: Ambiguity Problem (Language Structures)

text:
# Question
Title: Ambiguity Problem (Language Structures)
I'm having serious issues fining an unambiguous version of a particular grammar. I've looked online for help for this particular problem and for general methods for finding unambiguous versions of grammars, and though I understand the concept, I can't seem to figure this out. Any help/advice? I keep getting really close then finding something that doesn't fit. Here is the grammar in question:

S -\> aS | bS | Sa | Sb | aa

# Answer
The language of the grammar $G$ presented here is regular and its corresponding regular expression is $$r = (a \mid b)^\*aa(a \mid b)^\*.$$ Now, convert the regular expression to a minimal finite automaton and use this question to convert the automaton to an unambiguous regular grammar, which is always possible. In the end you can get something like this:

$$ \begin{align} S &\rightarrow aA \mid bS \\ A &\rightarrow aB \mid bS \mid a \\ B &\rightarrow aB \mid bB \mid \epsilon \end{align} $$

---

Proof that $\mathscr{L}(r) = \mathscr{L}(G)$: (1) Let $s \in \mathscr{L}(r)$, hence $s = x aa y$, where strings $x,y$ consist of characters $x\_i, y\_j \in \Sigma, i = \[1..m\], j = \[1..n\], m = |x|, n = |y|$. There is a derivation of $s$: $$S \rightarrow x\_1S \rightarrow x\_1x\_2S \rightarrow ... \rightarrow x\_1...x\_mS = xS \rightarrow xSy\_n \rightarrow xSy\_{n-1}y\_n\rightarrow ... \rightarrow xSy\_1...y\_n = xSy \rightarrow xaay.$$ Thus $s = xaay \in \mathscr{L}(G)$ and $\mathscr{L}(r) \subseteq \mathscr{L}(G)$.

(2) Let $s \in \mathscr{L}(G)$. This means there exists some derivation $$S \rightarrow \alpha\_1 \rightarrow \alpha\_2 \rightarrow ... \rightarrow \alpha\_p = s.$$ Observe that the only way to make the non-terminal $S$ disappear is to use the rule $S \rightarrow aa$ and it must be the last step of the derivation: $$S \rightarrow \alpha\_1 \rightarrow ... \rightarrow \alpha\_{p-1} = xSy \rightarrow \alpha\_p = s = xaay,$$ where $x,y$ are some strings of terminals. Thus $s = xaay \in \mathscr{L}(r)$ and $\mathscr{L}(G) \subseteq \mathscr{L}(r)$, resulting in $\mathscr{L}(G) = \mathscr{L}(r)$. Qed.
> 2 votes

---
Tags: formal-languages, ambiguity
---


title: Why Term Rewriting?

text:
# Question
Title: Why Term Rewriting?
I've done a bit of googleing and have come up a bit short.

I am wondering what are the main reasons for computing scientists, programmers, to study term rewriting, and/or term graph rewriting.

As far as I can tell, it just helps for basic reasoning about functional programs and (imperative) program control. Apparently, it is a topic of great interest to logicians and those who study constructive abstract algebras.

Any help would be most appreciated!

# Answer
> 12 votes
I am not sure that this will bring you more than you already know. But then, I may fail to understand the reasons that make you wonder about term rewriting. It does help.

As you may know, grammars are string rewriting systems. At the top of the Chomsky hierarchy, you have type 0 grammars, which define recursively enumerable (RE) anguages, and have the computational power of Turing machines.

So that tells you that rewriting systems in general have a lot do do with expressing algorithms.

The problem with strings in general is that there is no obvious way to attach semantics to them. It is a kind of amorphous rewriting.

What people are usually interested in is expressing algorithms in specific domains that have structure and properties. Such domains are often defined from elementary (atomic) entities, and closed by various operations, possibly quotiented by equivalence relations, and so on. These are often called algebras.

These domains are often abstract. But computations on their elements can be expressed only on concrete representations. Terms are natural represntation of these elements since they express how elements can be obtained for other elements by application of operations, recursively downto atomic elements (though general properties need not always go all the way down). Terms are a kind of tree structure syntax that can be manipulated to express algorithms (as for string). But the operator operand structure of terms also allows associating to them semantics in some abstract domain by means of homomorphisms.

Rather than take the very formal view of wikipedia and many texts on this topic, just consider programs. It is usually recognized that a convenient syntactic representation of programs is what is called Abstract Syntax Tree (AST). But an AST is just a term to represent a program object. Denotational semantics is a way of defining abstract domains and associate values from these domains to AST (or AST subtrees) by mean of homomorphisms. Programs in AST form can be transformed or optimized by applying rewriting rules (I am not asserting that all optimizations can or should be done that way).

Transformation of algebraic expressions for various purposes can be expressed by term rewriting. For example, the simplification of some expressions. Various types of computations can also be naturally expressed as term rewriting, such as the computation of derivatives. Term rewriting is also used sometimes to define canonical forms in algebras, when the same semantic entity can have several syntactic representations.

I do suggest that you look at the wikipedia article on this topic.

# Answer
> 7 votes
My thought is, it's because Term Rewriting is something extremely fundamental, and that lets you describe things in an extremely low-level way, independent of any hardware.

Term-rewriting can describe grammars, but it also gives you the mechanics to described logical systems, like first order logic, etc. Proving and deductions can be written as term-writings. Then, the substitution of term-rewriting is really the only operation you have. The simplicity here is valuable because you're describing logic, so you can't use the full complexity of logic to describe your system (since that's the system you're trying to describe).

This then gives you the mechanics you need to talk about the lambda calculus as a logical/axiomatic system, which gives you an extremely formal, fundamental version of computation.

Turing Machines are useful, but their underlying definitions require you to have a concept of sets, functions, etc. There's a lot more math that's assumed to have been build.

Lambda calculus, on the other hand, is defined in terms of logic, so you can use it without much in the way of definitions for set theory, functions, etc.

Term rewriting, modeled by logic, isn't only applicable to functional programing. When you're doing formal verification of hardware or software, you're always going to do reasoning of some sort, and this reasoning can be modeled by term rewriting.

# Answer
> 2 votes
One very practical reason is that it leads to the construction of program transformation systems, tools that let one manipulate the code for programs as terms (abstract syntax trees) using surface-syntax rewrites.

One example of this my system, the DMS Software Reengineering Toolkit, which has been used for a wide variety of program analysis and massive transformation tasks. You can see how DMS expresses rewrites. These rewrites are applied by an associative-commutative term rewriting system that operates behind the scenes.

---
Tags: term-rewriting
---


# Question
Title: Parsing arbitrary context-free grammars, mostly short snippets
I want to parse user-defined domain specific languages. These languages are typically close to mathematical notations (I am not parsing a natural language). Users define their DSL in a BNF notation, like this:

```
expr ::= LiteralInteger
       | ( expr )
       | expr + expr
       | expr * expr

```

Input like `1 + ( 2 * 3 )` must be accepted, while input like `1 +` must be rejected as incorrect, and input like `1 + 2 * 3` must be rejected as ambiguous.

A central difficulty here is coping with ambiguous grammars in a user-friendly way. Restricting the grammar to be unambiguous is not an option: that's the way the language is — the idea is that writers prefer to omit parentheses when they are not necessary to avoid ambiguity. As long as an expression isn't ambiguous, I need to parse it, and if it isn't, I need to reject it.

My parser must work on any context-free grammar, even ambiguous ones, and must accept all unambiguous input. I need the parse tree for all accepted input. For invalid or ambiguous input, I ideally want good error messages, but to start with I'll take what I can get.

I will typically invoke the parser on relatively short inputs, with the occasional longer input. So the asymptotically faster algorithm may not be the best choice. I would like to optimize for a distribution of around 80% inputs less than 20 symbols long, 19% between 20 and 50 symbols, and 1% rare longer inputs. Speed for invalid inputs is not a major concern. Furthermore, I expect a modification of the DSL around every 1000 to 100000 inputs; I can spend a couple of seconds preprocessing my grammar, not a couple of minutes.

What parsing algorithm(s) should I investigate, given my typical input sizes? Should error reporting be a factor in my selection, or should I concentrate on parsing unambiguous inputs and possibly run a completely separate, slower parser to provide error feedback?

(In the project where I needed that (a while back), I used CYK, which wasn't too hard to implement and worked adequately for my input sizes but didn't produce very nice errors.)

# Answer
> 19 votes
Probably the ideal algorithm for your needs is Generalized LL parsing, or GLL. This is a very new algorithm (the paper was published in 2010). In a way, it is the Earley algorithm augmented with a graph structured stack (GSS), and using LL(1) lookahead.

The algorithm is quite similar to plain old LL(1), except that it doesn't reject grammars if they are not LL(1): it just tries out all possible LL(1) parses. It uses a directed graph for every point in the parse, which means that if a parse state is encountered that has been dealt with before, it simply merges these two vertices. This makes it suitable for even left-recursive grammars, unlike LL. For exact details on its inner workings, read the paper (it's quite a readable paper, though the label soup requires some perseverance).

The algorithm has a number of clear advantages relevant to your needs over the other general parsing algorithms (that I know of). Firstly, implementation is very easy: I think only Earley is easier to implement. Secondly, performance is quite good: in fact, it becomes just as fast as LL(1) on grammars that are LL(1). Thirdly, recovering the parse is quite easy, and checking whether there is more than one possible parse is as well.

The main advantage GLL has is that it is based on LL(1) and is therefore very easy to understand and debug, when implementing, when designing grammars as well as when parsing inputs. Furthermore, it also makes error handling easier: you know exactly where possible parses stranded and how they might have continued. You can easily give the possible parses at the point of the error and, say, the last 3 points where parses stranded. You might instead opt to try to recover from the error, and mark the production that the parse that got the furthest was working on as 'complete' for that parse, and see if parsing can continue after that (say someone forgot a parenthesis). You could even do that for, say, the 5 parses that got the furthest.

The only downside to the algorithm is that it's new, which means there are no well-established implementations readily available. This may not be a problem to you - I've implemented the algorithm myself, and it was quite easy to do.

# Answer
> 6 votes
My company (Semantic Designs) has used GLR parsers very successfully to do exactly what OP suggest in parsing both domain specific languages, and parsing "classic" programming languages, with our DMS Software Reengineering Toolkit. This supports source-to-source program transformations used for large-scale program restructuring/reverse engineering/forward code generation. This includes automatic repair of syntax errors in a pretty practical way. Using GLR as a foundation, and some other changes (semantic predicates, token-set input rather than just token input, ...) we've managed to build parsers for some 40 languages.

As important as the ability to parse full languages instances, GLR has also proven extremely useful in parsing source-to-source rewrite rules. These are program fragments with a lot less context than a full program, and thus generally have more ambiguity. We use special annotations (e.g, insisting that a phrase correspond to a specific grammar nonterminal) to help resolve those ambiguities during/after parsing the rules. By organizing the GLR parsing machinery and the tools around it, we get parsers for rewrite rules for "free" once we have a parser for its language. The DMS engine has a built-in rewrite-rule applier that can then be used to apply these rule to carry out desired code changes.

Probably our most spectacular result is the ability to parse full C++14, in spite of all the ambiguities, using a context-free grammar as a basis. I note that all the classic C++ compilers (GCC, Clang) have given up the ability to do this and use hand-written parsers (which IMHO makes them much harder to maintain, but then, they're not my problem). We have used this machinery to carry out massive changes to the architecture of large C++ systems.

Performance-wise, our GLR parsers are reasonably fast: tens of thousands of lines per second. This is well below the state of the art, but we have made no serious attempt to optimize this, and some of the bottlenecks are in the character stream processing (full Unicode). To build such parsers, we pre-process the context free grammars using something quite close to an LR(1) parser generator; this normally runs on a modern workstation in ten seconds on big grammars the size of C++. Surprisingly, for very complex languages like modern COBOL and C++, the generation of lexers turns out to take about a minute; some of the DFAs defined over Unicode get pretty hairy. I just did Ruby (with a full subgrammar for its incredible regexps) as a finger-exercise; DMS can process its lexer and grammar together in about 8 seconds.

# Answer
> 1 votes
There are many general context-free parser that can parse ambiguous sentences (according to an ambiguous grammar). They come under various names, notably dynamic-programming or chart parsers. The best known one, and next to simplest, is probably the CYK parser that you have been using. That generality is needed since you have to handle multiple parses and may not know till the end whether you are dealing with an ambiguity or not.

From what you say, I would think that CYK is not such a bad choice. You probably do not have much to gain by adding predictiveness (LL or LR), and it may actually have a cost by discriminating computations that should be merged rather than discriminated (especially in the LR case). They may also have a corresponding cost in the size of the parse forest that is produced (which may have a role in ambiguity errors). Actually, while I am not sure how to compare formally the adequacy of the more sophisticated algorithms, I do know that CYK does give good computation sharing.

Now, I do not believe there is much literature on general CF parsers for ambiguous grammars that should only accept unambiguous input. I do not recall seeing any, probably because even for technical documents, or even programming languages, syntactic ambiguity is acceptable as long as it can be resolved by other means (e.g. ambiguity in ADA expressions).

I am actually wondering why you want to change your algorithm, rather than stick to what you have. That might help me understand what kind of change could best help you. Is it a speed issue, is it the representation of parses, or is it the error detection and recovery?

The best way to represent multiple parses is with a shared forest, which is simply a context-free grammar that generates only your input, but with exactly all the same parse trees as the DSL grammar. That makes it very easy to understand and process. For more details, I suggest you look at this answer I gave on the linguistic site. I do understand that you are not interested in getting a parse forest, but a proper representation of parse forest can help you give better messages as to what the ambiguity problen is. It could also help you decide that the ambiguity does not matter in some cases (associativity) if you wantd to do that.

You mention the processing time constraints of your DSL grammar, but give no hint as to its size (which does not means that I could answer with figures it you did).

Some error processing can be integrated in these general CF algorithms in simple ways. But I would need to understand what kind of error processing you expect to be more affirmative. Would you have some examples.

I am a bit ill at ease to say more, because I do not understand what are really your motivations and constraints. On the basis of what you say, I would stick to CYK (and I do know the other algorithms and some of their properties).

---
Tags: formal-languages, parsers, compilers
---


# Question
Title: How would a DFA be designed to accept a language defined as the string comprised of every other character in each string in another language?
For example, you have a DFA that accepts the language comprised of strings aabbbaa and aaabbbbaaa, and you want to create a new DFA that accepts a language comprised of strings abba and aabba (strings made up of every other character in the strings in the original language). What would be the generalized construction technique for creating the new DFA that could be applied to any DFA to produce the same results?

I think there's something to it involving creating an NFA using lambda transitions from each state to the following state in the original DFA, then converting the NFA to a DFA, but that creates a DFA that accepts more strings than originally intended.

Any suggestions?

# Answer
This is a closure property. For language $L\subseteq \Sigma^\*$, define the language $even(L) = \\{ x\_2x\_4\dots x\_{2n} \mid x\_1x\_2x\_3\dots x\_{2n-1}x\_{2n} \in L, x\_i\in\Sigma\\}$. Now for regular $L$ the language $even(L)$ is again regular. This is a special case of closure of the regular languages under finite state transductions.

In case of this specific property an automaton $M\_1$ for $even(L)$ when $M$ for $L$ is given, can be found as follows. For every pair of consecutive transitions $(p,a,q)(q,b,r)$ for $M$ introduce the transition $(p,b,r)$ in $M\_1$.

Additionally one needs a somewhat formal argument that this will in fact work.

Alternatively, this closure property can be deduced from known closure properties: (inverse) morphisms and intersection with regular languages. Make a copy of $\Sigma$: $\bar\Sigma=\\{\bar a \mid a\in \Sigma\\}$. Define the morphisms $g,h:(\Sigma\cup\bar\Sigma)^\*\to \Sigma^\*$ where $g$ removes the bar (but keeping the letters), and $h$ removes letters from $\bar\Sigma$. $R$ is the regular language $(\bar\Sigma\Sigma)^\*$ Then $even(L)$ is the composition $h(g^{-1}(L) \cap R) $.
> 2 votes

---
Tags: formal-languages, automata, finite-automata, dfa
---


# Question
Title: Solutions to Diophantine Equations using a Min Heap
I've recently come across this problem:

> Find all solutions to the equation $a + 2b^2 = 3c^3 + 4d^4$ for which $a, b, c, d$ are all less than $100,000$. Hint: use one min-heap and one max-heap.

I can think of an algorithm involving two min-heaps (one for the LHS and one for the RHS), but can't figure out how a max-heap can be used. It needs to be efficient.

How could a max-heap be incorporated?

# Answer
A min-heap with entries $x\_i$ is equivalent to a max-heap with entries $-x\_i$ (or more generally, $A - Bx\_i$ for any $B \> 0$, or even more generally, $\phi(x\_i)$ for any monotone decreasing $\phi$). So you can convert your solution with two min-heaps to a solution with one min-heap and one max-heap, as well as to a solution with two max-heaps.
> 1 votes

---
Tags: algorithms, heaps
---


# Question
Title: Finding examples of languages that are "anti-palindromic"
Let $\Sigma = \\{ 0, 1 \\}$. A language $L \subseteq \Sigma^\* $ is said to have the "anti-palindrome" property if for every string $w$ that is a palindrome, $w\notin L$. In addition, for every string $u$ that is **not** a palindrome either $u\in L$ or $\mathrm{Reverse}(u) \in L$, but not both(!) (exclusive or).

I understand the anti-palindrome property, but I could not find any languages that have this property. The closest one I could find is $\Sigma^\* \setminus L$, but it does not have the exclusive or part... that is, for example, both $01$ and $10$ are in $L$.

Could anyone give me an example of a language that has this propery? Or possibly even more than a single example, because I fail to see what kind of limitations this puts on a language. (Must it be non-regular? Context Free? Or not even in $R$? and etc.)

# Answer
One example will be $L = \\{ x\ \ |\ \ binary(x) \< binary(x^R), x\in \[0,1\]^\*\\}$.

And yet another example $L' = \\{ x\ \ |\ \ binary(x) \> binary(x^R), x\in \[0,1\]^\*\\}$.

The idea is, if $x \neq x^R$ you make a rule to choose only one of them. You need to choose the rule such that palindromes should be rejected ($f(x) \< f(x^R)$, for palindromes you must have $f(x)= f(x^R)$).You can also change the alphabet, I took binary alphabet just to get a quick answer.

$L$ and $L'$ above are not regular. And every *anti-palindromic* language will be non-regular and can be as bad as a non-RE language. Examble of an undecidable language: $L=\\{x\ \ |\ \ $such that $ binary(x)\<binary(x^R)$ if both $x$ and $x^R$ $\not\in$ Halt or both $x$ and $x^R$ $\in$ Halt, otherwise if $x \in$ Halt$\\}$

Klaus Draeger explained in the comment below that *anti-palindromic* language given at the beginning of the answer is context-free: $L=\\{x0y1x^R\ |\ x,y\in\\{0,1\\}^\*\\}$
> 13 votes

# Answer
About generating a few examples:

Building on the answer of @shreesh, we can prove that every anti-palindrome language must be of the form $$ L = \\{ x \ |\ x \< x^R \\}\qquad (\*) $$ for *some* strict total ordering $\<$.

Indeed, given any anti-palindrome $L$, we can define an associated $\<$ as follows. We start by taking any enumeration $x\_0,x\_1,\ldots$ of $\\{0,1\\}^\*$, where each word occurs exactly once. Then, we alter the enumeration: for each pair of non-palindromes $x,x^R$, we swap their position so to make the one that belongs to $L$ to appear before the other. The new enumeration induces a total ordering $\<$ satisfying $(\*)$.

That every $L$ defined as $(\*)$ is non-palindrome is trivial, so $(\*)$ is a complete characterization of non-palindrome languages.

Addressing the original question, we now know that we can obtain several examples of anti-palindrome languages $L$ by crafting orderings $\<$. We also know that by doing that we are not restricting ourselves to a subclass of languages, losing generality.

---

About the question "can these languages be regular?":

To prove that any anti-palindrome $L$ is non regular, assume by contradiction it is regular.

1. Since regularity is preserved by reversal, $L^R$ is also regular.
2. Since regularity is preserved by union, $L \cup L^R$, which is the set of all the non-palindromes, is also regular.
3. Since regularity is preserved by complement, the set of all palindromes is regular.

From the last statement, we can derive a contradiction by pumping. (See e.g. here for a solution)
> 11 votes

# Answer
For what it's worth, here is a simple context-free grammar for one anti-palindromic language:

$$\begin{align} S &\to 0 S 0 \mid 1 S 1 \mid 0 X 1 \\ X &\to \epsilon \mid X 0 \mid X 1 \end{align}$$

(In fact, this is the anti-palindromic language proposed by @shreesh, using lexicographic comparison for the less-than operator.)
> 10 votes

---
Tags: formal-languages
---


# Question
Title: Prize collecting Steiner tree on graph without weights on edges
I have been trying to find an easy-to-implement approximation algorithm on the problem of Prize collecting Steiner tree on node-weighted graph without weights on the edges. The closest I have come is the one in The prize collecting Steiner tree problem: Theory and Practice by Johnson, Minkoff and Phillips, but the GW algorithm provided won't work without weights on edges (I think).

The problem I'm trying to solve is:

Given a graph $G=(V,E,w)$, $w$ being a function assigning non-negative weights to nodes, and a set of query nodes $Q$, find a connected subgraph $H$ of $G$, spanning all nodes in $Q$, and also maximizing the following function

$$f(H) = \sum\_{v\in V\_H}w(v) + \min\_{v \in V\_H}\deg\_H(v)$$

with $V\_H \subseteq V$ being the set of nodes in $H$.

Keep in mind I need an easy to implement approximation algorithm to use as a baseline for comparison, so any LP or SDP ways to solve it, won't be of much help.

# Answer
Something seems not quite right. Your problem can be solved in polynomial time, so I doubt that it is NP-hard. Let me explain how to solve it in polynomial time.

First note that there exists a positive integer $t$ such that your problem is equivalent to finding $H$ that maximizes

$$f\_t(H) = \sum\_{v \in V\_H} w(v) + t,$$

subject to the additional constraint that $\deg\_H(v) \ge t$ for all $v \in V\_H$. Also, $1 \le t \le n$, where $n=|V|$ is the number of vertices in $G$, so there are at most $O(n)$ possible values for $t$. That means we can try them all and, for each $t$, find the optimal choice of $H$. Given $t$, maximizing $f\_t(H)$ can be done by a simple iterative fixpoint algorithm, where you keep as many vertices of $V$ as possible.

In this way, we obtain the following algorithm:

1. For $t := 1,2,\dots,n$:

a. Repeatedly delete vertices of degree $\le t$ until there are no more to delete. In other words, while there exists $x \in V$ such that $\deg(x) \le t$, delete $x$ from $V$.

b. If there exists a single connected component of $G$ that contains all vertices of $Q$, set $H$ to be that component, compute $f(H)$, and if this $f(H)$ is better than anything found before, remember this $H$.

Correctness follows from the above discussion. This can be implemented so that its running time is $O((n+m) \alpha(n))$, where $n=|V|$ and $m=|E|$ and $\alpha(\cdot)$ is the inverse Ackerman function.
> 1 votes

---
Tags: algorithms, approximation, spanning-trees
---


# Question
Title: How does the automatic complexity analysis of Codility work?
When completing exercises on Codility.com you submit your code to a server for analysis. You then receive a report containing the detected algorithm complexity of the code.

I was just wondering how it does this automatically - i.e. without any O(n) analysis?

# Answer
> 2 votes
Probably only Codility knows for sure how they do it. But here is how I bet they do it.

First, they devise a set of test cases of varying sizes. They run your program on each test case and time how long it takes. This gives them a set of observations $(n\_i,t\_i)$, where $n\_i$ is the size of the $i$th test case and $t\_i$ is the time your program takes given that input. These can be viewed as a set of points in the 2D plane.

Second, they try to fit a curve to these points. For instance, they check whether a line appears to fit the points, or a quadratic, or a cubic. They probably have a library of a set of families of curves (e.g., $cn, $cn^2$, $c n \lg n$, $c \lg n$, and so on), and they check each to which ones are consistent with the observation. Then they output that one as the running time of your algorithm.

I would imagine some adjustments might be necessary. Rather than checking whether the points fit the curve, it might be necessary to check whether the points all fall below the curve. For instance, rather than checking whether there exists a constant $c$ such that $t\_i \approx c n\_i^2$ for all $i$, they might check whether there is a constant $c$ such that $t\_i \le c n\_i^2$ for all $i$ (with some constraints on $c$, e.g., $c \le 1000$). Out of all asymptotic running times that seem to be consistent with the observations, they select the asymptotically smallest one and output that one.

This approach has the advantage that it does not require analysis of source code. All they need is the ability to run your program and time its running time.

At the same time, this heuristic is definitely not foolproof: it can give the wrong answers in some cases. See How to fool the plot inspection heuristic?

# Answer
> 1 votes
There are some known methods for doing this, but the important thing to remember is, we can only ever get an upper or lower bounds, but we can't know if they're tight. In general, determining the complexity of an algorithm is undecidable, since if we could do that, we could solve the halting problem.

But there are some known techniques for doing this, that will work well in practice. For example, if there's a loop `i from 0 to n-1`, and the loop doesn't alter `n`, or have any break statements, we know the loop will run exactly `n` times.

For clear cut cases like this, you can compute this in a "top-down" way: you recursively determine the complexity of the loop body, determine the number of times the loop body is run. Things like this break down as soon as you do something more complicated (i.e. the number of times the loop is run changes, or doesn't depend directly on an input parameter), and there's really no way to know how they deal with hard cases without seeing their system.

Many systems are based on the idea of a system of recurrence relation: the complexity of a group of functions which call each other is determined, where the complexity of the functions called are left as variables. Then, you try to "solve" the system, or at least find an upper bound for it. This is particularly popular in functional languages.

Any bounds obtained this way aren't tight. What that means is, such an algorithm might return $O(\infty)$ even if the algorithm halts, return $O(2^n)$ even if the algorithm is polynomial (for upper bounds). Likewise, it might return $\Omega(1)$ for a lower bound, even if the algorithm is slower. These technically aren't incorrect as upper or lower bounds, they're just not tight.

It's also possible that they are doing some things empirically. For example, you could sample the run-time of the algorithm on a large number of inputs of different lengths. Then, you could set up a least-squares regression system for $n, n^2 ... \log n, n \log n, 2^n$, etc, and use some model-selection procedure to eliminate factors. This is pretty unreliable, though: lots of algorithms look polynomial for small inputs, and then turn exponential for larger inputs, plus there's lots of noise from the randomness of the procedure.

---
Tags: algorithm-analysis, runtime-analysis
---


title: Datalog - Single Step Operator

text:
# Question
Title: Datalog - Single Step Operator
I am currently taking a class called Logic for Computer Scientist. During the first four weeks or so now we have been studying a concept Datalog with subsections Syntax and Formal Semantics and Fixed-Point Semantics. In these weeks we have looked at several definitions atoms, ground atoms, herbrand interpretations, herbrand models, and herbrand base, and these concepts make complete since to me. We are currently looking at something called the Single Step Operator(Immediate Consequence Operator), and I am having a hard time understanding what it actually does. It appears to be in the form of a set builder notation which simply builds a set based of certain rules. This operator appears to take input and filter out some results based of the rules in the Definition of the Single Step Operator

I am looking to see if somebody can actually explain what this is doing. When it comes to understanding what the symbols mean I get it. But I can understand how exactly it affects the data being passed to it/used by it. If anybody has some guidance I would really appreciate it or any good links everything I have found on Google has the same sort of layout as what I show in the image so it doesn't offer any benefit to understanding the concept.

Thanks in advance.

# Answer
It's pretty straightforward from an operational perspective. It finds all the facts deduced by firing all the rules for exactly one round on the current database. Typically, you'll have $I\_{n+1} = I\_n \cup T\_P(I\_n)$ so that $I\_n$ is a monotonically growing database.

Concretely, say you have the following rules and facts.

```
p(a).
q(X) :- p(X).
r(X) :- q(X).

```

Then the initial database is $I\_0 = \\{\mathtt{p(a)}\\}$. $T\_P(I\_0) = \\{\mathtt{q(a)}\\}$, so $I\_1 = \\{\mathtt{p(a)}, \mathtt{q(a)}\\}$. Then $T\_P(I\_1) = \\{\mathtt{q(a)},\mathtt{r(a)}\\}$ and $I\_2 = \\{\mathtt{p(a)}, \mathtt{q(a)},\mathtt{r(a)}\\}$. Finally, $T\_P(I\_2) = \\{\mathtt{q(a)},\mathtt{r(a)}\\}$. At which point $I\_3 = I\_2$ which would be an implementation's signal to stop. (In my particular formulation I didn't include facts as consequences but you could do that as well. It's not clear if your definition treats facts as rules with empty heads.)
> 2 votes

---
Tags: logic, sets
---


# Question
Title: How to iterate through all values of an array?
I'm trying to implement a brute-force algorithm.

If I have one variable `x`, I can iterate through all its values using a `for` loop:

```
for x in {1,2,..,MAX}:
    do something with x

```

But what if I have an array `A`? The array has length `SIZE`, and each element takes values in the range `1..MAX`. Thus, there are `MAX^SIZE` possible values of this array. How do I iterate through all such possible values?

I'm asking for an algorithm, not an implementation on a particular language. Both `MAX` and `SIZE` are arguments. `SIZE` is not fixed, so I can't just create a set of nested for-loops (the number of for-loops that would be needed isn't fixed in advance and depends on the value of `SIZE`).

# Answer
> 7 votes
There are several approaches. I will use 0-based indexing (so array elements are in the range `0 .. MAX-1`) rather than 1-based indexing (range `1 .. MAX`), for ease of notation.

## Treat as an integer

You can treat the contents of an array as an integer in the range `0 .. MAX^SIZE - 1`, expressed in base `MAX`. For example, the array with contents `[0, 3, 1]` corresponds to the integer `0 * MAX^2 + 3 * MAX + 1`. Conversely, each such integer corresponds to an array.

Of course you can iterate through these integers by starting at 0 and incrementing until you reach `MAX^SIZE - 1`. Now by expressing that integer in base `MAX`, you can convert the integer to an array, and thereby iterate through all possible values of the array.

## Depth-first search

You can view this as a complete tree of depth `SIZE`, where each internal node has branching factor `MAX`. Each leaf of the tree corresponds to a value of the array. Then, you can iterate through the leaves of the tree following any standard tree traversal algorithm.

## Direct iteration

To iterate through these arrays, it suffices to create an order on the arrays and build an algorithm to advance from one array to the next-largest array. For this, you can use lexicographic order. The smallest (first) such array is the all-zeros array `[0, 0, ..., 0]`.

Given an array `A`, you can advance to the next array in lexicographic order via a simple procedure. Basically, you increment the last element of the array; if that becomes too large (equal to `MAX`), it wraps around to 0, and then you increment the next-to-last element of the array (continuing if it wraps around). If you think about it a bit, this is basically equivalent to the "treat as an integer" solution.

## Running time

All of these methods have basically the same running time. Asymptotically they all require approximately `MAX^SIZE` operations. Depending on representation and implementation details, direct iteration might be slightly faster, but the differences are likely to be minor.

(The fine print: depending upon implementation details, the running time of the "treat as an integer" method might be more like `SIZE * MAX^SIZE`.)

There's no algorithm that can iterate through all values of the array in less than `MAX^SIZE` operations (as the number of possible arrays is a lower bound on the time to iterate through them all), so there's no hope for an algorithm that is significantly better.

---
Tags: algorithms
---


title: Voronoi cells for rectangles

text:
# Question
Title: Voronoi cells for rectangles
I am looking for a reference on the following variant of a Voronoi diagram:

* Instead of seed points, there are seed rectangles which are axis-parallel and pairwise-disjoint.
* Instead of Euclidean distance, we are interested in Manhattan distance.

The goal is to partition the plane into regions, such that the points in each region $i$ are closer (in Manhattan distance) to rectangle $i$ than to every other rectangle.

What would such cells look like? Are there algorithms for finding them?

# Answer
Essentially, these Voronoi diagrams are problems about solving Voronoi problems for $L\_1$ metric. Both $L\_1$ and $L\_\infty$ has efficient solutions for the case of points ($O(n \log n$) time complexity algorithms).

You might be interested in some of the Papadopoulou's papers.

For $L\_\infty$ metric you can use the more general solution for polygon offset distance. (Gill Barequet, Matthew Dickerson, Michael T. Goodrich: Voronoi Diagrams for Convex Polygon-Offset Distance Functions. Discrete & Computational Geometry 25(2): 271-291 (2001)).

Since your rectangles are axis-paralle, the offset distance function will be same as $L\_\infty$ metric. However, you will have trouble at the corners. I think, you will not have much difficulty in using their results. The algorithm presented by them is quite efficient too.
> 3 votes

---
Tags: reference-request, computational-geometry
---


# Question
Title: Why there's a single accepting state in G-NFA's?
It's clear that we can only have a single start state in G-NFA's but I would like to know why we can't have more than one accepting state in G-NFA's.I think it's better to have more accepting states so that we could avoid epsilon transitions.

Is this only a rule that might make conversion of NFA to Regular expressions simpler or is there any specific reason.If this rule makes the conversion simpler could anyone tell the reason behind it.

# Answer
A GNFA (generalized NFA) can have any number of accepting states, just like an ordinary DFA/NFA.

But, as you suspect, the conversion of NFAs to regular expressions is easier if there's only one accepting state. At each step of the conversion algorithm, you remove one state that isn't the start state and isn't the accepting state, and you modify the regular expressions that label the edges of the remaining transitions. The point is that, eventually, you end up with an automaton that has a start state, an accepting state, a single transition between the two and nothing else. The transition is labelled with a regular expression $R$ and the only possible transition from the start state is to reach the accepting state by reading some input that matches $R$. Therefore, $R$ matches exactly the language of the machine.

If you had multiple accepting states, you'd end up with an automaton that had one start state and multiple accepting states. In particular, there could be transitions between different accepting states. That means there's no unique way of reaching an accepting state so it's not at all obvious how to produce a single regular expression that corresponds to the automaton. You'd probably need to use a modified version of the standard algorithm to "crunch" those accepting states down to a single one. But that seems much more complicated than just having a single accepting state and dealing with a few harmless epsilon-transitions.
> 3 votes

---
Tags: finite-automata
---


# Question
Title: Revisiting Fixed Point: What does it mean in the world of computer science?
A while ago I asked Fixed point, what does it mean in the world of computer science?

While the answers did help me to understand what Fixed point meant, the answers left me in a murky world when ever I thought about what a fixed point meant. In other words, no clear definition poped into my mind and I would wonder about in thought trying to match up a definition with what I was trying to learn or understand.

Today I was watching the video Categories for the Working Programmer by Jeremy Gibbons in which he stated: (Time index: 33:00)

> It's fix point because it's the solution of a recursive equation.

And I thought that makes sense; is it really that simple?

So the question is:

Can the definition of fix point be thought of simply as

> "It's the solution of a recursive equation."

# Answer
A fixed point of a function $f$ is an element $x$ satisfying $f(x) = x$. A solution to a recursive equation can be put in that form.
> 4 votes

---
Tags: terminology, recursion
---


title: Why no rotate property in matrix 2d?

text:
# Question
Title: Why no rotate property in matrix 2d?
Why no rotate property in matrix 2D ? we know the short hand code in matrix 2D transform:matrix(a,b,c,d,x,y) a=scale X b=Skew y c=skew X d=scale Y

x=translate X y=translate Y

why developers didn't create extra place for rotation 2D?

# Answer
The 2 x 2 portion of the matrix ($a$, $b$, $c$ and $d$) can represent rotation as well as scaling and skewing. I'd have to see the code to be sure, but if the angle is $\theta$, you would probably set $a$ and $d$ to $cos(\theta)$, $b$ to $-sin(\theta)$ and $c$ to $sin(\theta)$. Put another way, rotation can be constructed as a combination of scaling and skewing.
> 2 votes

---
Tags: algorithms
---


title: Showing undecidability

text:
# Question
Title: Showing undecidability
I'm given the set $T = \\{\langle M, w\rangle : M $ is a Turing Machine that accepts $w^\mathcal R$ whenever it accepts $w \\}$ and I want to show it's undecidable but recognizable. (I'm using the bracket notation to denote the encoding of the TM and input string)

Given that I know the set $A = \\{\langle M,w\rangle : M \text{ accepts } w \\}$ is undecidable but recognizable, I'm trying to show that $A$ reduces to $T$. I start by assuming that $T$ is decided by a Turing Machine $R$ and then attempt to construct a new Turing Machine, $S$, that will decide $A$ by using $R$ as a subroutine.

To construct this new machine $S$, I will run $R$ on input $\langle M,w\rangle$. If $R$ accepts, then $\langle M,w\rangle$ is in $A$. However, $R$ rejecting doesn't necessarily mean that $\langle M,w\rangle$ isn't in $A$, since $M$ might reject $w$ reversed but accept $w$. So now I'm confused on how to actually construct the reduction. Any help would be great

# Answer
> 2 votes
I am interpreting the word "whenever" in the definition of $T$ to mean that $T$ consists of all pairs $\langle M, w \rangle$ such that either $M$ accepts $w$ and $w^R$ or $M$ rejects $w$ and $w^R$. Please, correct me if this is wrong.

I will show a reduction from $A$ to $T$. Input $\langle M, w\rangle$ will be transformed to $\langle M', w'\rangle$ as follows:

1. $w' = 0w1$
2. $M'$ on input $w'$ strips the first bit $b\_1$ and last bit $b\_2$ off $w'$. Let $w$ be the remaining string. If $b\_1 = 0$ then $M'$ runs $M$ on $w$ and outputs accordingly. Otherwise, if $b\_1 = 1$ then $M'$ simply accepts.

I claim that $\langle M, w \rangle \in A$ if and only if $\langle M', w' \rangle \in T$:

* If $M$ accepts $w$ then $M'$ on $0w1$ simulates $M$ on $w$ and accepts. Also, $M'$ on $(0w1)^R = 1w^R0$ immediately accepts, since the first bit is $1$. Thus, $\langle M', w' \rangle \in T$.
* If $M$ doesn't accept $w$ then $M'$ on $0w1$ simulates $M$ on $w$ and doesn't accept. However, $M'$ on $w^R = 1w^R0$ accepts. Thus, $\langle M', w' \rangle \notin T$.

---
Tags: computability, turing-machines, reductions, undecidability, semi-decidability
---


# Question
Title: Does the following modified Two-Phase Locking protocol ensure serializability and freedom from deadlock?
Consider the following variant of the two phase locking protocol. Suppose a transaction $T$ accesses (for read or write operations), a certain set of objects ${O\_1,...,O\_k}$.

The modified algorithm works as :

Step 1. $T$ acquires exclusive locks to $O\_1, . . . , O\_k$ in increasing order of their ids.

Step 2. The required operations are performed.

Step 3. All locks are released.

Does this protocol ensure serializability and freedom from deadlock?

Since the locks are being obtained in an increasing order of their ids, the circular wait condition cannot prevail and a deadlock can thus be avoided. But does it ensure serializability? How to argue with respect to the serialization aspect?

# Answer
The question is not clear about the details, but assuming said resources are *always* locked-then-accessed *sequentially*, then a deadlock is not possible to occur. Since the locks are always obtained in the same order, precedence would prevent any cross-lock scenarios. Once a transaction acquires the lock for the first item in the list, other transactions will have to wait for that lock to be released.

Even if the locks are acquired-released on one-by-one basis, deadlocks would not occur. Supposing 2 transactions **T1** and **T2** are concurring the locks for the resources **A**, **B**, **C**, the sequence of events would be:

1. **T1** acquires **A**
2. **T2** waits **A**
3. **T1** releases **A**
4. **T2** acquires **A**
5. **T1** acquires **B**
6. **T2** releases **A**
7. **T2** waits **B**

Then there's the scenario where **T2** *overtakes* **T1**. In that case nothing would change, T2 would then be the contentious transaction (holding everyone else behind). But no deadlocks.

1. **T1** acquires **A**
2. **T2** waits **A**
3. **T1** releases **A**
4. **T2** acquires **A**
5. **T2** releases **A**
6. **T2** acquires **B**
7. **T1** waits **B**
8. **T2** releases **B**
9. **T2** acquires **C**
10. **T1** acquires **B**

The number of concurrent transactions is not important. Possibly, the great the numbers of transactions concurring, the greater the number of *overtakes*. It would be contentious and some transactions, even though they entered first, could possibly lag way behind other transactions that arrived later. In edge cases, some transactions could give the impression they are deadlocked when in fact they are not (they are just being thrown around by the OS scheduler).

Also, in most (all?) Systems locks are not served on the the same order they are requested. **T1**, **T2**, **T3** could request a lock for the resource **A**, but **T3** could be the first to get it. It's *very likely* the locks will be given in the order they were requested, but it's not guaranteed, especially if the system running the process is already dealing with too many threads. In such cases the OS can reorder the threads, thus changing the order the locks are acquired. No deadlocks still, but some transactions could take abnormally longer than others.

The case you describe (all locks being acquired and released at once) could be even more contentious, and could become a pain in the arse as the load in the system increases - because strange (and often \*un-\*debuggable) things starts to happen.

Still no deadlocks though.
> 2 votes

---
Tags: concurrency, database-theory, deadlocks
---


# Question
Title: Acceptance of empty string by nondeterministic automaton
Why is the input $\epsilon$ accepted by the nondeterministic finite automaton shown below? Does it not leave $q\_1$ and go to $q\_3$?

# Answer
> 6 votes
You're confusing the concept of the empty string $\varepsilon$ with the concept of an $\varepsilon$-transition.

The empty string $\varepsilon$ is just the string with no characters. The presence of a $b$-transition from $q\_1$ to $q\_2$ means that the automaton can move between those two states by reading character $b$ but the presence of an $\varepsilon$-transition from $q\_1$ to $q\_3$ doesn't mean that it moves by reading the character $\varepsilon$. Rather, it means that the automaton *can* (but is not forced to) move from $q\_1$ to $q\_3$ without reading any input at all.

So, when this automaton has no input, it can either remain in state $q\_1$, which is accepting, or move to $q\_3$, which isn't. Since it can reach an accepting state, it accepts.

# Answer
> 3 votes
I think you are asking why the input string $\epsilon$ (the empty string) is accepted by the given NFA. If so, you need to create a set of all states reached by the given string (in this case it is $S=\\{q\_1, q\_3\\}$) and see if an accepting state belongs to this set (in this case - yes: $q\_1 \in S$).

# Answer
> 2 votes
To expand on Denis's answer, the given automata is non-deterministic because it has $\epsilon$-transitions. Because it's non-deterministic, given an input of the empty string $\epsilon$, we don't *have* to follow the transition from $q\_1$ to $q\_3$; we can just stay in $q\_1$, which accepts the string.

---
Tags: finite-automata
---


title: Decidable languages

text:
# Question
Title: Decidable languages
A recursive (decidable) language is defined as a language for which there exists an algorithm deciding if a string is or not in the language that terminates for every possible input.

The question is, does there exist a programming language/grammar/something that is able to represent all and only the algorithms that are a decider? I.e. all the possible programs that terminate, and not others?

# Answer
> 0 votes
Assume we have a programming language $L \subseteq \Sigma^\* $ satisfying the following natural requirements:

1. Programs in $L$ always terminate. I.e., for every program $p\in L$, its semantics $\[\\!\[p\]\\!\] : \mathbb{N}\rightarrow\mathbb{N}$ is a recursive *total* function.
2. There is an effective enumeration of $L = \\{p\_0, p\_1, \ldots\\}$. That is, given $i$ we can compute the program (a source code string) $p\_i$. This essentially requires that the syntax is reasonably regular.
3. The language can be interpreted by a Turing machine. I.e., the function $r(i,n) = \[\\!\[p\_i\]\\!\](n)$ is (total) recursive.

The question then becomes: can $L$ express all the deciders? More formally, given any total $0,1$ valued recursive function $f$, can we always have $f = \[\\!\[p\_i\]\\!\]$ for some natural $i$?

Take the following function: $$ g(n) = \begin{cases} 0 & \mbox{if } r(n,n) \neq 0 \\ 1 & \mbox{otherwise} \end{cases} $$ We have that $g$ can be implemented by a Turing machine, since $r$ is total recursive. Since $g$ is total and returns in $\\{0,1\\}$ said machine is a decider.

Assume by contradiction $L$ can compute $g$, say $g = \[\\!\[p\_i\]\\!\]$ for some $i$. Then, by definition of $g$ and $r$ we have $$ \[\\!\[p\_i\]\\!\](n) = \begin{cases} 0 & \mbox{if } \[\\!\[p\_n\]\\!\](n) \neq 0 \\ 1 & \mbox{otherwise} \end{cases} $$ Now, what happens when $n$ is equal to $i$ ? $$ \[\\!\[p\_i\]\\!\](i) = \begin{cases} 0 & \mbox{if } \[\\!\[p\_i\]\\!\](i) \neq 0 \\ 1 & \mbox{otherwise} \end{cases} $$ So, $\[\\!\[p\_i\]\\!\](i)$ is zero iff it is nonzero -- contradiction.

We conclude that $g$ can not be implemented in $L$.

---
Tags: formal-languages
---


# Question
Title: Select the maximum number of links to satisfy per-link constraint. How to prove is NP-hard?
I asked, **incorrectly**, my previous question here. I would like to thank D.W. for his answer though. He answeres that the problem is polynomial time solvable. The thing is that the cited paper shows that it is NP-hard. So I corrected my question. But I don't understand, am I missing something? In the paper, as shows the figure (page 2, right column in the paper), the authors says:

They show that that problem is NP-hard.

So here is the new question.

*Instance*: A matrix of size $n\times n$ of non-negative real numbers $\mathbf{G}=\left\[g\_{ij}\right\]$, a positive number $k\le n$, and a positive number $\tau$ and a positive number $\epsilon$.

*Question*: Is there a subset $S$ of $\\{1,\ldots,n\\}$ of cardinality $|S|\geq k$ such that

$$\dfrac{g\_{ii}}{\epsilon-g\_{ii}+\sum\limits\_{j\in S}g\_{ij}}\geq \tau,\text{ for all } i \in S.$$

Can you see a simple, direct reduction from an NP-hard problem?

*Note.* This problem is studied in wireless communication where the set represents links in a wireless network, the $g\_{ij}$ represents the powers and the constraint represent a quality of service guarantee.

I believe a more general problem is proven NP-hard, see for example paper, but the reduction is very hard for me.

# Answer
Even when each entry of G is in {0,1}, that is W\[1\]-hard by reduction from independent set:
$\mathbf{G}$  =  adjacency matrix \+ identity matrix    and    $\tau = 2$    and    $0 \< \epsilon \< 1/\hspace{.02 in}2$    .
> 2 votes

---
Tags: np-hard
---


# Question
Title: Proving $A$ avoiding $B$ regular if $A$ and $B$ are regular
Suppose we define an operation such that

$$A \text{ avoiding } B = \\{w \in A \mid w\text{ has no substring in }B\\}\\,.$$

How can I prove that, if $A$ and $B$ are regular then $A\text{ avoiding }B$ is regular too? I know I should either construct a DFA/NFA or use closure properties, but where to start?

What I come up with is that $A = (A\text{ avoiding } B) \cup \\{w \mid w\text{ has a substring in }B\\}$ and then I've tried to prove that $\\{w \mid w \text{ has a substring in }B\\}$ is regular by constructing a DFA for it. That would show that $A \text{ avoiding } B$ is also regular.

# Answer
> 11 votes
Yes you are on right track.

We can first define ($A$ avoids $B$) as ($A$ - ($A$ has $B$)), where ($A$ has $B$) are strings of $A$ which contain strings of $B$ as substrings. Then ($A$ avoids $B$) will be strings of $A$ that do not contain strings of $B$ as substrings.

We can define ($A$ has $B$) as $A \cap (\Sigma^\* B \Sigma^\*)$. Then ($A$ has $B$) are strings of $A$ which contain strings of $B$ as substrings.

Thus you have ($A$ avoids $B$) = ($A - (A \cap (\Sigma^\* B \Sigma^\*))$). Since regular languages are closed under concatenation, intersection, and subtraction they are also closed under operaion *avoid*.

Above relation also gives ($A$ avoids $B$) = $A - \Sigma^\* B \Sigma^\*$ as pointed out by Hendrik Jan.

---
Tags: formal-languages, regular-languages, closure-properties, dfa
---


# Question
Title: Select the maximum number of links to satisfy the constraint on each link. How to prove is NP-hard?
*Instance*: $n$ non-negative real numbers $P\_1,\ldots,P\_n$, a positive number $k\le n$, and a positive number $\epsilon$.

*Question*: Is there a subset $S$ of $\\{1,\ldots,n\\}$ of cardinality $|S|\geq k$ such that

$$\dfrac{P\_i}{\epsilon-P\_i+\sum\_{j\in S}P\_j}\geq 1,\text{ for all } i \in S.$$

Can you see a simple, direct reduction from an NP-hard problem?

*Note.* This problem is studied in wireless communication where the set represents links in a wireless network, the $P\_i$ represents the powers and the constraint represent a quality of service guarantee.

I believe a more general problem is proven NP-hard, see for example here, but the reduction is very hard for me.

# Answer
> 1 votes
This problem can be solved in polynomial time. Therefore, it's likely not NP-hard (unless P = NP).

After a little bit of algebraic manipulation, we find that the condition on $S$ is equivalent to requiring that

$$2 P\_i \ge \varepsilon + \sum\_{j \in S} P\_j \quad \text{for all $i \in S$}.$$

This, in turn, is equivalent to requiring

$$2 \min \\{P\_i : i \in S\\} \ge \varepsilon + \sum\_{j \in S} P\_j.$$

For convenience, sort the $P\_i$'s into increasing order, so $P\_1 \le P\_2 \le \dots \le P\_n$.

Now one can prove that if there is any set of cardinality $k$ that satisfies this equation, then there's a set of the form $S = \\{t,t+1,t+2,\dots,t+k-1\\}$ that satisfies this equation, for some $t$. (This can be proven using an exchange argument, swapping pairs of indices as needed and showing that the swap leaves the left-hand side unchanged and only decreases the right-hand side.)

Now you can try all possible values of $t$ and see whether the corresponding set satisfies the condition. There are only $n$ possible values of $t$, so this can certainly be tested in polynomial time. In fact, with clever programming (prefix sums, etc.), you can implement this in $O(n \lg n)$ time, or in $O(n)$ time if the $P\_i$'s are already provided in sorted order.

---

More generally, if you want to find the set $S$ of maximum cardinality that satisfies the equation, such a set will have the form $S=\\{t,t+1,t+2,t+3,\dots,u\\}$ for some $t,u$. Therefore, you can try all such possibilities and see which has largest cardinality. This too can be done in $O(n \lg n)$ time using appropriate methods (binary search, prefix sums). Alternatively, you can do binary search on $k$, and apply the decision algorithm of the previous paragraph for each candidate value of $k$ to find the largest $k$ for which a solution exists. The running time is again $O(n \lg n)$.

# Answer
> 1 votes
In equation $\dfrac{P\_i}{\epsilon-P\_i+\sum\_{j\in S}P\_j}\geq 1,\text{ for all } i \in S.$, and positive $\epsilon \> 0$ we can never have $k \geq 2$. Even in the case $k=2$ either $2P\_1 \< \epsilon + P\_1 + P\_2$ or $2P\_2 \< \epsilon + P\_1 + P\_2$.

And for $k = 1$ every subset is a yes-instance for small enough $\epsilon$.

So the problem is trivially polynomial.

---
Tags: np-hard
---


# Question
Title: Single-source shortest paths as a linear program
I saw that I can formulate single-source shortest path as the following linear program:

Given $G=(V,E)$ and $w\colon E\to R$ and with negative cycles, find $\max\\,d(s,t)$ such that

\begin{align\*} d(s,v) &\le d(s,u)+w(u,v) \quad \forall (u,v)\in E \\ d(s,s) &=0 \end{align\*}

We want to find the shortest path from $s$ to $t$ so we are we maximizing $d(s,t)$?

# Answer
What you have here is a dual formulation of the problem (not the standard one, but an equivalent one). According to strong duality, both the optimal primal and the optimal dual problem have the same objective value (i.e., the shortest path distance from $s$ to $t$). The constraints of the dual problem are then the optimality criteria of the shortest path problem. Note that you can obtain the actual shortest path by finding any $s$-$t$-path in the subgraph that is induced by the edges for which the corresponding dual constraint is tight.

By the way, there is a neat interpretation of this formulation: For each edge $(u,v)$, consider a string with length $w(u,v)$ and tie the ends of these strings together at the corresponding nodes they share. If you put the knot for $s$ and the knot for $t$ as far away from each other as possible, you will end up with several tight strings, which then describe the shortest path.
> 2 votes

---
Tags: graphs, linear-programming
---


# Question
Title: A Shortest Path Strange Formulation, or new modeling?
We have a directed Graph $G=(V,E)$ with vertex set $V=\left\\{ 1,2,...,n\right\\}$. weight of each edge $(i,j)$ is shown with $w(i, j)$. if edge $(i,j)$ is not present, set $ w(i,j)= + \infty $. For each vertex $i$ put $w(i,i)=0$. we want using Dynamic Programming to find shortest path between any two vertex in this graph. by using which of them following recursive relation $d\[i,j,n\]$ is equal to shortest path among vertexes $i$ and $j$?

$I)$ $d\[i,j,k\]=\begin{cases}w(i,j) & k=1\\ \min\_{1 \leq r \leq n} \left\\{ d\[i,r,k-1\] +w(r,j) \right\\}& k\>1 \end{cases}$

$II) d\[i,j,k\]=\begin{cases}w(i,j) & k=0\\ \min \left\\{ {d\[i,j,k-1\],d\[i,k,k-1\]+d\[k,j,k-1\]}\right\\} & k\>0 \end{cases}$

$III) d\[i,j,k\]=\begin{cases}w(i,j) & k=1\\ \min\_{1 \leq r \leq n} \left\\{ {d\[i,r,\lfloor k/2\rfloor \]}+d\[r,j, \lceil k/2\rceil \] \right\\} & k\>1 \end{cases}$

> This is an exam on 2011 that solution is wrote all of them. Who Can Help this confusing question better understood?

# Answer
> 2 votes
Solution I) is recursive definition where $k$ is number of links. This formulation comes from same as Bellman-Ford-Moore algorithm.

Solution II) is recursive definition where $k$ is an intermediate node. $d\[i,j,k\]$ is length of shortest path from $i$ to $j$ involving only $1..k$ as intermediate nodes. This formulation comes from Floyd Warshall algorithm.

Solution III) is recursive definition where $k$ is again number of links. I) and III) will give same value for $d\[i,j,k\]$. (See Shortest Paths)

Final solution will be $d\[i,j,n\]$ for every case.

---
Tags: algorithms, graphs, data-structures, trees, shortest-path
---


# Question
Title: Question on interpreting logical notation, relating to alphabets, theoretical comp sci
$\exists x \in \Sigma^\* (t=sx)$

Have I interpreted the above into words correctly?:

"There exists a symbol 'x', which is a member of the set which contains all possible strings of alphabet sigma, where sigma contains string 't', which is a concatenation of string x and string s."

I'm not clear on how/whether t=xs is an alphabet.

Note: an earlier version of this question, with some errors, was posted at Math.SE.

# Answer
> 2 votes
Since $t$ and $s$ aren't quantified, the expression $\exists x\in\Sigma^\*\\;(t=sx)$ is a predicate $P(s, t)$ in inputs $t$, and $s$. In other words, we could write $$ P(s, t)\stackrel{\text{def}}{\equiv}\exists x\in\Sigma^\*\\;(t=sx) $$ meaning "$P(s, t)$ is true if and only if there is a string $x$ over $\Sigma$ for which $t$ is the concatenation of $s$ and $x$". In answer to your question, $t=sx$ isn't an alphabet, but is a *condition,* namely that $t$ (a string) can be expressed as the string $s$ followed by the string $x$.

Look at some examples, with $\Sigma = \\{a,b\\}$,

1. Is $P(a, abb)$ true? It is if we can find a string $x$ such that $abb=ax$. Obviously $x=bb$ works here, so $P(a, abb)$ is true.
2. Is $P(ba, abb)$ true? It is if we can find a string $x$ such that $abb=bax$. There's no $x$ we can use here, so $P(ba, abb)$ is false.

In general, it's not hard to see that $P(s,t)$ can be interpreted as "$s$ is a prefix of $t$".

---

In a different universe of discourse, if $s, t, x$ were integers, can you see that $\exists x\in\mathbb{N}\\;(t=sx)$ would mean that $s$ divides $t$?

---
Tags: logic, notation
---


# Question
Title: Unconditional arithmetic circuit lower bounds for permanent/determinant
In this http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.12.1090&rep=rep1&type=pdf an unconditional lower bound (provided constants used are bounded by absolute value smaller than $1$) of $\Omega(n^2\log n)$ for size of arithmetic circuits computing $n\times n$ Matrix Multiplication is given.

What is the best unconditional lower bound for size of arithmetic circuits computing $n\times n$ Matrix Determinant and Permanent along similar lines?

# Answer
Kalorkoti gave an $\Omega(n^3)$ lower bound on arithmetic formulas for the determinant and permanent. As far as I know, nothing is known for unrestricted circuits.
> 1 votes

---
Tags: complexity-theory, circuits
---


# Question
Title: Probability bounds on size of smaller partition in randomized quicksort
Let $0 \< a \< 0.5$ be some constant. We have an $n$-element array as input. Randomized quicksort chooses one element from array uniformly at random as a pivot and partitions. With probability $1-2a$ the smallest section be greater than $an$. How we can Calculate this probability? after 72 hours try i reach to following that means valid area is (1-a)n-an=n(1-2a). by dividing n(1-2a)/ n we get 1-2a.

# Answer
> 2 votes
Suppose for simplicity that all elements are distinct, and that after sorting, these elements are $x\_1,\ldots,x\_n$. A random pivot has the same distribution as $x\_i$ for $i$ chosen uniformly at random from $\\{1,\ldots,n\\}$. The size of the smaller partition is $\min(i-1,n-i)$. If $I$ is the set of indices $i$ such that $\min(i-1,n-i) \geq an$, then the probability you are looking for is $|I|/n$ (by the definition of uniform probability). I'll let you complete the calculation.

---
Tags: algorithms, sorting, probability-theory, probabilistic-algorithms, quicksort
---


# Question
Title: what is the difference between memory access and data memory access?
what is the difference between **memory access** and **data memory access**?

for example, here are the examples of register transfer language instructions:

* $R1 ←\[18\]$
* $R2 ←\[R1 +3\]$
* $R1 ← R1 +2$
* $\[8\] ← R1$

From my understanding, **memory access** is where load/store occurs, like these instructions - $R1 ←\[18\]$
- $R2 ←\[R1 +3\]$
- $\[8\] ←R1$

But what about **data memory access**? what is it?

thanks!

# Answer
> 1 votes
A **memory access** happens when the CPU loads bits from main memory or stores bits to main memory. The CPU will first check to see if it can load the bits from a cache, in which case it will skip the (slow) memory access entirely.

One kind of memory access is a **data memory address**, when the CPU runs an instruction that explicitly loads or stores data from/to memory. In your examples, the arrows request data memory accesses (or cache accesses). "Data" is a very general term but here it means the bits that the program is operating on, as distinct from the bits that convey the program itself.

Another kind of memory access is an **instruction fetch**, which happens when the program counter gets a new value as part of running the instructions in the program. It usually just steps forward but a branch instruction can jump to a new location. Either way, no memory access is needed when the instructions are already cached.

In your example, the sequence of register/memory instructions have to load into the CPU before it can execute them. That requires instruction fetches.

(A Harvard architecture CPU has one bus to/from data memory and a second bus to/from instruction memory, so it can fetch from both in parallel. In that case the distinction between an instruction fetch and a data fetch is starker.)

The instructions themselves had to get into memory somehow. An interpreter or loader put them there, treating those instructions as data.

The distinction is whether the data is loading by the explicit request of the program instructions vs. the implicit need to load instructions themselves. The former are easier to cost out. The latter costs depend on the size of the instruction caches, on interruptions taken that might spill this program's instructions from the cache, etc.

---
Tags: computer-architecture, memory-access
---


# Question
Title: Checking my understanding of right quotient
So I am trying to fully understand the concept of quotient languages.

I will give some examples, let me know if this is correct: Say that

```
L1={} and L2 is {ot}, then L1/L2 is {carr}
Or if L1=ab*c and L2 is b*c then L1/L2 is a.

```

If this is it, I will then try to approach more complex concepts :) Thank you!

# Answer
If $L\_1=ab^\*c$ and $L\_2$ is $b^\*c$ then $L\_1/L\_2$ is $ab^\*$.

Note that the $b$'s are not forced to disappear. For instance (as part of these languages) $\\{ab^{10}c\\}/\\{b^3c\\} = \\{ab^7\\}$.
> 1 votes

---
Tags: regular-languages
---


title: (a,b)-tree vs B-tree

text:
# Question
Title: (a,b)-tree vs B-tree
I would like to know what are the differences between *(a,b)-tree* and a *B-tree*. It has been a few days I am studying different papers and I am seeing different definitions that make me confused.

For example in External Memory geometric Data Structure by *Lars Arge* on Page 3 he says

> Normally, the *N* data elements are stored in the leaves (in sorted order) of an (a; b)-tree T , and elements in the internal nodes are only used to guide searches.

So the *N* data elements are stored in the leaves and internal nodes are only used to guide searching, they don't contain any data element other than the leaves. While in *B-tree*s it is not so, In *B-tree* internal nodes contain their own different elements and every element of an internal node is used as a separator of its children. In fact it is a data element that is moved up. Like this

But from (a,b) Trees, it says

> A *B-Tree* is a *(a,b)-tree* with *a = ceil(b/2)*.

Which is in contradiction with the structure of internal nodes, Furthermore it shows that internal nodes have different elements than the leaves and all of the elements are not stored in the leaves. They may be stored in the internal nodes as well. In the *insertion* phase, some of the elements of the nodes are moving up to the parent as the separator.

I would like to know what are the elements in the internal nodes of *B-trees* and *(a,b)-trees*?

Thanks in advance.

# Answer
It seems you are right. The author probably takes as a standard definition the B+-tree where internal nodes are used as separators.

You should always be prepared for authors that deviate from standard definitions and naming conventions!
> 1 votes

---
Tags: data-structures, trees, big-data
---


title: Maximum frequency in any row and column

text:
# Question
Title: Maximum frequency in any row and column
I have been given 2D matrix with some elements. I want to find out what is maximum frequency in any row and column.
Example:
1 2 1 2
3 4 1 2
1 1 1 1
2 2 2 2
Maximum frequency is 6 which occurs in last row and last column of matrix.
Constraints
No. of rows X No. of columns \<= 10^6
1\<=Elements in Matrxi \<= 10^6
**My approach**
Firstly, I have calculated frequency of a number in each row and each column
Travel row wise. Let x be element we are searching, a=frequency\[x\] in this row. Then loop for each column, b=frequency\[x\] in that column.
ans=max(ans, a+b)
Complexity of above code is O(nm^2) where n is no. of rows and m is no. of columns.
I am looking for better complexity.

# Answer
> 0 votes
$O(nm \log (m+n))$ should not be difficult. Insert all elements in a rows and columns in height balanced search trees (one each for each row and each column) which also keep the frequencies. Now for each row and column just search the number in corresponding row search tree and column search tree and add the frequencies. Then compute the minimum of this sum.

---
Tags: algorithms, data-structures, matrices
---


# Question
Title: regular expression to accept all strings other than one containing ads or adlib
My intention is to select only those packages whose name do not contain adlib or ads. But if i add `*adlib* and *ads*` it selects all packages containing the substring adlib and ads. So i need a regular expression to select all packages that do not contain substring adlib and ads.

# Answer
> 2 votes
Let $\[$^$x\]$, $\[$^$xy\]$ be short cuts for $\Sigma - \\{x\\}$, $\Sigma - \\{x, y\\}$ etc., i.e., $\[$^$a\]$ will be regular expression: $(b+c+d+\dots)$.

Then the regular expresseion for words not containing ads or adlib would be

$\[$^$a\]^\*(a\[$^$d\]\[$^$a\]^\*+ad(\[$^$sl\]\[$^$a\]^\* $ $+ adl\[$^$i\]\[$^$a\]^\* + adli\[$^$b\]\[$^$a\]^\*)^\* (\epsilon + a +ad + adl + adli)$.

Basically we wait for an $a$ and then check it is not followed by the disallowed combinations.

Since regular expressions have built in operators for union, kleene and concatenation only, we will always have trouble with intersection, complement and minus operations. Basically the operation you want in your question is the complement.

---
Tags: formal-languages, regular-expressions, dfa
---


title: How to show ExactOneSAT is NP-Complete?

text:
# Question
Title: How to show ExactOneSAT is NP-Complete?
$\text{ExactOneSAT}= \\{\phi\\;|\\;\phi\\; \text{is a boolean formula}$ $\text{ such that it has a satisfying assignment with only one true literal per clause} \\}$

I am trying to reduce 3SAT to this problem but can't find a way. I tried taking a small example $\phi=(x\_1 \vee x\_2) \wedge (\overline{x\_1} \vee x\_2 ) $. In this example the formula can only be satisfied only when both $x\_1,x\_2$ are True. How do I reduce such a case of 3SAT to ExactOneSAT ?
This is an exercise from Sanjeev Arora and Barak Boaz : A modern approach to complexity, but not a homework exercise.

# Answer
> 8 votes
We can reduce 3SAT to ExactOneSAT (3SAT $\leq\_P$ ExactOneSAT) as follows. Replace each clause $C\_m$ by $(z\_{m,1} \lor z\_{m,2} \lor z\_{m,3})$ and ensure that if $C\_m$ is, say, $(v\_i \lor \overline{v\_j} \lor v\_k)$ then $(\neg v\_i \Rightarrow \neg z\_{m,1})$, $(\neg \overline{v\_j} \Rightarrow \neg z\_{m,2})$ and $(\neg v\_k \Rightarrow \neg z\_{m,3})$. Thus, for example, if $v\_i$ is true then $z\_{m,1}$ can be true or false, but if $v\_i$ is false then $z\_{m,1}$ must be false.

Thus replace $(X\_{m}^1 \lor X\_{m}^2 \lor X\_{m}^3)$ in clause $C\_m$ by
$$(z\_{m,1} \lor z\_{m,2} \lor z\_{m,3}) \land (\neg X\_{m}^1 \lor y\_{m,1} \lor z\_{m,1}) \land ( \neg X\_{m}^2 \lor y\_{m,2} \lor z\_{m,2}) \land ( \neg X\_{m}^3 \lor y\_{m,3} \lor z\_{m,3})$$
where $X^1\_m, X^2\_m, X^3\_m$ are the three literals in the clause $C\_m$. Note that $X$'s are literals in the clauses and can have negations, whereas $y$'s and $z$'s are variables.

If $\phi'$ is the modified boolean CNF, then this will give us $\phi \in$ 3SAT iff $\phi' \in $ ExactOneSAT. This along with the fact that above transformation is polynomial-time gives us a proof of NP-completeness.

Let us see how $\phi \in 3SAT \Rightarrow \phi' \in$ ExactOneSAT.

Assume we have a satisfying assignment for $\phi$.

For example, say $X\_m^1$ is true and $X\_m^2$ and $X\_m^3$ are false. Then we can make following assignments:

$y\_{m,1}$ = False, $z\_{m,1}$ = True
$y\_{m,2}$ = False, $z\_{m,2}$ = False
$y\_{m,3}$ = False, $z\_{m,3}$ = False

For example, say $X\_m^1$ and $X\_m^2$ are true and $X\_m^3$ is false. Then we can make following assignments:

$y\_{m,1}$ = False, $z\_{m,1}$ = True
$y\_{m,2}$ = True, $z\_{m,2}$ = False
$y\_{m,3}$ = False, $z\_{m,3}$ = False

For example, say all $X\_m^1$, $X\_m^2$ and $X\_m^3$ are true. Then we can make following assignments:

$y\_{m,1}$ = False, $z\_{m,1}$ = True
$y\_{m,2}$ = True, $z\_{m,2}$ = False
$y\_{m,3}$ = True, $z\_{m,3}$ = False

So we can see that we can find a satisfying assignment for $\phi'$ where only one literal is true in every clause.

Let us now see how $\phi' \in$ ExactOneSAT $\Rightarrow \phi \in $ 3SAT

Assume we have a satisfying assignment for $\phi'$ where exactly one literal is true in every clause.

Let us say $z\_{m,1}$ is true and $z\_{m,2}$ and $z\_{m,3}$ are false. Then definitely $X\_m^1$ in the second clause should be true, implying that same assignment satisfies $C\_m$.

Thus we have $\phi \in$ 3SAT iff $\phi' \in $ ExactOneSAT.

We have actually prove ExactOne3SAT is NP-complete by this because every clause has 3 literals.

---
Tags: complexity-theory, np-complete, satisfiability, 3-sat
---


# Question
Title: What is the Big Theta of $(\log n)^2-9\log n+7$?
How can I find the Big Theta of $(\log n)^2-9\log n+7$?

I thought of $(\log n)^2-9\log(n)+7 \< c\_1(\log n)^2 +7$ or something like this and can't find the right way.

# Answer
There is no such thing as "the" big $\Theta$ of a function. For a given function $f(n)$, many functions $g(n)$ satisfy $f(n) = \Theta(g(n))$. For example, every function satisfied $f(n) = \Theta(f(n))$.

However, usually we are interested in a "succinct", "canonical" or "simple" expression $g(n)$, for example of the form $c^n n^a (\log n)^b$, for some $c \geq 1$. In your case $g(n) = (\log n)^2$: your function is $\Theta((\log n)^2)$, which is not too hard to show.

Setting the proof apart, how do I know that your function is $\Theta((\log n)^2)$? Since $(\log n)^2$ is the dominant term: all other terms ($\log n$ and $1$) grow slower than $(\log n)^2$. The constants in front of them don't matter asymptotically.
> 5 votes

# Answer
Hint: what is the answer for $n^2-9n+7$ ?
> 2 votes

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


title: Understanding Murmur3

text:
# Question
Title: Understanding Murmur3
The Bloom filter data structure requires a set of hashing functions. The Murmur3 family is a great fit, as it contains the `seed` parameter to easily create a variety of different functions (plus it has good distribution of values and adequate speed).

### Choosing the `seed`

Is there any particular method of choosing the `seed` values for the Bloom filter application? By selecting them randomly, I give up the deterministic nature of the algorithm and hand-picking these values seems a little bit too brave. Is it known, whether two `seed` values `s1` and `s2`, where `s1 != s2`, yield the same function (borrowing a linear algebra term: they would be linearly dependent) ?

### Limiting the hash domain

The Murmur3 hash is a 32-bit value. Since the Bloom filter might not need all 32 bits, is it still OK with respect to the uniformity to just apply the modulo function to this value?

# Answer
You have asked two questions. I will answer them one by one.

**Choosing the seed.** The usual approach here is to choose the seeds randomly *once and for all*, and to hard-code them. If the hash family is reasonable, then all small sets of seeds should look "the same". I don't know the Murmur3 family, but it's probably reasonable enough.

Note that linear dependence is not the correct measure here — you want a $k$-tuple of hash values generated from $k$ different seeds to look like a random $k$-tuple of values, either statistically or computationally. Linear dependence is just one possible wrong thing that could happen.

**Limiting the hash domain.** If the modulus isn't a power of 2 then the resulting value wouldn't be uniform, but usually it will be "close enough" to uniform, particular with respect to the performance of a Bloom filter. Indeed, it is standard practice to generate a random number in a range $\\{0,\ldots,m-1\\}$ by taking a random 32-bit or 64-bit value modulo $m$.

In the specific case of Bloom filters, if you know that every value in $\\{0,\ldots,m-1\\}$ appears with probability in the range $\[c/m,C/m\]$ then you can adjust the analysis of the Bloom filter to see what you get. You can then calculate $c,C$ in your case (exercise) and choose parameters for the Bloom filter accordingly. You will probably find out that in most cases the parameters you get by assuming $c=C=1$ are very close to the ones that you get by taking into account the actual $c,C$.
> 4 votes

---
Tags: hash, bloom-filters
---


# Question
Title: Elimination rule for the equality type aka J axiom
I'm implementing a interpreter for lambda calculus, and now I want to add the equality type. The introduction rule for it is easy, but the elimination rule is rather obscure for me. I found this stackoverflow thread, but it explains the J axiom only in one sentence. How can it be understood intuitively?

# Answer
> 8 votes
A complete understanding of what `J` was actually saying and why has only come fairly recently. This blog post discusses it. While thinking in terms of homotopy and continuous functions provides a lot of intuition and connects to a very rich area of mathematics, I'm going to try to keep the discussion below at the logical level.

Let's say you axiomatized equality types directly (these are groupoid operations and laws): $$\frac{\Gamma\vdash x:A}{\Gamma\vdash \mathbf{refl}\_x : x=\_A x} \qquad \frac{\Gamma, x:A, y:A\vdash p : x=\_A y}{\Gamma, x:A, y:A\vdash p^{-1} : y =\_A x} \qquad \frac{\Gamma, x:A, y:A\vdash p : x=\_A y \quad \Gamma,y:A, z:A\vdash q : y=\_A z}{\Gamma, x:A, y:A, z:A\vdash p\cdot q : x =\_A z}$$ $$(p^{-1})^{-1} \equiv p \qquad p\cdot p^{-1} \equiv \mathbf{refl} \qquad (p\cdot q)^{-1} \equiv q^{-1}\cdot p^{-1} \\ \mathbf{refl} \cdot p \equiv p \equiv p \cdot \mathbf{refl} \qquad (p \cdot q) \cdot r \equiv p \cdot (q \cdot r)$$ We have substitution which is functorial. $$\frac{\Gamma, z : A\vdash F(z) : \mathbb{U}\qquad\Gamma,x:A,y:A\vdash p : x=\_A y}{\Gamma, x:A,y:A\vdash \text{subst}(F,p) : F(x) \to F(y)}$$ $$\text{subst}(F,\mathbf{refl}) = \text{id} \quad \text{subst}(F,p\cdot q) = \text{subst}(F,q)\circ\text{subst}(F,p)\\\text{subst}(\lambda x.c=\_A x,p)(q) = q\cdot p$$ Finally, we would have congruence rules for everything, saying everything respects this equality. Here is one of the most important congruences. $$\frac{\Gamma, x:A, y:A\vdash p : x=\_Ay \quad \Gamma,z:A\vdash B(z) : \mathbb{U}}{\Gamma, x:A, y:A, b : B(x)\vdash \text{lift}\_B(b,p) : \langle x,b\rangle =\_{\Sigma x:A.B(x)}\langle y,\text{subst}(B,p)(b)\rangle}$$

Now let's consider a special case of substitution. $$\frac{\Gamma\vdash c:A \quad \Gamma,t:\Sigma x\\!:\\!A.c=\_Ax\vdash C(t):\mathbb{U} \quad \Gamma\vdash b : C(\langle c,\mathbf{refl}\_c\rangle)}{\Gamma,y:A,p:c=\_Ay\vdash\text{subst}(C,\text{lift}\_{\lambda z.c = z}(\mathbf{refl}\_c,p))(b) : C(\langle y,p\rangle)}$$

This is `J`. We can use currying to get the nicer looking form:

$$\frac{\Gamma\vdash c:A \quad \Gamma, y:A, p : c=\_A y \vdash C(y,p): \mathbb{U} \quad \Gamma\vdash b : C(c,\mathbf{refl}\_c)}{\Gamma, y:A,p : c=\_A y\vdash J\_{A,c}(C,b,y , p) : C(y,p)}$$

Of course, if we start with `J` we can rederive all the other structure I defined.

Now if we have $p : x =\_A y$ and $q : y =\_A y'$ then $\text{lift}\_{\lambda z.x=z}(p, q) : \langle y,p\rangle = \langle y',p\cdot q\rangle$. So if we have $\langle y', p' \rangle$, there's no way to get to it from $\langle y,p\rangle$ via a pre-selected $q$ in general unless $p \cdot q = p'$. (From the homotopy perspective, $p \cdot q = p'$ says we can fill in the triangle with edges $p$, $q$, and $p'$.) To make it more blunt, set $p = \mathbf{refl}\_x$ (and $y=x$) and we get $q = p'$ being the required equality which is not true in general (because a value of type $x =\_A y'$ can represent an arbitrary equivalence and there's nothing saying two equivalences have to be the same, or, equivalently, because we know groupoids can be non-trivial). The point of this is to demonstrate that things can be equal in more than one way, i.e. one value of $y = y'$ is not as good as another in general.

A key thing to understand is that `J` says the type $\Sigma y\\!:\\!A.x=\_Ay$ is inductively defined, and says little about the type $x=\_Ay$ for fixed $x$ and $y$. One way to see this, and why `J` is the way it is, is to look at what congruence at equality types with matching endpoints looks like. We have the following rule (ignoring the proof term, it's expressible with $\text{subst}$ or `J`): $$\frac{\Gamma, x:A\vdash p : x=\_Ax}{\Gamma, x:A, q : x =\_A x\vdash \\\_ : q =\_{x=\_Ax} p \cdot q \cdot p^{-1}}$$ With $\text{lift}\_{\lambda z.x=z}$ we have the option of doing $\text{lift}\_{\lambda z.x=z}(p, p^{-1}\cdot p') : \langle y,p\rangle = \langle y',p'\rangle$ so every point was equivalent to every other point (though not necessarily trivially). With both endpoints matched, we don't have the flexibility of choosing the equalities to first cancel out the input equality and then performing an arbitrary equality.

While `J` carefully respects the non-trivial groupoid structure of equality types, in typical dependently typed languages there's no way to actually define a non-trivial element of an equality type. At this point you hit a fork in the road. One route is to add Axiom K which says that the groupoid is actually trivial which makes many proofs much simpler. The other route is to add axioms that allow you to articulate the non-trivial groupoid structure. The most dramatic instance of this is the Univalence Axiom which leads to Homotopy Type Theory.

---
Tags: lambda-calculus, intuition, equality
---


# Question
Title: What is the time complexity of checking if a number is prime?
Could some one please explain how to get the time complexity of checking if a number is prime? I'm really confused as to if it is $O(\sqrt{n})$ or $O(n^2)$.

I iterate from $i=2$ to $\sqrt{n}$ and continuously checking if `n%i != 0`.

However, do we consider the complexity of the square root function also?

If we do, the Newtons method for finding square roots has a complexity of $n^2$.

# Answer
> 12 votes
When $n$ is the input, we test $\sqrt{n}$ divisors. However, we also have to take into account the complexity of division itself. For a number with $b$ bits, this takes $O(b \log b \log\log b)$ operations, when we are using the Schönhage–Strassen algorithm. Since half of the numbers below $\sqrt{n}$ have $\log(\sqrt{n})$ digits, we may assume the all have this amount of digits. It only matters a factor $\frac12$ at most, and that is absorbed in the $O$.

This gives a computational complexity of $O( \sqrt{n} \log \sqrt{n}\log(\log(\sqrt{n}) ) \log\log(\log(\sqrt{n}) )))$. We can simplify this to $O( \sqrt{n} \log(n) \log(\log(n) ) \log(\log(\log(n) )))$.

However, when notating it using the number of bits $b$ of a number, which is more standard usage, we get a computational complexity of $O(2^{b/2} b \log b \log\log b)$.

You also need to compute $\sqrt{n}$ but that has only complexity $O(b \log b \log\log b)$ when using Newton's method and the Schönhage-Strassen algorithm.

---

However, this is not optimal. The current best algorithm, the AKS algorithm, reaches a complexity of less than $O(b^{7})$ worst-case , which is much faster. <sub>(To be precise, even $O(b^{6+\varepsilon})$ for any $\varepsilon\>0$ has been shown, but that is more complicated than it needs to be for this answer.)</sub>

# Answer
> 2 votes
A recent famous result is that checking if a number of $n$ bits is prime can be done in time polynomial in $n$, see the AKS test (it's somewhat heavy going).

---
Tags: complexity-theory, time-complexity, primes
---


# Question
Title: Sum of Maximum of continuous blocks of length k
Given a array of N elements and a number k, then find the sum of maximum of a all continuous blocks of length k?

Examples :

1. A = {2,5,2}, k = 2, Max for 1st block = 5, 2nd block = 5, So sum is 10.
2. A = {3,1,8}, k = 2, Max for 1st block = 3, 2nd block = 8, So sum is 11.
3. A = {2,5,2}, k = 1, Max for 1st block = 2, 2nd block = 5, third block = 2. So sum is 9.
4. A = {2,5,2}, k = 3, Max for only block = 5. So sum is 5.

# Answer
> 1 votes
For an appropriate data structure $D$, which maintains the last $k$ elements, it is natural to consider the following solution:

1. Initialize $D$ with $A\_1,\ldots,A\_k$, and initialize the sum $S$ with $\max D$.
2. For $i=k+1,\ldots,n$:

1. Remove $A\_{i-k}$ from $D$.
    2. Add $A\_i$ to $D$.
    3. Add $\max D$ to $S$.
3. Return $S$.

The data structure has to support three kinds of operations:

* Adding an element.
* Removing an element.
* Calculating the maximum.

I'll let you figure out what data structure is most suitable, and what is the resulting complexity.

# Answer
> 0 votes
If you want *all* sums separately, just add up the first $k$ elements, for the next stretch add the $k + 1$-st and subtract the first, and keep going adding the next and subtracting the first one.

---
Tags: arrays, maximum-subarray
---


# Question
Title: Matrix permanent, #P-hard problems and NP
First of all, I'm not a computer scientist so I apologize if this is a stupid question.

I know that the problem of computing the permanent of a matrix is #P-hard, which as I understand it this implies that if you can solve an arbitrary instance of the problem in polynomial time then you can in principle solve any problem in #P in polynomial time.

What I'm wondering is if it also implies being able to solve NP problems in polynomial time (I'm guessing not).

# Answer
> 2 votes
Let's take SAT, the quintessential NP-complete problem, as an example. An instance of SAT is a formula, and the answer is whether the formula is satisfiable. The corresponding #P-hard problem #SAT is instead to count the number of satisfying assignment. Clearly if you can count the number of satisfying assignments then you can tell whether one exists. In particular, if you can solve #SAT in polynomial time, you can solve SAT in polynomial time.

This shows that if some #P-hard problem can be computed in polynomial time, then all problems in NP can also be solved in polynomial time.

---
Tags: complexity-theory
---


# Question
Title: Ways to perform "batch" Approximate Member Queries efficiently
In this problem, I'm first given `n` number of values which I have to store in a space efficient manner. Then I'm given `m` number of values which I have to check if they were added to the data structure before (such that after the operation, I know which value was a member, and which weren't).

I could use a Bloom Filter and simply iterate through `m`, but because `m` is considerably large, I wanted to see if there are more efficient ways. One potentially exploitable property of the data is that most values will not be present. I'm thinking I could construct an "aggregated query" which tells me if any of the value is present or not in one operation, and do something like a binary search, but wanted to see if there is already something out there.

Some additional details:

* I can tolerate both false positives and false negatives (with predictable error rate)
* `n` is very large (trillions)
* `m` is considerably large (millions)
* Only very few values in `m` will be members (ca. 1 in 100K)
* The data structure can be immutable (no need for frequent writes)

# Answer
> 3 votes
If the query results are mostly false, the answer will be returned in $O(1)$ on average. (In traditional Bloom filters, negative results are faster than positive ones.)

This might be slow, however, since the lookups are random and have bad cache behavior. There are a few ways to fix this.

I'd suggest:

1. Use a blocked bloom filter (from Cache-, Hash- and Space-Efficient Bloom Filters) in which each item is mapped to a single cache-line-sized Bloom filter.
2. With the hash function that is used to map each item to a cache-line-sized Bloom filter, sort your queries in hash-value order.
3. Do the queries as usual, but in order.

Another approach is:

1. Use a split bloom filter, in which instead of setting $k$ values from a single array on each insert, set one value from each of $k$ arrays on insert.
2. After doing the inserts, use your first hash function to sort the values you wish to query in hash value order.
3. Query the first of your $k$ arrays for these values. Only a constant fraction will remain - $O(m)$ will be eliminated.
4. Take the remainder and repeat the last two steps, but using the second hash function, and the second bit array. Repeat $k$ times.

Sorting is expensive in internal memory, but it might be cheaper than all the random accesses. It depends on your machine and your data sizes.

---
Tags: data-structures, approximation, probabilistic-algorithms, bloom-filters
---


# Question
Title: Counting all $x,y,z$ such that $a[x] > a[y] + a[z]$
Given an array $a$, I want to count all triplets of indices $x,y,z$ such that $a\[x\] \> a\[y\] + a\[z\]$.

I can think of two solutions:

1. Go over all triplets of indices $x,y,z$ directly. This takes time $O(n^3)$ and constant space.
2. Compute a new array consisting of all sums $a\[y\]+a\[z\]$, sort it, and then go over all $x$ and use binary search. This takes time $O(n^2\log n)$ and space $O(n^2)$.

Is it possible to improve on these solutions?

# Answer
Let me try to sketch a method that counts the triplets by directly counting. Let me first assume that $a$ is sorted. I will also keep $x$ constant for this exposition (and iterate over $x$). For simplicity take $a\[x\]=0$, so the task is to count $(y,z)$ such that $a\[y\]+a\[z\]\<0$. We can count the pairs, but not by going over all $n^2$ of them, but by following the "boundary" between negative and positive pairs. This is like counting the number of negative elements in a two dimensional array that is increasing in both dimensions. This seems to be possible in linear time? (for fixed $x$)

As an example we consider the following *virtual* two-dimensional array; i.e., it is not explicitly constructed, element $(y,z)$ just is $a\[y\]+a\[z\]$. We can *count* the elements $a\[y\]+a\[z\]\>9$ by "walking" along the "boundary".

$\begin{array}{c|ccccc} a & 1 & 3 & 4 & 7 & 8 \\\hline 1 & 2 & 4 & 5 & 8 & 9 \\ 3 & 4 & 6 & 7 & \color{green}{10}& \color{green}{11}\\ 4 & 5 & 7 & 8 & \color{green}{11}& \color{green}{12}\\ 7 & 8 & \color{green}{10}& \color{green}{11}& \color{green}{14}& \color{green}{15}\\ 8 & 9 & \color{green}{11}& \color{green}{12}& \color{green}{15}& \color{green}{16} \end{array}$
> 2 votes

# Answer
Assuming the 3SUM conjecture, this cannot be solved in $O(n^{2-\epsilon})$ for any $\epsilon \> 0$. For more lower bounds, I suggest you consult the 3SUM literature, which has recently been enjoying a renaissance; your problem seems even harder.
> 1 votes

---
Tags: time-complexity, space-complexity
---


title: When to not use count sort?

text:
# Question
Title: When to not use count sort?
If I have n integers, which are in range 1 to n^2, should I use count sort? My thought is that I shouldn't because it would be a risk if n happens to be substantial. I can't seem to figure out the implication on the time complexity for this problem, so I can't prove anything. Anybody have any insights?

# Answer
Since count sort is $O(k+n)$ (Analysis of count sort) as pointed out by D.W., for worst case input count sort will be more efficient than $O(n\log n )$ sorting algorithms as long as $k = o(n \log n)$.

Since in your case $k$ is $n^2$. i.e. $k = \omega(n \log n)$, it will be better to use $O(n \log n)$ sorting algorithms, or you can even use quick sort (for better overall average case efficiency).
> 5 votes

---
Tags: algorithms, sorting
---


# Question
Title: Does Huffman algorithm generate a minimal weight of a tree?
Does Huffman algorithm generate a minimal weight of a tree?

I noticed that by trying to make two different trees with the same frequencies of letters, I get different weights of the trees.

We defined the weight of the tree as $\displaystyle\sum\_{c\in C}f(c)d(c)$ where $C$ is all the letters, $f()$ is the frequency of the letter, $d()$ is the depth in the tree of that letter.

# Answer
> 2 votes
If you normalize the frequencies so that they add to 1, then the weight of the tree is just the average codeword length, which is exactly what Huffman's algorithm tries to minimize. Check this section of the Wikipedia article you link to.

---
Tags: algorithms, algorithm-analysis, huffman-coding
---


title: What is extra thread for idle time

text:
# Question
Title: What is extra thread for idle time
Here http://tomstechnicalblog.blogspot.com/2016/02/rxjava-understanding-observeon-and.html I've found a sentence which I do not understand:

> If you have a quad-core, you can optimally support 5 computational threads (4 cores + 1 extra thread for idle time).

What is that `1 extra thread for idle time` for? Is it similar to those "normal" `4 cores`?

# Answer
What I think they mean is that while you only have 4 cores to do computation on sometimes they will halt, pause, or "idle". When they do that the OS will run another thread on that core. As such you should be able to have 1 more thread to fill in the periods where a core is not doing anything.
> 1 votes

---
Tags: threads, multi-tasking
---