# Question
Title: Compute sum of edges in paths from source to target node?
Given a directed acyclic graph G = (V,E). Suppose that the vertices are in topological sort, in particular there exist an edge $(u,v) \in E$ if u \<v (see the graph below). The weight $w(u,v)$ on each edge is a positive number. For a given node $i$, I am interested in computing the following term $s\[i\]$ defined as follows: s\[i\] is sum of weights on any edges (w.o duplicates) of some paths from the source node 1 to the node i. For example, in the below graph s\[6\] = 3+ 2+ 10 + 20 + 200 + 100 = 335. I am struggling how to come up with a linear time w.r.t $|V|$ and $|E|$ to compute $s\[i\]$ for a given node $i$.

I am thinking of using dynamic programing. For example, suppose we already can compute $s\[j\]$ up to $j\<k$, to compute $s\[k\]$ we might attempt $s\[k\] = \sum\_{i} s\[i\] + w\[i,k\]$ if there is an edge $(i,k)$. For example, to compute $s\[6\]$ we need $s\[4\]$ and $s\[5\]$,

So $s\[6\] = (s\[4\] + 200) + ( s\[5\]+ 100) = (3+200) + ( (3+2+20+2+10) +100) $ but this approach fails since we did not take into account that the edge $(1,4)$ is shared in computing $s\[4\]$ and $s\[5\]$. The edge $(1,4)$ should be summed one time in $s\[6\]$.

# Answer
A simple approach that should work w/out need for a hash table is as follows:

Let two boolean arrays $a,b$ such that

* $a\[u\] =1 $ iff a path $1 \ldots u$ exists
* $b\[u\] =1$ if a path $u \ldots i$ exists

Both can be calculated in $O(V+E)$ time : $a$ with a simple BFS from $1$, and $b$ by a bottom-up approach of examining the vertices in the reverse topological order.

Now, you consider each edge of the graph $ u \rightarrow v$ and add $w(u,v)$ to the answer iff $a\[u\]=1$ and $b\[v\]=1$. Because the graph is a DAG the two paths above must be disjoint thus their concatenation is a valid path from $1$ to $i$ and since we consider each edge once, there are no duplicates.
> 1 votes

---
Tags: dynamic-programming
---


# Question
Title: Why does Python allow stand-alone expressions?
In Python, this is a valid program

```
def PrintWorld():
    print('World')

print('Hello')
0
'beautiful'
True
None
0 < 0
3, 3
lambda c:3
PrintWorld()

```

All it does is print 'Hello World' on two lines. The expressions are `0`, `'beautiful'`, `True`, `None`, `0 < 0`, `3, 3`, and `lambda c:3` are ignored and I'm wondering why.

I realize that this behavior allows Python to treat the function call `PrintWorld()` like any expression: It is an expression with value `None` in the course of whose evaluation the function is called. In a sense, this means that both `'beautiful'`, `PrintWorld()`, and a hypothetical expression with side effects like `PrintWorld() is None` could be treated the same on some level.

I also realize that this is related to interactive mode: When you run the Python interactively, giving only a stand-alone expression will result in its value being printed.

Still, why should non-interactive mode accept these expressions (except function calls)? In my eyes they open up the possibility for pointless code without offering anything in return.

And, as a follow-up: If you *do* allow these stand-alone expressions, why have comments or a `pass` statement in the language when you could just use a stand-alone expression instead? Sure, "explicit is better than implicit", but it's also valuable to keep the language small.

As research I googled and searched stack overflow and CS stack exchange. I also looked into the Python language definition.

# Answer
> 5 votes
The python creators decided that any expression is valid as a statement. While not all expressions are useful as statements, it would make the language more complex to have to remember which expressions may be statements and which can not.

A second reason is that many expressions that may seem "safe" can still have side effects, making it useful to evaluate them without using the return value.

## Operators

Operators are the most obvious examples of expressions that you can easily add side-effects to. In your example `0 < 0` is equivalent to `0.__le__(0)`. You can overwrite the `__le__` method or any operator special method to do whatever you want, including writing to a file or incrementing a counter.

You can also evaluate operator expressions just to make sure the types are compatible. For example, if you are going to do a very long computation on variables `a` and `b` that ends by dividing some value based on `a` by `b` you might evaluate `a/b` at the start of your function as a quick and dirty way to make sure the types can be divided and that `b` is not zero before spending a lot of time calculating.

## Strings

Strings don't typically have any side effects, but string expressions are frequently used in python code as a type of comment. Specifically, docstrings are triple-quoted strings right after the heading of a class or function, and will be assigned to `__doc__`.

## Variables

Evaluating variables has one important function: It will crash if the variable doesn't exit. For example, suppose I have a module `server.py` that must be configured `server.host = 'localhost'` before starting. I could write this:

```
try:
    host
except NameError:
    raise ConfigurationException("must set host")

```

## Tuples

The tuple expression `a, b` where `a` and `b` are expressions will evaluate any side effects from `a` `b`.

## Others

Ok, there is little use for a loose `None`. However, only disallowing `None`, `True`, `False`, `Ellipsis`, `NotImplemented`, and `...` would be a unnecessary special case that would make the language harder to learn for little benefit.

# Answer
> 1 votes
Python can be used interactively, in which case the bare expression's value (if any, it might be `None`) is printed out. If running a script or as part of a function, the value is just discarded.

If you look closely, Python only has functions (no `procedure`s in e.g. Pascal sense or `SUBROUTINE` for Fortran that specifically don't return a value at all). Like in C, procedures are fake, functions that return `None` either explicitly, doing a bare `return`, or by not executing `return` at all.

Why Python is architected this way is anybody's guess. You'd have to ask the people in charge. It does simplify the grammar somewhat and presumably also makes the parsing/processing simpler/faster, besides making interactive use cleaner.

---
Tags: python, language-design
---


# Question
Title: Confusion in the added loop of the Halting Problem
I know there's like a thousand questions about this topic in the site and elsewhere. I'm just going to pick one that at least for me it serves as a good basis for my question. The answer by Rick Decker is the one that I understood more, so I'm just going to take it as a basis for my actual doubt.

It's not difficult to see that if one adds an if (and extra loop) into 'Halting Program ' $H$, then feeding $H$ to itself yields a contradiction. What it confuses me is why to add the extra loop to force the contradiction, if by hypothesis $H$ solves (itself?)

It doesn't seem logical to say first (of course I'm missing something), hey I give you $H$ that solves your issue, but afterwards I give you an augmented $H$ that does not and so we reach a contradiction.

# Answer
> 1 votes
What we show is that this augmented $H$ can not even exist. You gave me $H$, and I gave you back an augmented $H$, called $\hat H$. We can build this $\hat H$ by adding the extra loop and `if` statement, but its easy to show that this augmented $\hat H$ will never be able to exist: $\hat H(\langle \hat H\rangle)$ is not either rejecting or accepting, nor stuck in an infinite loop, but we know that any TM must be either one of those.

Therefore, we get a contradiction to the existence of $H$: we showed that if $H$ exists, then some other $\hat H$ exists, but also $\hat H$ couldn't ever exist.

---
Tags: halting-problem
---


# Question
Title: Multiplying two bivariate polynomials using FFT
> Consider two bivariate polynomials of degree at most $n − 1$ in each variable: $$ F(x,y) = \sum\_{i,j=0}^{n-1} f\_{i,j} x^iy^j \quad\text{and}\quad G(x,y) = \sum\_{i,j=0}^{n-1} g\_{i,j} x^iy^j $$ Show how to compute the product polynomial in $O(n^3 \log n)$ time.

Can anybody briefly explain the solution please?

# Answer
The product is $$ F(x,y) G(x,y) = \sum\_{i=0}^{2n-2} x^i \sum\_{i'=0}^{n-1} \left(\sum\_{j=0}^{n-1} f\_{i',j} y^j \right) \left(\sum\_{j=0}^{n-1} g\_{i-i',j} y^j\right). $$ You take it from here.
> 0 votes

---
Tags: algorithms, fast-fourier-transform
---


# Question
Title: If a key in a red-black tree has exactly one child (which isn't null) then it is always red
I have the following claim:

> Prove or disprove: If a key in a red-black tree has exactly one child (which isn't null) then it is always red.

---

***My attempt:***

*Disproof.*

We will exhibit a counterexample:

This tree satisfies the conditions of being a red-black tree, since:

1. The root is black.
2. All leaves are black.
3. There isn't any red key.
4. In each path there is the same amount of black keys, in particular, we have three black keys in such paths.

***However***, we have two keys in level 1, which have one child and it is black.

$\qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \blacksquare$

---

Is this counterexample correct?

# Answer
The disproof is wrong because in your Red-Black tree, all possible leaves need to be represented (see exemples on wikipedia). That means that the real tree represented should be:

It is easy to see that it does not respect the fourth condition of the definition.

In the claim, when it is said that:

> a key \[…\] has exactly one child (which isn't null)

it actually means that it has two children, and exactly one of them is null. It is due to the fact that in the representation of a red-black tree, you can either represent ALL null leaves or represent none.

I will let you try to prove or disprove the claim knowing that and edit this answer if necessary.
> 2 votes

---
Tags: data-structures, binary-trees, binary-search-trees, red-black-trees
---


# Question
Title: Why can't one use the Cook-Levin theorem to show that TQBF is PSPACE-complete?
I have been reading Michael Sipser's *Introduction to the Theory of Computation*, and I have stumbled upon a paragraph in Chapter 8 (Theorem 8.9 on page 339 of the 3rd international edition) that I simply do not understand.

For context, TQBF is the language of all first-order logical formulas in prenex normal form that are true given a universe/domain.

A language $B$ is PSPACE-complete if

1. $B$ is in PSPACE, and
2. every $A$ in PSPACE is polynomial *time* reducible to $B$.

The following paragraph from the book tells us that it is a bad idea to use Cook-Levin theorem for the purpose of showing that a language $A$ in PSPACE is polynomial time reducible to TQBF. The paragraph reads:

> As a first attempt at this construction, let's try to imitate the proof of the Cook-Levin theorem, Theorem 7.37. We can construct a formula $\phi$ that simulates $M$ on input $w$ by expressing the requirements for the accepting tableau. A tableau for $M$ on input $w$ has width $O(n^k)$, the space used by $M$, but its height is exponential in $n^k$ because $M$ can run for exponential time. Thus, if we were to represent the tableau with a formula directly, we would end up with a formula of exponential size. However, a polynomial time reduction cannot produce an exponential-size result, so this attempt fails to show that $A$ is polynomial time reducible to TQBF.

This last sentence I don't get. Why cannot a polynomial time reduction produce an exponential size result? Doesn't any reductions using Cook-Levin from an NP language result in an exponential-size result? Is it that it doesn't work in this particular situation, or is this a general thing?

My guess is that it has to do with the assumed space complexities of $A$ or TQBF, however I still don't see it. One of the conditions for TQBF's PSPACE-completeness is to show that any PSPACE language is polynomial *time* reducible to TQBF. Any talk about space shouldn't really belong.

Maybe it's my sheer interpretation of the sentence?

# Answer
> 3 votes
If you want to write $N$ words of output, it takes at least $N$ steps of computation to do that. So, if you need to produce an exponential-sized output, you'll need to spend exponential time to do it. For that reason, a polynomial-time reduction cannot produce an exponential-sized output when run on a polynomial-sized input.

# Answer
> 2 votes
The fact that the given reduction takes exponential space implies it must take exponential time and therefore is not polynomial.

Using Cook-Levin on a NP-complete problem does not produce an exponential-sized output; it produces a polynomial-time circuit. It constructs a circuit whose size is polynomial in the number of steps taken by the NP-verifier; since the verifier runs in polynomial time, this circuit is polynomial in size.

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


title: determine Eulerian or Hamiltonian

text:
# Question
Title: determine Eulerian or Hamiltonian
I am a beginner in graph theory and just found this question in a book after completing few topics and I was wondering how you approach this questions. For eulerian, I can say that the graph has vertex with odd degree hence not eulerian, but how can I determine if they are hamiltonian or not?

# Answer
> 6 votes
That's a very good question, and the easy answer is that checking whether a graph is Eulerian is much simpler than checking whether a graph is Hamiltonian. You're diving head-first into the field of complexity theory and the famous question P vs NP. (Further reading: What is the definition of P, NP, NP-complete and NP-hard.)

As you said, a graph is Eulerian if and only if the vertices have even degrees.

For checking if a graph is Hamiltonian, I could give you a "certificate" (or "witness") if it indeed was Hamiltonian. However, there is no anti-certificate, or a certificate for showing that the graph is non-Hamiltonian; Checking if a graph is *not Hamiltonian* is a co-NP-complete problem.

In fact, we believe that any certificate for non-Hamiltonian-ness needs to be exponentially large.

---

To answer the question:

1. Try every permutation of vertices, and if one of the permutations is a cycle, then the graph is Hamiltonian. If so, you get a certificate.
2. If no permutation was a cycle, the graph is not Hamiltonian. You cannot convince your friends that the graph is non-Hamiltonian without trying all permutations\*.

(Ps, using algorithmic techniques (DP) you don't have to try *every* permutation, but still exponentially many.)

# Answer
> 4 votes
Indeed, for Eulerian graphs there is a simple characterization, whereas for Hamiltonian graphs one can easily show that a graph is Hamiltonian (by drawing the cycle) but there is no uniform technique to demonstrate the contrary.

For larger graphs it is simply too much work to test every traversal, so we hope for clever *ad hoc* shortcuts.

As an example, consider your graph to the right. Let us color the top three nodes red and the bottom four nodes green. While there are edges between red nodes, in any Hamiltonian cycle any green node must be between two red nodes. Of course there are only three red nodes, not sufficient to be between the four green nodes. Hence the right graph is not Hamiltonian.

One can generalize this to the following theorem: (see our friends at math.SE)

> Let $G$ be a graph. If there exists a set of $k$ nodes in $G$ such that removing these nodes leads to more than $k$ components, then $G$ is not Hamiltonian.

The graph to the left can also be handled in that way (or, directly, the graph is bipartite and the two partitions are not of equal size).

The middle graph, the Petersen graph, is not Hamiltonian either. It seems to need a different approach. Google is your friend.

---
Tags: graphs
---


# Question
Title: Context-free grammar for complement of $\{ab \mid b=\mathrm{complement}(a)\}$
I want to construct a context-free grammar for $$L=\Sigma^\*-\\{ab \mid b=\mathrm{complement} (a) , a,b \in \\{0, 1\\}^\*\\}$$ and prove the correctness of answer. The complement of a string is obtained by switching $0$s and $1$s. For example, $\mathrm{complement}(001) = 110$.

I'm trying to decompose the language but I'm not sure about the different cases I should consider. For example, I know that $L$ contains all strings with odd length. But what else do I have to consider? Also, I can't make sure that the language of constructed grammar equals the given language, so a proof is needed.

# Answer
As you have noticed, you can decompose between words of odd length and words of even length. Since the odd part is quite easy, I will focus on the even one, that is $L = \\{uv \mid u, v\in \\{0,1\\}^\*\wedge u\neq \mathrm{complement}(v)\\}$.

Given $u, v\in\\{0,1\\}^\*, |u|=|v|$, if we write $u = u\_1…u\_k$ and $v = v\_1…v\_k$, then $uv \in L$ if and only if $k \geq 1$ and $\exists i \in \[\\!\[1,k\]\\!\], u\_i = v\_i$. In that case, we can write $uv = wu\_ixv\_iy$ where $|w| = u\_1…u\_{i-1}$ and $y = v\_{i+1}…v\_k$. We also have $|x| = k-i + i -1= k-1$, so $x$ can be written as $x = zt$ with $|z| = i-1 = |w|$ and $|t| = k-i = |y|$.

We will now write a grammar to generate these words. Let's define:

> $S\to AA\mid BB$
>
> $A \to 0 \mid 0A0 \mid 0A1 \mid 1A0 \mid 1A1$
>
> $B\to 1\mid 0B0\mid 0B1 \mid 1B0 \mid 1B1$

It is clear that $A$ rules will generate a word $w0x$ with $|w| = |x|$. That means that $AA$ will generate $w0zt0y$, with $|w| = |z|$ and $|t| = |y|$. The same thing can be done with $BB$.

(This answer was greatly inspired by this one.)
> 3 votes

---
Tags: context-free
---


# Question
Title: Having trouble understanding blatantly non-private definition because of Little-o notation
I was pretty confident that I understand asymptotic notation until now. However, I am having a hard time understanding some basic definition that use asymptotic notation, specially little-o.

> Definition 8.1.A mechanism is blatantly non-private if an adversary can construct a candidate database 'c' that agrees with the real database 'd' in all but o(n) entries, i.e.,‖c−d‖0∈o(n).

A bit of context. 'd' is a database where each row is one individual 'i' with 'n' individuals in total. the database has just one column representing some important questions. The values of the column can be 0 or 1. 'c' is a candidate database, a database that will try to be as similar as possible to the database 'd', it has the same structure one row for each individual and values for the column of {0,1}. Both are treated as a vector.

I watched a lecture and the informal description of the professor was "database 'c' will agree with database 'd' in 99,9..% of the cases".

But my interpretation of the definition is exactly the opposite "database 'c' will agree with database 'd' in all entries except 99,9..%".

My definition seems a bit odd to a "blantly" non-private mechanism. But I cannot understand how "except o(n)" would mean that a minority of the entries would not be equal in both databases.

# Answer
> 1 votes
The interpretation of your professor is "intuitively correct" (but still formally wrong). The notation $o(n)$ denotes the set of functions that grow less than linearly with $n$.

That definition means that, if we look at databases $d$ whose number of entries $n$ grows towards infinity, the candidate database $c$ will agree with $d$ in all but a vanishingly small fraction of the entries.

Notice that if $c$ agrees with $d$ "only" on $99.9\\%$ of the $n$ entries, then the number of disagreements still grows linearly with $n$. Indeed: $0.001n \in \Theta(n)$ and hence $0.001n \not\in o(n)$. See the page about asymptotic notation on Wikipedia.

---
Tags: complexity-theory, asymptotics, security, definitions
---


# Question
Title: Are modern programming languages context-free?
Which language class are today's modern programming languages like Java, JavaScript, and Python in?

It appears (?) they are not context-free and not regular languages.

Are these programming languages context-sensitive or decidable languages? I am very confused!

I know that context-free is more powerful than regular languages and that context-sensitive is more powerful than context-free.

Are modern programming languages both context-free and context-sensitive?

# Answer
Practically no programming language, modern or ancient, is truly context-free, regardless of what people will tell you. But it hardly matters. Every programming language can be parsed; otherwise, it wouldn't be very useful. So all the deviations from context freeness have been dealt with.

What people usually mean when they tell you that programming languages are context-free because somewhere in the documentation there's a context-free grammar, is that the set of well-formed programs (that is, the "language" in the sense of formal language theory) is a *subset* of a context-free grammar, conditioned by a set of constraints written in the rest of the language documentation. That's mostly how programs are parsed: a context-free grammar is used, which recognises all valid and some invalid programs, and then the resulting parse tree is traversed to apply the constraints.

To justify describing the language as "context-free", there's a tendency to say that these constraints are "semantic" (and therefore not part of the language syntax). \[Note 1\] But that's not a very meaningful use of the word "semantic", since rules like "every variable must be declared" (which is common, if by no means universal) is certainly syntactic in the sense that you can easily apply it without knowing anything about the meaning of the various language constructs. All it requires is verifying that a symbol used in some scope also appears in a declaration in an enclosing scope. However, the "also appears" part makes this rule context-sensitive.

That rule is somewhat similar to the constraints mentioned in this post about Javascript (linked to from one of your comments to your question): that neither a Javascript object definition nor a function parameter list can define the same identifier twice, another rule which is both clearly context-sensitive and clearly syntactic.

In addition, many languages require non-context-free transformations prior to the parse; these transformations are as much part of the grammar of the language as anything else. For example:

* Layout sensitive block syntax, as in Python, Haskell and many data description languages. (Context-sensitive because parsing requires that all whitespace prefixes in a block be the same length.)
* Macros, as in Rust, C-family languages, Scheme and Lisp, and a vast number of others. Also, template expansion, at least in the way that it is done in C++.
* User-definable operators with user-definable precedences, as in Haskell, Swift and Scala. (Scala doesn't really have user-definable precedence, but I think it is still context-sensitive. I might be wrong, though.)

None of this in any way diminishes the value of context-free parsing, neither in practical nor theoretical terms. Most parsers are and will continue to be fundamentally based on some context-free algorithm. Despite a lot of trying, no-one yet has come up with a grammar formalism which is both more powerful than context-free grammars and associated with an algorithm for transforming a grammar into a parser without adding hand-written code. (To be clear: the goal I refer to is a formalism which is more powerful than context-free grammars, so that it can handle constraints like "variables must be declared before they are used" and the other features mentioned above, but without being so powerful that it is Turing complete and therefore undecidable.)

### Notes

1. Excluding rules which cannot be implemented in a context-free grammar in order to say that the language is context-free strikes me as a most peculiar way to define context-freeness. Of course, if you remove all context-sensitive aspects of a language, you end up with a context-free superset, but it's no longer the same language.
> 73 votes

# Answer
The boundary between context-free and context-sensitive is only determined by *one thing*: whether or not it can be decided with a nondeterministic pushdown automata.

With respect to grammar specifically, most practical programming languages are *almost* context-free if not context-free, but the context-free/context-sensitive distinction isn't nearly as important as the ease of parsing. It's possible to create a context-free language that is difficult to parse or is ambiguous, and it is also possible to create a context-sensitive language that is easy to parse. Remember, the computers we use to parse programming languages are functionally equivalent to Turing machines (if given infinite memory) and are limited by the fact that they are deterministic. The determinism is the practical limiting factor that informs our choice in grammars that programming languages will use, so the boundary between context-free and context-sensitive is less practically interesting than the boundary between deterministic and nondeterministic.

$LL\_k$ and $LALR\_k$ grammars form specific subsets of deterministic context-free grammars that can be parsed with generated tables within programs that simulate a deterministic pushdown automaton (which is less powerful than a nondeterministic one).

On the other hand, $PEG$ grammars have a handful of features that technically fall under the context-sensitive umbrella, however they can be parsed in linear time* with generated code, which outperforms generalized nondeterministic context-free parsing (The best known algorithm for CFGs is somewhere between quadratic and cubic time. This class of grammars includes certain obscure features that are technically context-free but are hard to parse- I don't know of any examples off the top of my head). PEGs have become quite popular for modern languages, and even Python has adopted its use for upcoming versions and new languages such as Zig have been using them from the beginning.

Having a "more powerful" grammar doesn't matter at all for the power of a programming language because the computing model they represent can simulate a Turing machine. In fact, it's often the opposite because "more powerful" grammars tend to be more difficult to parse and are therefore less friendly to both machines and computers (and slower to compile). C++ is a particularly notorious offender in this realm, with templates (and how they are expanded) having the ability to affect the parse tree. In fact, C++ is not even decidable because templates are Turing complete.

\*: Technically, there are some pathological cases that can cause catastrophic backtracking and explode the parsing to exponential time, however for most useful grammars and programs, this is not an issue. In addition, since PEG parsers typically cache intermediate parsing results, two rules that only differ slightly will not cause a tremendous amount of backtracking in order to properly select the correct rule, and smart code generators can mitigate the worst backtracks.
> 5 votes

# Answer
For a detailed discussion how C as standardized in 2011 (see ISO/IEC 9899:2011 – Programming languages – C) diverges from context freeness you might want to look at Jourdan and Poitier, "A simple, possibly correct LR parser for C11", ACM Transactions on Programming Languages and Systems 39:4 (Aug 2017), article 14. And that one assumes preprocessed code (already mangled by the C preprocessor).

Note that the preprocessor has *no* idea or respect for C syntax, and can be (perversely) used to rename keywords and partially replace syntax. An (in)famous example is the dialect of C deformed into almost-Algol in which Bourne wrote his original version of the Unix shell (see the V7 shell source).

The history of Algol 68 with its two-level grammar (the idea was to have a grammar generating a grammar tailored to the program) is also a data point showing programming languages are not context free.

Even a language with extremely simple "context free" syntax like Scheme as described by the R7RS (its syntax isn't much more than "open parenthesis has to be closed") is accompanied by a lot of non-context-free restrictions in its description.
> 2 votes

# Answer
On top of what others have said, many modern programming languages come with explicit disambiguation rules, and non-compiler-writers are often not aware of just how often these are applied.

Most modern programming languages have a two-level grammar, split into lexical analysis and syntax analysis. The lexical language in particular is almost always based on two disambiguation rules:

* Some lexemes take precedence over others. For example, an identifier is a sequence of characters of a certain form which isn't a keyword. This *can* be expressed as a grammar or regular expression (regular languages are closed under set difference), but it's difficult
* Lexemes are as long as possible. This is known as the "maximal munch rule". So, for example, `ifwhile` is a single identifier rather than the two keywords `if` and `while`.

Similarly, it is *possible* to solve the "dangling else" problem with an unambiguous grammar, but it's more typically solved using a CFG form of the maximal munch rule ("prefer shift to reduce" in LR speak).

Having said that, there are languages whose grammars are inherently ambiguous, and disambiguation must happen semantically. The C family of languages famously has several places where this occurs:

* In C, `foo(bar);` is a function call if `foo` is an identifier, or a declaration of a variable named `bar` if `foo` is a type name. In C++, it could also be a function-style cast of `bar` to type `foo`.
* In C++, `foo bar();` could be a declaration of a function named `bar`, or it could be a declaration of a variable named `bar` using the default constructor of `foo`.
> 1 votes

---
Tags: formal-languages, programming-languages, syntax
---


# Question
Title: (reference) Where can I learn more about I/O operations in OS?
I have basic understanding of file I/O. I know how to operate the read and write system calls in Linux. I know that there is blocking and non-blocking I/O. I want to know more about the underlying mechanism in OS for I/O. How is blocking and non-blocking I/O implemented? How do the kernel I/O buffers work? How big are they and when are they "erased"? For example if there is an open socket how much data will be kept in the kernel buffer before the data is overwritten? I prefer a book of some kind. And please don't tell me to go and read the source. I konw that if I REALLY want to know how those things work that is the best I can do, but I simply am unable to dedicate so much time to this subject.

# Answer
It is pretty complex because there are several layers between the actual hard-disk and the software implementation of sockets. In today's x86 computers, the actual hard-disk is read using the Intel's AHCI controller which is a PCI device. All SATA plugs on your motherboard are directly connected to the AHCI. The AHCI will control the hard-disk and present a complex interface to software so that it can read/write to/from the hard-disk.

The best way to learn those things is to write an OS yourself. Get the basics of bootloading then write a minimal OS and this knowledge will come by itself over time. The MCFG ACPI table informs software of the address of the beginning of the PCI configuration space. Then you can scan PCI buses (more often only bus 0 for home computers). On bus 0 you can have up to 32 devices which can each have up to 8 functions. The function is what the device actually does. Each function of each device will have a configuration space which allows to get more information on the function. It will present class IDs and subclass IDs will allow to identify the different devices. As stated on osdev.org (https://wiki.osdev.org/AHCI).

> An AHCI controller can be found by enumerating the PCI bus. It has a class id 0x01 (mass storage device) and normally a subclass id 0x06 (serial ATA). The vendor id and device id should also be checked to ensure it’s really an AHCI controller.

Once you found an AHCI on the PCI bus, you can look at the specification of the AHCI for implementing a driver: https://www.intel.com/content/www/us/en/io/serial-ata/serial-ata-ahci-spec-rev1-3-1.html. This spec really covers what you need to implement an AHCI driver.

Blocking versus non-blocking I/O is a software construct. Blocking I/O waits for the data buffer to be filed while non-blocking I/O will return immediately if there are no data ready. Non-blocking I/O expects you to call the read again so that you can get a full buffer. It isn't this complex for hard-disks while for network it is very complex. Basically, the AHCI is a DMA device (since it is PCI compliant and PCI devices are DMA in nature since they have access to RAM bypassing the CPU). I never implemented a driver for it but the AHCI will be triggered by a command and, once the command is completed, will trigger an interrupt on a certain vector using the MSI-X capability of PCI devices. The MSI-X capability allows to specify a vector to trigger on command completion.

I think this answer is a good starting point for you on what to read and what to do. I doubt there will be a good book on this matter for you to read. You should implement an AHCI driver and socket layer above this driver to really understand how it works under the hood. The socket layer is a POSIX specification that you can find on internet.
> 3 votes

---
Tags: operating-systems, os-kernel
---


# Question
Title: Amortized analysis - adding operations to a data structure
One of the finer points of amortized analysis about which I have been able to find relatively little information is the broad question of what happens to the amortized cost of a structure's existing operations if we add a new one. I'll use two popular examples to illustrate my confusion:

In a binary counter which only supports the increment operation, choosing the potential function $\Phi=\\#$ of $1$'s in the present configuration gives us constant amortized cost for the operation. In every example I can see in the literature, adding the decrement operation to the counter creates a situation where both it and the increment operation have linear amortized costs. The argument given is that we can toggle $m$ times between values of $2^n$ and $2^n-1$ with a series of alternating decrement and increment operations, giving us a time of $\Theta(mn)$.

In a binomial heap, using the number of binomial trees in the structure as a potential function gives us constant amortized time for insertion. Popping the minimum takes logarithmic time both amortized and in actuality.

Perhaps I'm mistaken, but I see a certain contradiction here. In a binomial heap we could reach a point where we have one large binomial tree with $2^n$ elements and repeatedly perform pop and push operations, which will cost $\Theta(m\log n)$ time. Even if each vertex keeps its children in a linked list which would give the deletions constant time, the insertions will all take logarithmic time.

Having said that, the insertion operations for both structures still function the same way: for any sufficiently large $m$, any series of $m$ insertions to either structure still takes $O(m)$ time - the inclusion of the deletion (decrement in the counter) operation doesn't affect the way the insertion operation works.

So why do we say that adding decrementation to a binary counter increases the amortized cost for incrementation and then ignore the same argument when analyzing binomial heaps?

# Answer
> 2 votes
I don't know much about the amortized running time of binomial heap, but after reading Wikipedia, I suspect the following might be true: the amortized time of a long sequence of consecutive insert operations is $O(1)$; but this is only true for consecutive insert operations that don't have any other operations mixed in. Based on that, I wouldn't really summarize the running time of a binomial heap by saying that insert takes $O(1)$ amortized time, without further caveats.

As you quite astutely point out with your example based on a binary counter, the amortized running time of an operation depends on the full set of operations that are allowed to be performed. So I suspect that the resolution is that the claim about the amortized running time of inserts into a binomial heap wasn't quite right, or had some additional caveats. I don't know that for sure, as I don't know much about binomial heaps, but that would be my running hypothesis at this stage.

---
Tags: data-structures, amortized-analysis
---


# Question
Title: Will random function ever hit a hard coded decimal number?
I'm not very sure how exactly a fractal number is stored nor how random function works in mordern programming languages.

But I am curious, will random function ever hits a hard coded decimal number?

I know mathematically it is impossible, but how about in computer science?

Such as the following javascript code, will it ever hit the number and stop?

```
// this can be any number
const rnd = 0.123456;

while (true) {
    if(rnd === Math.random()) {
        console.log('hit');
        break;
    }
}

```

> *Also I ran that code for 2 hours and it didn't stop*

If decimal points are store in 64 bit, does that mean the chance to hit any decimal point is `1/2^64`?

If it can hit, is `0.000123456` harder to hit than `0.01`?

# Answer
Your random number generator might not be able to produce all numbers. Without looking at Math.Random, if it returned an integer then it would never match 0.123456. If it returned a double precision floating point number 0 \<= rnd \< 1, it might produce a 53 bit integer from 0 to 2^53-1, and multiply by 2^-53. In this case it is quite possible that 0.123456 will never be hit.

But even if 0.123456 would be hit eventually, that random number generator would produce 2^53 possible values. On average it needs to produce 2^52 values before a match. That isn't going to happen within two hours. Assuming 10ns per number, 10ns * 2^52 is about 45 million seconds, or 521 days.
> 3 votes

# Answer
Well, it technically *is* possible (with a small caveat). This is due to the fact a computer has finite memory, and hence cannot represent all possible numbers, but rather only a very very small fraction of them (and thus the probability to "hit" some particular number it can represent is not 0). However, it still depends on the random function's behavior. For example (an example I totally made up, just for the point), if the random function will always return a value with only 4 digits after the decimal dot, then it can't return `0.123456`. This can happen for a lot of reasons, not only if it returns a value with only 4 digits after the decimal point (which was a made up restriction).

So it is possible to hit numbers like that, maybe not `0.123456` specifically, but some other numbers.

Anyways, the computer can still represent a *lot* of numbers. Depending on your computer, it can be around $2^{32}$ different numbers, hence, if you try to actually run this code on your computer, it could take a lot of time and you might even start to think it will never finish...

Anyways, the probability to hit a certain number should depend on the randomized algorithm you are using (those are called pseudo-random number generators). For example, if you are using an algorithm that will generate uniformly numbers, then the probability should be around the same. But if you are using a different probability distribution (like a normal distribution), then the probabilities will be different.
> 1 votes

---
Tags: data-structures, randomized-algorithms
---


# Question
Title: Is this definition of $\alpha$-equivalence correct?
I want to extend $\alpha$-equivalence to cover substitution.

That is, I will implement `runSubst_Term : Subst -> Tm -> Tm` and prove:

```
Theorem runSubst_Term_main_property (sub : Subst) (tm : Tm)
  : AlphaSubst sub tm (runSubst_Term sub tm).

```

where the definitions of `Subst`, `Tm`, `AlphaSubst` are below.

But I don't sure that `AlphaEquiv` is a correct $\alpha$-equivalence relation.

So it would be appreciated if you could check that the definition is correct.

```
Definition IVar : Set := nat.

Inductive Tm : Set :=
| Var (iv : IVar) : Tm
| App (tm1 : Tm) (tm2 : Tm) : Tm
| Lam (iv : IVar) (tm1 : Tm) : Tm.

Definition Subst : Set := list (IVar * Tm).

Fixpoint runSubst_Var (sub : Subst) (iv0 : IVar) : Tm :=
  match sub with
  | [] => Var iv0
  | (iv, tm) :: sub' => if Nat.eq_dec iv iv0 then tm else runSubst_Var sub' iv0
  end.

Inductive AlphaSubst (sub : Subst) : Tm -> Tm -> Prop :=
| AlphaSubstVar (iv : IVar) (tm : Tm)
  (SUBST_iv : runSubst_Var sub iv = tm)
  : AlphaSubst sub (Var iv) tm
| AlphaSubstApp (tm1_1 : Tm) (tm1_2 : Tm) (tm2_1 : Tm) (tm2_2 : Tm)
  (SUBST_tm1 : AlphaSubst sub tm1_1 tm2_1)
  (SUBST_tm2 : AlphaSubst sub tm1_2 tm2_2)
  : AlphaSubst sub (App tm1_1 tm1_2) (App tm2_1 tm2_2)
| AlphaSubstLam (iv1 : IVar) (iv2 : IVar) (tm1 : Tm) (tm2 : Tm)
  (SUBST_tm : AlphaSubst ((iv1, Var iv2) :: sub) tm1 tm2)
  : AlphaSubst sub (Lam iv1 tm1) (Lam iv2 tm2).

Definition AlphaEquiv (tm1 : Tm) (tm2 : Tm) : Prop :=
  AlphaSubst [] tm1 tm2.

```

# Answer
> 2 votes
The approach itself makes sense, but the relationship with `runSubst_Var` probably makes proofs more difficult.

I think it's better to work on De Bruijn indices for alpha-equivalent semantics.

# Answer
> 1 votes
That is wrong. Because:

```
Example counter_ex : AlphaEquiv (Lam 2 (Lam 0 (Var 2))) (Lam 1 (Lam 1 (Var 1))).

```

---
Tags: lambda-calculus
---


title: On lambda calculus notation: FGa

text:
# Question
Title: On lambda calculus notation: FGa
If we've got this expression:

> **FGa**

where **F** and **G** are functions (as well as **a**, of course; but let's treat **a** as a constant).

It must be understood that: first apply **F** taking **G** as input; then apply the previous result with **a** as input. This is

> FGa = (FG)a

conventionally expressed:

> ( F(G) )( a )

Or is it this instead:

> **FGa** == **F(Ga)** == **F(G(a))**

Thanks.

# Answer
> 1 votes
It's the first one. Function application is left-associative.

$$FGa = (F G) a$$

---
Tags: lambda-calculus, notation
---


# Question
Title: Minimize sum of $w_i(y_i-y)$ given $|y_i-y| \leq 4w_i$
> Given numbers $y\_1,\ldots,y\_n$ and $w\_1,\ldots,w\_n \> 0$, find $y\_c$ which minimizes $$ L = \sum\_{i=1}^n w\_i (y\_i - y) $$ under the constraint $|y\_i - y| \leq 4w\_i$.

How to proceed?

# Answer
> 0 votes
Write $$ L = \sum\_{i=1}^n w\_i y\_i - \sum\_{i=1}^n w\_i y. $$ Thus $L$ is linear in $y$, and moreover, it is a decreasing function. Thus we want to choose the largest $y$ which satisfies the constraints $|y\_i - y| \leq 4w\_i$, if any. I'll let you figure out how to find this $y$.

---
Tags: algorithms
---


# Question
Title: Is the algorithm implemented by git bisect optimal?
Let $G$ be a DAG. We know that some nodes in $G$ are "bad", while the others are "good"; a descendant of a bad node is bad while the ancestors of a good node are good. We also know that bad nodes have a unique minimal element in $G$ which we'd like to find querying as few nodes as possible with queries of the type "Are you good or bad?".

This problem is solved in Git, the popular version control system, by the command `git-bisect`, which helps a programmer find the first commit in which a bug was introduced.

At the start, the algorithm implemented by Git assumes to know a single bad commit and one or more good commits. At each step of its execution, the algorithm finds a commit using the following steps (taken from here):

1. Keep only the commits that:

*a)* are an ancestor of the bad commit (including the bad commit itself), and

*b)* are not an ancestor of a good commit (excluding the good commits).
2. Starting from the good ends of the resulting graph, associate to each commit the number of ancestors it has plus one.
3. Associate to each commit $\min(X, N-X)$, where $X$ is the value associated to the commit in step 2, and $N$ is the total number of commits in the graph (after it was reduced in step 1).
4. The best bisection point is the commit with the highest associated number.

This algorithm is essentially finding the commit that achieves the "worst best case": in fact, $\min(X,N-X)$ is the number of nodes in the DAG at the next iteration in the best case, thus $\max\min(X,N-X)$ is the worst best case.

I'm wondering:

* Does it make any difference if we select the "best worst case", that is, the node that achieves $\min\max(X,N-X)$?
* Is this algorithm worst-case optimal?

EDIT: I've noticed that this problem has a $\Omega(N)$ bound. Consider the DAG formed by a single node $b$ with $N-1$ parents called $g\_1,\dots,g\_{N-1}$. If we know that $b$ is bad then we have check each of the parents to see if they are the minimal bad node.

EDIT 2: The previous is actually a $\Omega(w)$ bound, where $w$ is the width of the poset. An alternative algorithm for this problem is given in this answer on cstheory.stackexchange that uses $O(w\log{n})$ queries.

# Answer
> 5 votes
Here's some intuition for what $X$ and $N$ are doing. Focus on a particular commit $c$. Suppose we test $c$ and classify it as either "good" or "bad". Until we test it, we don't know whether it is good or bad, but we can predict in advance how much smaller the graph will get in each of those two cases. In particular, $X$ is the number of commits that would be trimmed away if commit $c$ turns out to be good, and $N-X$ is the number of commits that would be trimmed away if commit $c$ turns out to be bad.

Therefore, the value $\min(X,N-X)$ is a lower bound on the number of commits we'll be able to trim away in the next step, no matter how the test turns out. The idea of the Git algorithm is to maximize of this metric. In other words, Git picks a threshold $t$ that is as large as possible, and a commit $c$ to test next, such that Git can be sure that it'll be able to trim away at least $t$ commits in the next step.

If we have no information about whether each commit is likely to turn out good or bad, so it's equally likely that it's good or bad, then this looks like a locally optimal choice. Thus, the Git algorithm is a greedy algorithm.

Is the Git algorithm globally optimal? That will depend upon the definition of "optimal", and (probably) on the distribution of DAGs one encounters in practice. Probably there is no simple characterization of the probability distribution on DAGs one encounters in practice, so I'd expect it is probably going to be difficult to find an optimality result for this problem.

# Answer
> 0 votes
I believe a **golden-section-search would be faster** than git-bisect's current binary-search implementation.

I remember learning about the advantage of the golden-section-search over the binary-search while reading Steven C. Chapra's numerical method book , but I can't find the original reference as I don't own the book anymore...

However, I found some other reference here that indeed suggests that modify the bisection method with the golden ratio that results in faster computation.

---
Tags: algorithms, graphs
---


# Question
Title: Is it possible to create a NFA that accepts only n*"a" or n*"b" inputs?
I'd like to create a NFA that accepts only inputs like "aaaaa";"a";"bb";"bbb", but not like "aab";"aabaa". Is the even possible? As far as I understand NFA is processing a superspositon of all sub-inputs. So then, if given automaton accepts "a" or "b", it would always accept "ab" just like it accepts "b". Is there a way around, am I missing something?

Would it work? After reading n\*'a' and then 'b' the automaton leaves accepting state but in the same time it is entering another accepting state.

# Answer
> 1 votes
Yes it is.

Considering regular expression and NFA have the same power (source here), your question amounts to asking if there is such a regular expression.

So the regular expression would be /a\*|b\*/.

As for a NFA doing such a thing, here is an article describing how to go from regex to NFA.

In the article about regex to NFA, there is a section at the end explaining about metacharacter \\$ for end of string. An actual regex for your problem would then be /^(a\*|b\*)$/ .

---
Tags: automata, finite-automata
---


# Question
Title: Computing coefficients of $p(x)^n$ in time $O(n \log n)$
For homework I've to give an algorithm that computes the coefficients of the polynomial $p(x)^n$ in time $O(n\log n)$, where $p(x)$ is a polynomial of degree 7.

As an hint I'm told to consider first the case where $n$ is a power of 2.

My guess is that I should use FFT and somehow manipulate it with modulo operations (maybe using the fact that for even powers the unity roots of power $n$ are the same as for $n/2$, only twice) but I'm pretty clueless about this one.

# Answer
> 3 votes
Suppose $n = 2^k$ and for $0\leq i \leq k$, set $p\_i(x) = p(x)^{2^i}$. We want to efficiently compute $p\_k(x)$.

It is clear that for $0\leq i \< k$, $p\_{i+1}(x) = p\_i(x)^2$. Using the Cooley-Tukey algorithm, knowing $p\_i(x)$, we can compute $p\_{i+1}(x)$ in time complexity $O(d\_i\log d\_i)$ where $d\_i = \deg p\_i = \deg p \times 2^i = 7\times 2^i$.

We can know compute $p\_k(x)$ by successively computing $p\_1, p\_2, …, p\_{k-1}$. The total time complexity will be:

$$O\left(\sum\limits\_{i=0}^{k-1} i 2^i\right) = O(k2^k) = O(n\log n)$$

Now for the general case where $n$ is not a power of two, you can choose the intermediate polynomials you compute based on the binary decomposition of $n$, like in fast exponentiation.

---
Tags: polynomials, fast-fourier-transform
---


# Question
Title: How to prove NP-hardness of a Hamiltonian Path problem by reducing longest-path problem?
I know how to prove longest-path problem by reducing Hamiltonian Path problem.

Here I want to prove NP-hardness of a Hamiltonion Path problem by reducing longest-path problem. (pretend we know longest-path problem is NP-hardness, not Hamiltonion Path problem)

I'm wondering if it is possible to reduce Hamiltonian Path problem to longest path problem.

Is there any way I can do that?

# Answer
> 3 votes
Suppose you have a graph $G$ of order $n$. $G$ has a simple path of length $\geq n - 1$ if and only if $G$ has a hamiltonian path.

---
Tags: complexity-theory, np-complete, reductions, proof-techniques
---


title: Interrupt enabling and disabling

text:
# Question
Title: Interrupt enabling and disabling
While reading about interrupt mechanism, I understood that there is an IRQ signal line on the bus by which an I/O interface raise an interrupt request.

There is an INTA signal line using which the processor indicates acceptance of to the interrupt request.The processor interrupts the program currently under execution, saves the current PC & PS in the stack and transfers control to the ISR meant for the I/O device concerned.

After completion of execution of the ISR the processor restores the saves PC & PS so as to resume execution of the interrupted program.

But can anyone help me to understand in depth about the mechanism for interrupt enabling and disabling.

# Answer
> 1 votes
The process that you've described happens only if interrupts are *enabled*. The IRQ request (via INTR line) asks the CPU to handle the interrupt. If the CPU accepts, it will issue an INTA as you describe.

The CPU doesn't always accept interrupts. For instance, if the CPU is "in the middle of something", then it might delay handling the interrupt (for instance, until the instruction which is currently being executed, finishes). Additionally, the CPU has an internal flag that indicates whether or not is should accept interrupts. In the x86 family, this is the IF (interrupt flag), and you can control it by the commands STI (set interrupt flag == enable accepting interrupts) and CLI (clear interrupt flag == disable accepting interrupts). In other CPUs the naming might be different or there might be a more sophisticated mechanism setting/clearing interrupts of specific type/priority.

If the IF is cleared and interrupts are disabled, the CPU just "ignores" the input INTR line. This is known as *masking* interrupts. The CPU just continues as if the INTR line is low... Once you set the IF, then the CPU will stop ignoring the interrupt and will handle it according to the standard procedure (save flags and return address, and jumps to the ISR, issuing INTA, etc.)

Just to make it clear, enabling/disabling interrupt does not change the way the external I/O creates the interrupt. It just changes the way the CPU behaves in case of an external interrupt: if enabled, the interrupt is processes. If disabled/masked, interrupts are ignored.

# Answer
> 1 votes
For x86 it is a bit more complex today. Especially with the advent of PCI. Most of that IRQ stuff you're talking about is emulated today and obsolete. Most devices I can think of, that people are using the most today, are devices connected to PCI devices. For example USB is connected to the xHCI PCI device, SATA drives are connected to an AHCI PCI device, network cards are PCI devices, graphics cards (even Intel HD Graphics integrated in your CPU) are PCI devices. Everything is a PCI device.

Mostly, this IRQ method of having a line per device is over. That was how it worked with the old 8259 PIC but today it is just being emulated. Especially, with the mandatory MSI/MSI-X capability of PCI-Express devices (if they follow the spec).

---
Tags: computer-architecture
---


title: Context-free language from grammar

text:
# Question
Title: Context-free language from grammar
I'm on second year IT studies. I can't do this on my own and my teacher is not eager to help. I went that way but I'm pretty sure it's wrong. Please, help :/

# Answer
Start out by replacing in the grammar all $Z$ by $y$, since from $Z$ this is the only derivation.

Then, you can easily see what $X$ does: from it we can derive $(xy)y^\*$ or $(yxy)y^\*$, combined can be written as $(xy+yxy)y^\*$ as a regular expression (notice that not always you can write down the derivations as regular expressions!)

Now, $Y$ derives either $xy$ or $yX$, and since $X$ derives $(xy+yxy)y^\*$, then $Y$ derives $xy+y(xy+yxy)y^\*$.

You can now complete the analysis by noticing that $S$ derives either $Yy$ which is $(xy+y(xy+yxy)y^\*)y$, or an additional $SX$. I believe from here you already understand what the language is :)
> 1 votes

---
Tags: context-free
---


# Question
Title: What are the minimum and maximum numbers of elements in a heap of height h?
I came across the question:

> What are the minimum and maximum numbers of elements in a heap of height $h$?

To which I came up with this theory: $$\sum\_{i=0}^{h-1} 2^i = 2^h-1$$

$2^h-1$ is the internal nodes and that is understood according to the understood fact. But because nowhere except CLRS mentions heaps to be a **Nearly Complete Binary Tree** everywhere it is mentioned as a Complete Binary Tree.

The maximum number of elements can be easily computed: $$\sum\_{i=0}^{h} 2^i = 2^{h+1}-1$$

But I cannot get the point of computing the minimum number of elements: Should it be: $$2^{h}+1$$ for $0$ or $2$ children property

Or should it be: $$2^{h}$$ for $0$ or $1$ children property

Reference1: https://walkccc.github.io/CLRS/Chap06/6.1/#61-1

Reference2: HeapSort

Thank you.

# Answer
> 3 votes
A heap of height $h$ is complete up to the level at depth $h-1$ and needs to have at least one node on level $h$.

Therefore the minimum total number of nodes must be at least $ \sum\_{i=0}^{h-1} 2^i + 1 = 2^{h}-1 + 1= 2^h. $, and this tight since an heap with $2^h$ nodes has height $h$.

# Answer
> 1 votes
I know there's already an accepted answer, but for those who've got the same question and are still a little bit confused (as I was), or sth is unclear, watch this crystal clear explanation till the end.

---
Tags: algorithms, binary-trees, heaps
---


# Question
Title: Why is there no "traditional"-mathy way to describe the general algorithm and give a more math-friendly definition of algorithm?
Why is there no algebraic definition of algorithm besides recursive functions?

If I'm wrong, what is the matheist definition of algorithm that you've ever seen in a paper and can you provide a link?

For example, modern machines do overflowed arithmetic by the rules of modulo $2^{32}, 2^{64}$, etc arithmetic.

So why is there rarely a discussion of a theoretical machine that works on finite groups or just integer quotient groups brought to some power which is the memory length (number of "words").

I think a lot can be done with math to solve algorithmic questions, but when one first approaches the subject, there is very little workable mathematics.

Recursive functions are nice, but mathematically they can be very hard to deal with. Since every recursive algorithm has an iterative counter-part, I wish there were a paper that had operators like $\sum\_{i=1}^{g(n)} f(i)$ which mimic a for-loop with bound dependent upon $n$ and that essentially evaluates $f(n)$ every loop.

Why can't we have this type of more traditional mathematics describe algorithms, or can we? Do you have a definition you're working on?

If so, please share it in an answer to this question.

# Answer
> 6 votes
If you're looking for algebraic structure, then you should look at the field of denotational semantics. This is exactly what you describe: using algebra, and often Category Theory, to model computation mathematically.

Some examples:

* Domain theory provides a mathematical model of the untyped lambda calculus, which is powerful enough to capture all computable functions. The trick is that, to model computation, we need to represent functions, but for any set $S$, the function space $S \to S$ is always larger than $S$. So there's no simple set that captures all computations involving computations. Instead, Dana Scott introduced domains, which impose additional structure on sets to avoid countability problems.
* SKI Combinators provide a "point-free" description of computation. Every computation can be expressed by composing and applying three base combinators $S$, $K$, and $I$. The equations for the combinators are:

+ $ S\ x\ y\ z = (x\ z)(y\ z)$
    + $ (K\ x) y = x$
    + $ I x = x$

So these equations, in some sense, give an algebraic account of all of computation.
* Cartesian closed categories provide models for typed programming languages. They don't capture all of computation, but they do provide an abstract model of it.
* Topos theory provides a generalization of logic using category theory. And logic corresponds to computation via the Curry-Howard correspondence

As for recursion, it turns out that you can eliminate it by instead using fixed-point combinators like the Y combinator. So recursion can always be eliminated from (untyped) languages, even without using iteration.

# Answer
> 2 votes
There is a definition, take a look at turing machines.

It still is extremely complicated to work with, so it won't be perfect. But it sill does give a different definition of computation, that can be useful in constructing theorems, such as the time hierarchy theorem.

---
Tags: algorithms, computability, recursion, loops, iteration
---


# Question
Title: If $\{ww^R \mid w \in L\}$ is regular, is $L$ itself regular?
If $L$ is some language and $\\{ww^R \mid w \in L\\}$ is a regular language then does $L$ have to be a regular language?

# Answer
Let $A = \\{ww^R \mid w \in L\\}$, and suppose that $A$ is regular. What can we say about $L$?

For a word $w \in \Sigma^\*$, let $E(w) = \\{x : wx \in A\\}$. Since $A$ is regular, there are only finitely many different $E(w)$.

Say that $w \in L$ is *self-terminating* if it has no extension in $L$. If $w \in L$ is self-terminating then $E(w)$ is finite, and the unique longest word it contains is $w^R$. Therefore if $w\_1 \neq w\_2$ are both self-terminating words in $L$, then $E(w\_1) \neq E(w\_2)$. Consequently, there are only finitely many self-terminating words in $L$. Let $L'$ result from removing them and all their prefixes. Thus every word in $L'$ has infinitely many extensions in $L'$.

Say that $w \in L'$ is *creative* if there are two different letters $\sigma,\tau$ such that both $w\sigma$ and $w\tau$ have extensions in $L'$. If $w \in L'$ is creative then we can recover $w$ from $E(w)$ by taking the longest common suffix which appears infinitely often. This implies that there are only finitely many creative words in $L'$. Let $L''$ result from removing all creative words in $L'$ and their prefixes. Thus every word in $L''$ has infinitely many extensions in $L''$, and all of them are prefixes of a single $\omega$-word.

Let $x$ be an $\omega$-word that $L''$ has infinitely many prefixes of, and choose the shortest such prefix $w\_x$. We can recover $x$ from $E(w\_x)$ in the following way: the first $\ell$ letters of $x$ are the reverse of the suffix of length $\ell$ of all long enough words in $E(w\_x)$. It follows that $L''$ consists of prefixes of finitely many $\omega$-words.

Let $x$ be one such $\omega$-word. By the pigeonhole principle, there exist $n\_1 \< n\_2$ such that $x\_1 \ldots x\_{n\_1},x\_1 \ldots x\_{n\_2} \in L$ and $E(x\_1 \ldots x\_{n\_1}) = E(x\_1 \ldots x\_{n\_2})$. Since all long enough words in the former start with $x\_{n\_1+1} \ldots x\_{n\_2}$, it follows that $x\_{n\_2+1} \ldots x\_{n\_2+(n\_2-n\_1)} = x\_{n\_1+1} \ldots x\_{n\_2}$, and continuing in this way, we see that $x$ is eventually periodic, say $x=yz^\omega$.

The number of words of given length in a regular language is eventually periodic. It follows that we can modify $L''$ to another language $L'''$, differing in finitely many words, such that $L'''$ also consists of prefixes of finitely many $\omega$-words, and furthermore there exists a modulus $m$ such that for each $a \in \\{0,\ldots,m-1\\}$ and each $\omega$-word, either all prefixes of length $nm+a$ are in $L'''$, or none of them. Up to finitely many words, for each $\omega$-word $x = yz^\omega$, these prefixes are of the form $y' (z')^\*$.

Every two $\omega$-words in $L'''$ differ in some symbol. It follows that for each such word $x$, and for each $a$, we can use regular closure operations to isolate the corresponding subset of $A$, which is of the form $$ \\{ ww^R \mid w \in y z^\* \\} = \\{ y z^n (z^R)^n y^R \mid n \geq 0 \\}. $$ We can further use regular closure operations to isolate $$ \\{ z^n (z^R)^n \geq 0 \\}. $$ Applying the pigeonhole principle to the sets $E'(z^n)$ (where $E'$ is the analog of $E$ to the new language), we see that $E'(z^{n\_1}) = E'(z^{n\_2})$ for some $n\_1 \< n\_2$. Since $(z^R)^{n\_1} \in E'(z^{n\_1}) = E'(z^{n\_2})$, it follows that $z^{n\_2}(z^R)^{n\_1} = z^{n\_1} (z^R)^{n\_2}$, and so $z = z^R$.

We conclude that there exist $a,b \in \mathbb{N}$, words $w\_1,\ldots,w\_a,y\_1,\ldots,y\_b$, and palindromes $z\_1,\ldots,z\_b$, such that $$ L = \sum\_{i=1}^a w\_i + \sum\_{j=1}^b y\_j z\_j^\*. $$ The corresponding language $A$ is $$ A = \sum\_{i=1}^a w\_i w\_i^R + \sum\_{j=1}^b y\_j (z\_j z\_j)^\* y\_j^R. $$
> 3 votes

---
Tags: regular-languages
---


# Question
Title: Hierarchial clustering cannonnical representation?
I have to handle large binary dataset. That is one of the reasons I have to build my own Hierarchical Clustering. As I digged into the algorithms I was surprised and not ;) to find that it is possible to have multiple (not just two) vectors that have the same distance (hamming,overlap,...), so you can pair them differently in a 'correct' way.

F.e. using overlap as similarity mesaure ... the following 3 vectors have overlap of 2 and there are 2 different correct pairing.

```
 sequence : 110,101,111

```

what this means is that there is multiple ways to cluster those :

```
 ((110,111),101)  vs (110,(111,101))

 sequence : 110,101,111,011

 (110,((111,011),101))  vs ((110,(111,011)),101)

```

Let me illustrate it with integers :

```
 2,6,8,4
 (2,((4,6),8))  vs ((2,(4,6)),8) vs ....

```

What this means is that there are no canonical way of clustering/dendogram .

How do you handle that ? Is there a different type of clustering that can have canonical/single representation ?

# Answer
> 1 votes
You can always adjust your algorithm to use a deterministic tie-breaking rule, e.g., sort the data points before applying the clustering algorithm, and always break ties in favor of the earliest/leftmost item. This yields a deterministic algorithm, so if you give it exactly the same input both times, it will produce the same clustering both times. I can't tell whether this is what you are looking for or not.

---
Tags: clustering, normal-forms, hamming-distance
---


title: Is $\Omega(n) = O(n \log n)$?

text:
# Question
Title: Is $\Omega(n) = O(n \log n)$?
problem $T(n) = 3T(n/4) + n \log n$

$f(n) = n \log n$ and $g(n) = n$

Why is $\Omega(g(n)) = O(n \log n)$? Is it because $\Omega$ means at some $n$ and constant, $\Omega(g(n)) = O(n \log n)$?

# Answer
> 2 votes
No. Consider $n^2 \in \Omega(g(n))$, obviously, $n^2\notin O(n\log n)$ and therefore $\Omega(g(n)) \neq O(n \log n)$.

# Answer
> 1 votes
Intuitively: $\Omega(\cdot)$ gives a *lower* bound, $O(\cdot)$ gives an *upper* bound. If I tell you $x \> 1$, you can't deduce an upper bound for $x$ from it.

---
Tags: asymptotics, big-o-notation
---


title: What is a Trace bit?

text:
# Question
Title: What is a Trace bit?
What is a trace bit in Processor Status register, I can't find any resource that describe about how it work, for now all I could find is that it take two bits 0,1 for Trace on/Trace off mode. Can anyone help me understand it in detail?

# Answer
Yuval's comment is correct. When the flag is set, the processor executes one instruction and then issues a trap (i.e. an interrupt), which is typically caught by the operating system.

The purpose is to help with debugging.

Programmers who are debugging their software want to set breakpoints at specific locations. This can be implemented using a variety of mechanisms, including the processor's debug registers, modifying code (i.e. overwriting an instruction with another instruction which causes a trap; the single-byte INT3 instruction on x86 is for precisely this purpose), or through the virtual memory system (i.e. marking a page in such a way that executing code in that area causes a page fault).

From the earliest days, another desired feature is single-step debugging, where the processor executes one instruction at a time and then returns control to the debugger. Many early CPUs would actually let you stop and "toggle" the processor clock to support single-stepping, but this required additional specialised hardware to make use of it which would add to the cost of a home machine.

Hence, the trace flag.

As a final note, I'm not surprised at all that you didn't know this. Very little attention is paid these days to the kind of support needed by both the CPU and OS to implement a debugger. Code modification, for example, interferes with the instruction pipeline on modern superscalar CPUs, so some extra circuitry is needed to make techniques like INT3 work.
> 4 votes

---
Tags: cpu
---


# Question
Title: What's the runtime complexity of this algorithm for breaking up string into words?
I am given a input string $s$ ("bedbathandbeyond") and a set of words {"bed", "bath", "beyond", "bat", "hand", "and"}. I need to divide the input string $s$ into a series of words in the dictionary. In this case, the two allowed outputs would be \["bed", "bath", "and", "beyond"\] and \["bed", "bat", "hand", "beyond"\]. Both outputs are allowed and none is better than the other.

Here is my recursive solution. On input $s$, it either outputs a decomposition of $s$ into a sequence of words in the dictionary, or Fail.

* If the input $s$ is empty, output the empty decomposition.
* Otherwise, go over all prefixes of $s$. For each prefix that belongs to the dictionary, recursively try to decompose the corresponding suffix, and if successful, output the corresponding decomposition.
* If no decomposition was found, output Fail.

In order to speed up the procedure, I envision using memoization. That is, I maintain a hashtable with answers to previous queries, and on input $s$, I first check whether I already know the answer for $s$. If not, after computing the answer, I put it in the hashtable.

If no memoization is used, the runtime is clearly exponential: we have $O(n)$ branching factor, and $O(n)$ as the depth: $O(n^n)$. With memoization; however, the algorithm seems to be polynomial: the procedure can be called with at most $n$ different inputs, and it then performs a polynomial amount of work on it.

I've been told by a very knowledgeable person that it's still exponential. Could someone explain why? I've been thinking very hard about it and I'm not sure why that's the case. If it matters, I'm implementing this algorithm in python.

# Answer
The running time is polynomial with memoization. If the original input string has $n$ characters, then there are only $O(n)$ possible suffixes of the original string, the function is only called on a suffix of the original string, and (ignoring recursive calls) the time to execute the function is polynomial; so the total running time with memoization is polynomial.
> 3 votes

---
Tags: algorithms, runtime-analysis, dynamic-programming, python, memoization
---


# Question
Title: How many languages are described by a regular expression?
How many languages can a Regular Expression describe is it only one or infinite? I have tried to google it but i haven't found any answer?

I know that a Regular Expression describes a Regular Language?

# Answer
If you look at the definition of regular expressions (they are usually defined in parallel to the language denoted) you see there is only one language denoted by a given expression. That language could be empty, finite or infinite, but that is another question.
> 2 votes

# Answer
Every regular expression describes one language --- the language of words matched by the regular expression, or, in other words, the language of words accepted by the finite automaton corresponding to the regular expression.
> 3 votes

# Answer
A language is described by a regular expression if and only if it is regular.

There are infinitely many regular languages over any fixed alphabet.
> 0 votes

---
Tags: regular-languages, regular-expressions
---


# Question
Title: Assuming the original instance is not easy in NP-hardness reduction
Partition problem: given a non-empty finite set $P = \\{p\_i : i ∈ I = \\{1,\dots,m\\}\\}$ of $m$ positive integers such that $\sum\_{i=1}^m p\_i = 2T$, can $I$ be partition into two disjoint subsets $I\_1, I\_2$ such that $\sum\_{ i \in I _ 1} p\_i = \sum\_{ i \in I _ 2} p\_i = T$?

My question is: when we deriving reduction from Partition to another problem, can we assume that $\max\_{ i\in I} p\_i \leq T$?

# Answer
A polynomial time reduction from PARTITION to a language $L$ is a polynomial time function $f$ such that if $x$ is a Yes instance of PARTITION then $f(x) \in L$, and if $x$ is a No instance of PARTITION then $f(x) \notin L$.

If $x$ is an "easy" instance — belongs to some polynomially solvable class of instances — then $f$ can just solve it, outputting a fixed Yes or No instance of $L$. Therefore you can assume that $x$ is a "hard" instance.
> 2 votes

---
Tags: polynomial-time-reductions
---


# Question
Title: Are run time bounds in P decidable when the problem is promised that an input program must halt?
I'm solving Problem 11-10(b) in "what can be computed".

> **11.10** Consider the decision problem HALTSINSOMEPOLY (HISP), defined as follows. The input is a program P, and the solution is “yes” if and only if there exists some polynomial q(n) such that, for every n, P halts after at most q(n) steps on all inputs of length ≤ n.
>
> (a) State, with proof, which of the following statements are true: (i) HISP is undecidable, (ii) HISP ∈ Expo, (iii) HISP ∈ Poly.
>
> (b) Would your answer to a change if we restrict the domain of HISP, so that the input P is guaranteed to halt on all inputs? (Note: This is an example of a promise problem, in which the input is promised to have a certain property, which may itself be undecidable.)

The proof of 11-10(a) is basically same as "Are runtime bounds in P decidable?", which is that HISP reduces to halting problem.

If an input program is promised to halt, however, this reduction does not help us.

Is there any suggestion to solve this problem?

# Answer
> 0 votes
Given a Turing machine $T$, construct a new Turing machine $T'$ which, in input of length $n$, simulates $T$ for up to $n$ steps. If $T$ halts then $T'$ also halts, and otherwise $T$ counts up to $2^n$ and then halts.

---
Tags: undecidability, halting-problem
---


# Question
Title: virtual machine based programming languages vs low level
I took programming lecture it was about C/java and how to build compilers, so I wanted to know.

As far I see, languages like Java/C# are developing their virtual machine CLR/JVM with good base and are improving repeatedly to increse its speed and their JIT compiler.

So I was wondering, is it possible in near future that languages such as JAVA or C# to be faster than C++ ? Or is it logically impossible ?

# Answer
It is impossible for one language to be faster than another language, period.

A programming language is a set of abstract mathematical rules and restrictions. It is an idea. A piece of paper. You cannot run a language, therefore, you cannot measure its performance.

What you *can* do is run a particular piece of code written in one language using a particular version of a particular implementation of that language with a particular set of command line flags in a particular environment and compare its performance to a different piece of code written in a different language run with a different version of a different implementation configured with a different set of flags in a different environment.

But with all those differences, it will then be impossible to tell *which* of all of those differences actually caused the difference in performance. Was it the different benchmark programs? The different configuration options? The different versions? The different implementations? The different environments? Was the difference in performance caused by the language or by the quality of the implementations? Was it maybe caused by the difference in how much money was invested in optimizations?

I am willing to bet that for every set of environments and implementations that you can present me where language A is faster than language B, I can find a different set of environments and implementations where for the same two pieces of code, language B outperforms language A.

For example, there are Java implementations that are really fast. There are C++ implementations that are really slow. All I need to do is run my benchmarks using those two implementations, and I will have "proven" that Java is much faster than C++.

In the YARV Ruby VM, the `Hash` class is implemented in C. In the Rubinius Ruby VM, the `Hash` class is implemented in Ruby. Benchmarks that make heavy use of `Hash`es run faster on Rubinius than on YARV. Does that prove that Ruby is faster than C?
> 3 votes

---
Tags: programming-languages, compilers, java, c++
---


# Question
Title: What will be the frequency count of this code snippet?
```
int i=0,j;

while(i<=n)
{
 while(j<=(i+1)){
   a=a*a;
    j++;
  }
i++;

```

This question was in my homework and we have to calculate the frequency count of the code above. I am having difficulty understanding how the code will execute and how many times will the loops execute. I know the inner loop is dependent on 'i', otherwise I'm lost.

# Answer
> -1 votes
> ```
> Statement         Frequency Count
> int i=0,j                1
> while(j<=(i+1))         n+1
>  a=a*a                   n
>  j++                     n
> i++                      1
>
> ```

f(n) = 3n+3 = Time Complexity
Degree is O(n)

Space:
a = n
i = 1
j = 1
S(n) = n+1 = Space Complexity
Degree is O(n)

---
Tags: algorithms, time-complexity, data-structures
---


# Question
Title: Is this relation in Boyce-Codd's Normal Form?
I thought I understood BCFN until I bumped into this example from my course slides.

* A relation in a library database contains what books are currently borrowed by what users.
* The relation contains the unique ID of the user, their name and the title of the book.
* Different users might share the same name.
* A book can only be borrowed by one user.
* A user can have borrowed more than one book.

An example of this relation could be:

| USER\_ID | USER\_NAME | BOOK\_TITLE |
| --- | --- | --- |
| U012 | Charles | Hamlet |
| U034 | Alex | Blue Moon |
| U491 | Diane | Capital |
| U034 | Alex | The Crow |
| U491 | Diane | Economics 2 |
| U012 | Charles | Lost Girl |
| U034 | Alex | Chess basics |
| U012 | Charles | Greek History |
| U491 | Diane | Red Mars |

According to the slide, this relation is in Boyce-Codd's Normal Form,as:

> all functional dependencies of the form $\alpha \rightarrow \beta $ are either trivial or satisfy that $\alpha$ is a super-key of the relation

While it is my understanding that those are the requirements for BCNF, I don't think this relation satisfies them. In particular, the functional dependency `USER_ID` $\rightarrow$ `USER_NAME` is not trivial (as $\beta$ is not a subset of $\alpha$) and $\alpha$ is not a super-key (since by itself we cannot distinguish between entries representing different books borrowed by the same user).

Am I missing something?

# Answer
> 1 votes
Assuming that each book has a different title, you are correct in thinking that the relation is not in BCNF.

In fact, the (only) candidate key of the relation is `Book_title`, so the functional dependency `User_id -> User_name` violates the definition of BCNF. Assuming that a cover of the dependencies are:

```
User_id -> User_name    (each user_id identifies a user with a certain name)
Book_title -> User_id   (each book can be borrowed only by a certain user)

```

a decomposition of the original relation in BCNF is:

```
R1(User_id, User_name)  with candidate key User_id
R2(Book_title, User_id) with candidate key Book_title

```

---
Tags: database-theory, normal-forms
---


# Question
Title: What's an example of a planar graph with two embeddings whose geometric duals are nonisomorphic?
How to prove that the dual of the dual of a connected planar graph $G$ is isomorphic to $G$?

In the post linked above, the user "plop" gives a great response where they claim, in particular, that a **plane graph** $G$ has a well-defined geometric dual. Paraphrasing, for any two drawings $G^\*\_1$ and $G^\*\_2$ obtained in the following way, there exists a unique **planar graph** $Y$, up to isomorphism, such that the plane graphs $G\_1^\*$ and $G\_2^\*$ are planar embeddings of $Y$. Consequently, we may write $G^\*$ for either $G\_1^\*$ or $G\_2^\*$, and call it **the** *geometric dual* of $G$.

To obtain such a plane graph $G^\*$ from $G$, draw a point in$^\dagger$ each face of $G$, and for each arc $e$ of $G$, draw a new arc passing once through $e$ connecting the points in the two faces $f\_1$ and $f\_2$ incident with $e$. Do this such that no two of these new arcs intersect.$^{\dagger\dagger}$ This new set of points together with this new set of arcs describes the plane graph $G^\*$.

$^\dagger$To make complete sense of this construction, one needs at least the Jordan Curve Theorem, and according to "plop" also needs the Jordan-Shoenflies Theorem. $^{\dagger\dagger}$By the way, shouldn't this also require us to use the fact that a topological subspace of $\mathbb R^2$ (or of $S^2$) is connected if and only if it is path-connected? (Otherwise I could imagine two curves technically not intersecting but with something pathological happening where the curves get arbitrarily close to each other and end up "crossing" while still being *curves* in the sense that they are topological embeddings of $\[0,1\]$. This is a little beside the point.)

I am ok with the above claim. My question is:

Does there exist a planar graph $X$ with two planar embeddings $G\_1$ and $G\_2$ such that $G\_1^\*$ and $G\_2^\*$ are the planar embeddings of nonisomorphic graphs $Y\_1$ and $Y\_2$? If so, what's an example construction. If not, why not?

Note: Wikipedia claims seems to claim that the answer is "yes", but doesn't provide an example. I put a \[citation needed\] tag, so maybe once this is resolved, we can link it back to here.

> The definition of the dual depends on the choice of embedding of the graph G, so it is a property of plane graphs (graphs that are already embedded in the plane) rather than planar graphs (graphs that may be embedded but for which the embedding is not yet known). For planar graphs generally, there may be multiple dual graphs, depending on the choice of planar embedding of the graph.

https://en.wikipedia.org/wiki/Dual\_graph

# Answer
There is an answer in Graph Theory by Bondy and Murty:

It is clear that both graphs are isomorphic. Their respective duals are not, because each face of the first dual has degree 3 (except the unbounded one, of degree 5), and there are two faces of degree 4 in the second dual.
> 2 votes

---
Tags: graphs, planar-graphs, topology, duality
---


# Question
Title: Big-O notation for Polynomial Time Complexity
Recently we had a quiz where one of the question were -

```
Q: Asymptotic notation for polynomial :

 - 2^Ο(n)
 - Ο(n log n)
 - n^Ο(1)
 - None of these

```

I know that Polynomial time complexity is $\mathcal{O}(n^c)$, where $c$ is an arbitrary constant.
But then I checked it up on Wikipedia, and it got me confused.

According to Wikipedia, Polynomial Time Complexity is $2^\mathcal{O(log n)} = poly(n)$, where $poly(x) = x^\mathcal{O(1)}$.

---

So my questions are -

1. What is the $Big-O$ notation for ***Polynomial Time Complexity*** and how is it $2^\mathcal{O(log n)} = poly(n)$ ?
2. What will be the answer for the quiz ?
<sub> I have answered *None of these* .</sub>

Also it has got this line - `In the table, poly(x) = x^O(1), i.e., polynomial in x.`
What does ***polynomial in x*** means ?

# Answer
The question is worded in a tricky way. When it says "polynomial" it really means "all functions that represent a polynomial complexity class". Essentially, they want the asymptotic notation for the functions $f(n)=1$, $f(n)=n$, $f(n)=n^2$, etc. The reason we want this is because you would see this inside big-O like $O(1)$, $O(n)$, $O(n^2)$, etc. Those functions represent these big-O sets.

The reason we talk about it this way is because we are talking about it in the world of complexity classes. An example is $P$.

\begin{align} P = DTIME(poly(n)) = \bigcup\limits\_{k\in\mathbb{N}}DTIME(n^k) \end{align}

From the wiki on DTIME.

> If a problem of input size $n$ can be solved in $O(f(n))$, we have a complexity class $DTIME(f(n))$ (or $TIME(f(n))$).

So the asymptotic notation for the set of these functions is $n^{O(1)}$. The following is a way to reason about it. \begin{align} n^{O(1)} &= n^{\\{0,1,2,...\\}} \\ &= \\{1,\ n,\ n^2,\ ...\\} \end{align}

To show that $2^{O(\log n)} = poly(n)$ is with the same reasoning as above. \begin{align} 2^{O(\log{n})} &= 2^{\\{0\cdot\log{n},\ 1\cdot\log{n},\ 2\cdot\log{n},\ ...\\}} \\ &= 2^{\\{0,\ \log(n^1),\ \log(n^2),\ ...\\}} \\ &= \\{2^0,\ 2^{\log(n)},\ 2^{\log(n^2)},\ ...\\} \\ &= \\{1,\ n^1,\ n^2,\ ...\\} \\ &= n^{O(1)} \end{align}

To formally show these are equal, you would have to use set notation.

Finally, "polynomial in x" means that $poly(x)$ grows polynomially depending on $x$. You can see that some of the entries in the table have a function as the argument to $poly$. For instance, $poly(\log{n})$ (polylogarithmic) grows slower than $poly(n)$ (polynomial) since $O(\log{n}) \< O(n)$.
> 2 votes

---
Tags: asymptotics, big-o-notation
---


# Question
Title: How can you convert the depth of a boolean circuit to its size?
I know that the depth of a circuit is the maximal length from an input gate to the output gate of the circuit and its size is its number of gates.

Is there a formula that you can go from depth to size and can someone explain the steps?

# Answer
First of all, there are several types of (Boolean) circuits:

* Circuits with unbounded fan-in. These are circuits with AND, OR, and NOT gates, where the AND and OR gates can have arbitrarily many inputs.
* Circuits with bounded fan-in. These are circuits with AND, OR, and NOT gates, where the AND and OR gates have exactly two inputs.
* Formulas, which are circuits with bounded fan-in and fan-out. You can think of formulas either as expressions using the operators binary AND, binary OR, and unary NOT, or as circuits with AND, OR, and NOT gates, where the AND and OR gates have exactly two inputs, and the output of each gate is used only once.

(There are even more types of circuits. For example, we could vary the set of gates. But such circuits are less commonly encountered.)

For circuits with unbounded fan-in, not much can be said about the relation between depth and side, since there are depth 1 circuits of arbitrary size.

For circuits with bounded fan-in, we can say that a circuit of depth $d$ has size at most roughly $2^d$. It also has size at least roughly $d$. Both of these are tight: a circuit whose shape is a depth $d$ complete binary tree and whose gates are AND computes the AND of $2^d$ inputs in depth $d$ and size roughly $2^d$, and in contrast, you can construct a "path" (a tree where the left child of every internal node is a leaf) which computes the AND of $d$ inputs in size and depth both roughly $d$.

For formulas you cannot improve on these relations, but you can there is another important property: a formula of size $s$ can always be converted to a formula of size $s^{O(1)}$ and depth $O(\log s)$, an operation we call *balancing*. It is conjectured that the same cannot be said for circuits (this is one interpretation of the $\mathsf{NC^1}$ vs $\mathsf{P}$ question), though every circuit of size $s$ can be converted to depth $s/\log s$.
> 0 votes

---
Tags: circuits
---


# Question
Title: Myhill-Nerode - Prove irregularity for $\{a^{n^3}\}$
I need to prove that the following language is *not regular* by showing there are infinite pairwise distinct equivalence classes: $$ L = \\{a^{n^3} \mid n \geq 1\\} \subseteq \\{a\\}^\* $$

Looking at a few examples, I intuitively noticed that for each $i \geq 1$ there is an equivalence class $\[a^{i^3}\] \neq \[a^{j^3}\]$ for $i \neq j$ because the number of $a$'s we need to add increases exponentially with $i/j$. Thus for every $i$ we can add a suffix of $a$'s to reach the next higher power $(i+1)^3$ but the length of that suffix is different for every other power, so that each equivalence class only actually contains the representative itself.

**Example**: $$ \begin{align\*} &n = 1 \implies a \\ &n = 2 \implies a^8 \\ &n = 3 \implies a^{27} \\ \vdots \end{align\*} $$ Then $$ \begin{align\*} & \[a\] = \\{x \in \\{a\\}^\* \mid a \\; R\_L \\; x\\} = a \\ & \[a^8\] = \\{x \in \\{a\\}^\* \mid a^8 \\; R\_L \\; x\\} = a^8 \\ \vdots \end{align\*} $$ Consider $\[a\]$. For $z = a^7$ we get $az = aa^7 = a^8 \in L$, but starting from $i \geq 2$, we have that $a^{i^3}z \notin L$.

How can I write this down in a more formal/rigorous way?

# Answer
> 2 votes
More generally, you can use Myhill–Nerode to prove the following characterization:

> For $A \subseteq \mathbb{N}$, let $L(A) = \\{ a^n : n \in A \\}$.
>
> The language $L(A)$ is regular iff $A$ is eventually periodic.

In particular, if $A$ is an infinite set with *density zero* then $L(A)$ is not regular. Here *density zero* means:

$$ \lim\_{n\to\infty} \frac{|A \cap \\{0,\ldots,n-1\\}|}{n} = 0. $$

This shows that $\\{a^{n^k} : n \in \mathbb{N}\\}$ is not regular for any $k \geq 2$.

---

Let us prove the claimed characterization. If $A$ is periodic, say with period $m$, then $L(A)$ is clearly regular: it is accepted by a circular DFA with $m$ states. If $A$ is eventually periodic then there is a periodic $B$ such that $L(A),L(B)$ differ in finitely many words, and so standard closure operations show that $L(A)$ is regular.

Now suppose that $L(A)$ is regular. The equivalent class of $a^m$ is the set $E\_m = \\{ k \in \mathbb{N} : m+k \in A \\}$. Since there are finitely many equivalence classes, there exist $m \< p$ such that $E\_m = E\_p$, that is, for all $k \in \mathbb{N}$, $m + k \in A$ iff $p + k \in A$. In other words, for all $\ell \geq m$, $\ell \in A$ iff $\ell + (p-m) \in A$. Hence $A$ is eventually periodic (with period $p-m$).

---
Tags: regular-languages, formal-grammars
---


# Question
Title: PDA translating $a^{m+n} b^n$ to $x^{2m+2} y^{3n}$
On my compilation theory exam we had the following problem:

Construct a PDA translator (just one stack) such that it translates the language $$ a^{m+n}b^n \rightarrow x^{2m+2}y^{3n}, \text{ where } n,m \geq 0$$
I cant think of any solution. My approach was as follows: I would put in the stack $m+n$ symbols of $a$. Then, for every $b$ in $b^n$ I would remove one $a$. Then I would be left with $m$ symbols of $a$ in the stack. After, that, I would emit two symbols of $x$ and I would empty the stack. For every $a$ that was left I would emit two symbols of $x$. I could not figure out how to obtain the second part because in order to determine $m$ I would need subtract the $n$ from $b^n$.

By PDA translator I mean a regular PDA but instead of accepting/rejecting a language, we use it to transform a language into another (every transition in the automaton can emit some symbols).

# Answer
> 1 votes
This seems impossible if the translator has to be deterministic.

Let's clean up the problem and ask the PDA to convert $a^{n+m} b^n$ to $x^m y^n$ (your translator can be converted to such a translator by using a regular transducer). Since your PDA is deterministic, it cannot output anything until it knows whether $m = 0$ or not, which can happen in one of two ways: either it reaches the end of input, or it reads $a^n b^n$ (which must also be the end of input).

Now let us modify your PDA so that instead of outputting $x^m y^n$, it checks that the rest of the input has the form $x^m y^n$. We obtain a deterministic PDA accepting the language of all words of the form $a^{n+m} b^n x^m y^n$, yet this language is not context-free (you can see this by intersecting with $a^\*b^\*y^\*$ to get the language of all words of the form $a^nb^ny^n$).

---
Tags: formal-languages, automata, compilers, pushdown-automata, interpreters
---


# Question
Title: Probability of reaching a state in asymmetric random walk
Consider the following random walk:

Namely, if $S\_i$ is the state at time $i$, then $\Pr(S\_{i+1}=1|S\_i=0)=1$, and for every $s\>0$ we have $$S\_{i+1}|S\_i=s= \begin{cases} s+1 & \text{w.p. }1-p\\ s-1 & \text{w.p. }p \end{cases}. $$ In my application, $p\>\frac{1}{2}$. I'm interested in two quantities, $\Pr(S\_T \> H)$ and $\mathbb E(S\_T)$. My intuition is that $\Pr(S\_T \> C \ln T)\leq \frac{1}{T^2}$ for some global constant $C$, and that $\mathbb E(S\_T)=O(1)$. However, I couldn't show it (yet).

Any ideas?

---

Here are some trivial claims. First, $\Pr(S\_T \> H) \leq \exp(-\frac{H^2}{T})$ due to Azuma's inequality, but that doesn't use the value $p$ nor the fact that $p\> \frac{1}{2}$. Second, $\mathbb E(S\_T) \leq O(\sqrt{T})$ since $S\_t$ is stochastically dominated by a symmetric random walk, for which the expected place at time $T$ is $O(\sqrt{T})$.

The stationary distribution is easy to find, being $\pi\_0=1-\frac{1}{2p}$ and $\pi\_i = \frac{\pi\_0}{p} \left(\frac{1-p}{p}\right)^{i-1}$, but I'm not sure how to use it.

# Answer
Suppose that $S\_T \> C\ln T$. Let $T\_0-1$ be the last time that the random walk reached the origin. Thus if we run an unconstrained biased random walk starting at position $1$ at time $T\_0$, we reach beyond $C\ln T$ at time $T$. This can only happen if $T-T\_0 \geq C\ln T$.

The probability that an unconstrained biased random walk starting at position $x$ ends up to the right of $x$ after $L$ steps is exponentially small in $L$, by Hoeffding's inequality. In your case, $L \geq C\ln T$, and so this probability is polynomially small in $T$. Taking a union bound over all possible values of $T\_0$ (at most $T$ of them), you can choose $C$ so that the error probability is at most $\frac{1}{T^d}$ for $d$ of your choice.

(More formally, choose the $\pm 1$ steps $\xi\_1,\ldots\xi\_T$ of your walk ahead of time. You start at some fixed $S\_0$, which here is implicitly assumed to be $S\_0 = 1$, and then $S\_{n+1} = |S\_n + \xi\_{n+1}|$. If $S\_T \> C\ln T$ then $S\_{T\_0} + \xi\_{T\_0+1} + \cdots + \xi\_T \geq C\ln T$, by definition of $T\_0$. We bound the probability that this happens for *fixed* $T\_0$ and take a union bound.)

---

As for $\mathbb{E}(S\_T)$, since you have a stationary distribution, then your chain is *positive recurrent* (see Chapter 21 of Markov Chains and Mixing Times). Your chain is not ergodic due to a parity issue, so let's consider the square of your chain (moving two steps at once). The square decomposes into two separate chains. The one of the even integers looks as follows:

* At $0$, stay at $0$ with probability $p$, and transition to $2$ with probability $1-p$.
* At $2n\>0$, transition to $2(n-1)$ with probability $p^2$, stay at $2n$ with probability $2p(1-p)$, and transition to $2(n+1)$ with probability $(1-p)^2$.

The one on the odd integers looks as follows:

* At $1$, stay at $1$ with probability $p(2-p)$, and transition to $3$ with probability $(1-p)^2$.
* At $2n+1$, transition to $2(n-1)+1$ with probability $p^2$, stay at $2n+1$ with probability $2p(1-p)$, and transition to $2(n+1)+1$ with probability $(1-p)^2$.

Let's focus on the case of even integers. Let $f\_{2n} = cn$. Using $p(i,j)$ for the probability to transition from $i$ to $j$,

\begin{align} &p(0,0) e^{f\_0 - f\_0} + p(0,2) e^{f\_2 - f\_0} = p + (1-p) e^{-c}, \\ &p(2n,2n-2) e^{f\_{2n-2} - f\_{2n}} + p(2n,2n) e^{f\_{2n} - f\_{2n}} + p(2n,2n+2) e^{f\_{2n+2} - f\_{2n}} = p^2 e^{-c} + 2p(1-p) + (1-p)^2 e^c. \end{align} For any $c \> 1$, the first line is strictly less than 1. For $c = 1+\epsilon$, the second line is $$ p^2 (1 - \epsilon) + 2p(1-p) + (1-p)^2 (1 + \epsilon) + O(\epsilon^2), $$ which is less than 1 for any small $\epsilon\>0$ since $p^2 \> (1-p)^2$.

We have thus verified Popov's conditions for geometric ergodicity (see for example Isaacson), and we conclude1 that there exists $\beta \< 1$ such that $$ \left|\Pr\[S\_{2T} = 2n \mid S\_0 = 0\] - \pi^e\_{2n}\right| = O(e^{f\_0-f\_{2n}}\beta^T) = O(\beta^T), $$ where $\pi^e$ is the stationary distribution of the even component of the squared chain, given by $\pi^e\_{2n} = 2\pi\_{2n}$. Denoting the corresponding expectation by $E^e = \mathbb{E}(\pi^e)$, we conclude that $$ |\mathbb{E}(S\_{2T} \mid S\_0 = 0) - E^e| = O(\beta^T). $$ Similarly, $$ |\mathbb{E}(S\_{2T+1} \mid S\_0 = 0) - E^o| = O(\beta^T). $$ We obtain similar results for any other fixed starting point.

1This equation appears in Popov's paper but not in Isaacson's.
> 1 votes

---
Tags: probability-theory, random-walks
---


# Question
Title: Find distinict elements in an array in $O(n)$ time
Given this pseudo-code that finds the number of distinct elements in the given array:

```
D(A) // A is an array of numbers
U_Size = 1
For i=2 to length(A)
                  U=?
  For j=1 to U_Size
    If A[j]=A[i]
     Then U = FALSE
      j = U_Size
   if U = TRUE
     Then U_Size = U_Size +1
         A[U_Size] = A[i]
return U_Size

```

Time complexity for that alogrithm is $O(n^2)$

I will need to write 2 new algorithms for the same purpose in $O(n)$ according to one of each of the conditions bellow:

1. let's say that the numbers are integers only and inside the range of \[$10,10n$\], without using any sorting method
2. Now, there is no given range of numbers, and I can use any sorting method I want

> MY SOLUTION:
>
> for the first condition, I tried using HashSet, but I think it has a more sofisticated solution. My pseudo-code:
>
> ```
> countDistinctNums(int A[], int n)
>   hashSet hs = new Hashset
>     for i=0 to n
>     // add all the elements to the HashSet
>       hs.add(A[i])
>
>     // return the size of hashset as it consists of
>     // all unique elements
>   Return hs.size();
>
> ```
>
> for the second one, a hash table will be the optimal solution but I think also one of the linear-sorting methods will be good enough

**My questions are:**

1. Does HashSet is a good solution for one of the conditions ( or both )?
2. How do I implement an HashTable for the solution of the second condition?

# Answer
For the first task you can use a solution similar to yours. Let the input array be $A\[1, \dots n\]$. Create an array $B$ indexed with the integers from $10$ to $10n$ where each entry is a boolean value initially set to false. Then, for each input element $A\[i\]$, set $B\[A\[i\]\]$ to true. At the end of the above loop, return the number of indices $y$ such that $B\[y\]$ is true. This runs in $O(n)$ worst-case time.

Notice that, depending on how the hashtable is implemented, a hashtable-based solution is not guaranteed to have a **worst-case** time complexity of $O(n)$. Usually the hash-tables provided by the common programming languages only provide you with **expected** constant time operations.

Also, if don't have any other information on the values the the input integers, you can't use linear-time sorting algorithms (since their complexity depends on the range of the input values).

Anyway, your solution already works for the general problem in $O(n)$ **expected** time.

I don't think the general problem can be solved in $O(n)$ worst-case time. According to Wikipedia, there is a lower bound of $\Omega(n \log n)$ on the algebraic decision tree model, and randomness doesn't help.
> 2 votes

# Answer
You can solve the second task with $O(n)$ expected running time (average-case running time), if you use a hash table with a 2-universal hash function. As far as I know, no deterministic $O(n)$-time algorithm is known.
> 1 votes

---
Tags: time-complexity, data-structures, hash-tables, pseudocode, linear-complexity
---